RDBMSの順序付きリストの最も適切なデータ構造ですか？

Question

私は、数百万アイテムの注文リストをMySQLデータベースに保存しています。合理的には、アイテムをリストに追加または削除する必要があります。同様にしばしば、項目のリスト内の位置を決定しなければならない。私は、読み取り/書き込みの比率は約50:50だと思います。

リンクリストモデルから始めて、[1]とそこで説明したさまざまなモデルを読んでいます。厳密なリンクリストの場合、隣接リストモデルはうまく動作しますが、読み書きの比率が多かれ少なかれ等しいので、標準的な連続リストを使用して分割と征服のアプローチに行きます：

リスト全体バケットサイズのインデックスとメインリスト内の相対位置を維持しながら、おおよその長さ（例えば〜10000）のバケットに変換します。各アイテムは特定のバケットに割り当てられ、そのバケット内の位置を追跡します。

このアプローチでは、アイテムの位置は、リスト内のアイテムのバケットに先行するバケットのサイズを合計し、そのアイテムの位置を独自のバケット内に追加することによって決定されます。リストからアイテムを挿入/削除するには、アイテムが追加または削除されているバケットに結果の「シフト」がローカライズされます。そのバケットのサイズもそれに応じて更新する必要があります。

このアプローチではある種の非正規化（バケットサイズ）があります。トランザクションの場合でも、本質的にスレッドセーフではありません。削除/挿入時にアイテムのテーブルを照会して、アイテムが変更され、そのアイテムのバケット内の他のすべてのアイテムに対して「シフト」を実行するように更新されます。これらのアクションがアトミックでないかぎり（ストアド・プロシージャによるものかもしれません）、スレッドは常にデッドロックします。

この種のデータをRDBMSに保存するための適切なアプローチはありますか？スレッドセーフの問題は大きな頭痛を引き起こしています。ストアドプロシージャを使用するよりも、この問題を解決するためのより良い方法があるはずです。

多くのありがとう、 マット。

[1] Database Structure for Tree Data Structure

Answer 1

を使用すると、リンクリスト（ない階層）必要な場合は、ちょうど私のブログにこの資料に記載されたアプローチを使用することができます。

• Sorting lists

、この簡単なクエリ：

SELECT @r AS _parent, 
     @r := (
     SELECT id 
     FROM t_list 
     WHERE parent = _parent 
     ) AS id 
FROM (
     SELECT @r := 0 
     ) vars, 
     t_list 

idとparentにはUNIQUEインデックスが有効であることが定義されていることを確認してください。

@r := 0を@r := @id_of_record_to_start_withに置き換えて、任意のidからブラウズを開始してください。

だけでクエリを逆に、アイテムの位置を見つけるには：

SELECT COUNT(*) 
FROM (
     SELECT @r AS _id, 
       @r := (
       SELECT parent 
       FROM t_list 
       WHERE id = _id 
       ) AS id 
     FROM (
       SELECT @r := @item_id 
       ) vars, 
       t_list 
     ) q