階層型順序付きリスト（flatfile/sql/nosql）を永続化する

Question

階層型の順序付きリストを格納します。 1つの例は、入れ子にされたToDoリストです。もう1つの例はXMLです。子供たちが秩序だったのはただの樹木だろう。簡単にするため、エントリは単なるテキスト文字列です。

ことは、一般的な操作が高速であることが重要であるので、リストには、ユーザによって編集されるということです。

• 編集要素
• 要素
• を削除する前にエントリを挿入します別の

データ構造でこれを行う方法を想像することができます：エントリはリンクされたリストです。子が含まれている場合、リンクされたリストの先頭も指しています。エントリIDを実際のデータにリンクするハッシュテーブルがあります。

• の編集は、ハッシュを検索して、
• 削除は、ハッシュを見上げると
• 挿入はハッシュを見上げている
リンクリストの削除を行っているリンクリストのデータ部分を交換し、リンクリストの挿入を行っています

しかし、私はデータを保存する必要があり、どのようにこれを達成するか分かりません。 1つの要素だけが変更された場合、ツリー全体を保存したくありません。最善の方法は何ですか？フラットファイル/ SQL/NoSqls/voodoos？

Answer 1

リレーショナルデータベースの使用は実行可能なソリューションです。ニーズのために - 高速挿入、更新、削除 - 私は、次のような追加のカスタマイズと隣接リストを使用したい：

id 
parent_id 
cardinality -- sort order for all nodes with the same parent_id 
depth -- distance from the root node 

cardinalityとdepthを計算するコードで行うか、されるか - 好ましくは - すべてのためのデータベース・トリガーを挿入、削除、または更新できます。さらに、1つのSELECT文で階層全体を検索するため、階層ブリッジテーブルが呼び出される：

id 
descendent_id 

この表はまた、上記と同じトリガーを介して移入されると、上記のすべてのノードを検索するための手段としてまたはidの下に表示されます。

See this question for additional detail around Adjacency List, Hierarchy Bridge and other approaches for storing hierarchical data in a relational database。

は、最後にあなたが記載されているオプションにいくつかの追加の明確化を提供します

• フラット・ファイル：リンクされたリストとメモリの組み合わせは、ファイルはおそらく役立つであろうマッピングされたが、あなたは本当にただであなた自身の圧延していますその点では、SQLまたはNoSQLソリューションがおそらく良くなるでしょう。
• SQL：これは私のアプローチです。ツールは、データの操作、バックアップ、リカバリに最適です。
  • ：ベンダー固有のデータベースでも可能ですが、ノードの挿入、更新、削除の構文を調べる必要があります。データベースがXMLデータ型を提供する場合、非常に高速になります。
• のNoSQL：あなたはtypical approach for hierarchical data appears to be materialized pathkey-value storageを、話しているが、これはおそらく遅い変更の影響を受けるすべてのノードのためのパス全体を再計算が必要になります。代わりにJava Content Repository（JCR）を考えてください。Apache Jackrabbitはインプリメンテーションです。階層構造のデータを表現し、永続化することを中心としたAPI全体です。解決しようとしている問題に対してはおそらく重すぎます。
• ブードゥー教：ええと...

更新

追加、この回答からすべてのピースを実装するた場合は、再ソート、安価で小型のコストで、動きは高価です。トレードオフは、高速な階層トラバーサル読み取りです。たとえば、1回の操作でノードの完全な祖先を見つけることができます。具体的には、リーフを追加するのはO（1）操作です。再ソートとは、移動したノードの後に​​来るすべてのピアノードを更新することを意味します。移動とは、（2）移動 - および子孫ノードの深さ、および（3）階層ブリッジテーブルへの祖先の除去および追加の後に来るソースおよび宛先ピアノードの（1）基数の更新を意味する。

しかし、Adjancency Listだけでは（つまりid, parent_id）、書き込みが安くなり、1レベルの読み取りは安いが、階層を走査する読み取りは高価になる。後者の場合、SQL Serverやその他のRDBMSにあるようなOracleのCONNECT BYやCommon Table Expressionsなどの再帰的なSQLを使用する必要があります。

Answer 2

リスト（またはツリー）を保存し、ツリー全体が変更されるとツリー全体を書き換えたくありません。これから私は構造が巨大であり、小さな変化が比較的頻繁に起こると結論づけます。

リンクされたリストはすべてポインタの追跡に関するもので、ポインタとその参照はキーと値によく似ています。キーと値のペアを効率的に格納する必要があります。アイテムの順序は、リンクされたリスト構造によって保持されます。

現代的なNoSQL製品のいずれかに、xDBMまたはBerkeley DBの典型的なキー値ストアを使用するとします。コンパクトなSQLエンジンを使用することもできます。 sqlite。彼らは通常、キーを索引付けするためにツリーを使用します。したがって、キーにアクセスするにはO（logN）が必要です。

データを段階的に保持する場合は指定していません。 1度に1回しか実行しない場合（すべての更新ではなく）、データベースを効果的にプライマリデータ構造と比較する必要があります。これは、ツリー全体を走査し、データベース内の各ノードIDを調べる必要があるため、比較的時間がかかります。これは対数ですが、必要なI/Oのために巨大な定数があります。そして、あなたは、もはや参照されていないアイテムから永続ストアをきれいにしたいでしょう。 JSONとしてツリーをダンプするだけではるかに効率的です。実際には、それが多くのメモリ内データベースで行われています。

主構造に対するすべての更新で永続構造を更新する場合、その主構造を持つ必要はありません。永続化メカニズム（および他の素敵なもの）を既に持っているRedisのようなメモリ内のキー値ストアで置き換える方が良いです。