Rubyでのツリーデータ構造の永続化

Question

Rubyに大きなデータツリーを構築して格納する必要があるプロジェクトがあります。シリアライゼーション、デシリアライゼーション、ツリーのクエリなど、さまざまなアプローチを検討していますが、何が最善の方法になるのだろうかと思っています。私の主な制約は、読み取り時間、クエリの効率性、およびクロスバージョン/クロスプラットフォームの互換性です。最も頻繁な操作は、id/valueおよび/またはfeatureの組み合わせに基づいてノードのセットを検索することです。ツリーは、最大15〜20レベルの深さにすることができます。サブツリーを移動することは珍しいことですが、あまりにも多くの黒い魔法がなければ可能です。 Railsの統合は主要な関心事ではありません。以下の通り、私は心配ですいくつかの問題と一緒に私が考えたオプション、：

• 元帥木々、そして時に必要なメモリにロードし、木の成長に合わせてルビー（非効率でそれらを照会し、クロスバージョン互換性？
• YAMLを使用します（より多くのバージョン間互換性がありますが、効率が悪いです）
• 上記と同じですが、カスタムXMLパーサーを使用します（ツリーごとにオブジェクトをゼロから再作成する必要がありますロードされていますか？）
• ツリーをXMLにシリアル化し、XMLデータベース（Sednaなど）に格納し、XPathを使用してツリーをクエリします（このアプローチの経験はありません）。 h）、
• スキーマレスデータベースに格納されているツリーをクエリするために隣接リストを使用する（子孫を数えると効率が悪い）
• ディープツリーの最大文字列長をオーバーフィルする可能性がありますか？
• ネストされたセットを使用する（複雑なSQLクエリ？）
• array of ancestorsアプローチを使用しますか？ MongoDBのページに基づいて効率を照会するという面では面白いようですが、私はこのアルゴリズムの真剣な議論を見つけることができませんでした。

あなたの経験に基づいて、どのアプローチが私が記述した制約に適合するでしょうか？私がXMLデータベースを探しているなら、このプロジェクトに適したものはありますか？私が見過ごした他のアプローチはより効率的でしょうか？御時間ありがとうございます。

Answer 1

木は、のNeo4jのようなグラフのデータベースと実際にうまく機能：http://neo4j.org/learn/

のNeo4jグラフのノードとの関係のデータを記憶し、グラフデータベースです。最も一般的なデータ構造であるグラフは、あらゆる種類のデータをエレガントに表現し、ドメインの自然な構造を保持します。 https://github.com/andreasronge/neo4j

ペーサーは非常に表情豊かなグラフトラバーサルを可能にJRubyのライブラリです：

Rubyは木のための良好な界面を持っています。 Pacerでは、非常に高速かつメモリ効率の高いストリーム処理を使用して、グラフの作成、変更、およびトラバースが可能です。つまり、ほとんどすべての処理が純粋なJavaで行われるということです。通常のRubyの表現力対速度の問題になると、ケーキを食べて食べることができます。それは非常に高速です！

https://github.com/pangloss/pacer

Neography我々はノードを格納し、良い結果を経験したneo4j.rb宝石のようなもので、コメントでロンによって提案された私の仕事上の（感謝ロン！）

https://github.com/maxdemarzi/neography

Answer 2

あなたはancestry gemを見ましたか？私は単純な木のためにそれを使用しましたが、説明によってあなたの要求に合っているように見えます。

Answer 3

SQLのアプローチを検討しているので、ここでいくつか考えてみましょう。

まず、木の大きさはどれくらいですか？多くのアプリケーションでは、10,000のリーフが大きく見えるでしょう。しかしこれはデータベースにとっては小さいです。まともなデータベースシステム（ラップトップのような）では、数千から数百万の葉をメモリに保存することができます。データベースは、他のアプローチの上にあなたを買う何

は次のとおりです。

- メモリ/ディスクのパフォーマンスを気にすることはありません。データがディスクに流出すると、パフォーマンスに大きな影響を与えません。比較すると、ハッシュテーブルがメモリをオーバーフローしたときに何が起こるかを考えてください。

- インデックスを追加してパフォーマンスを最適化できること。 、： -

SQLに標準SQLに問題の

一つを変更することで、ツリー「だけ」のためのあなたのアクセス・パスを変更できることは、あなたが簡単なペアとしてツリーノードを表すことができるということです。次に、単純な結合で、親と葉の間を移動できます。ただし、ツリーの上に移動すると結合が累積します。

Sigh。異なるデータベースには、これに対するさまざまな解決策があります。 SQL Serverには再帰的なCTEがあり、ツリーをトラバースすることができます。 Oracleにはツリー構造の別のアプローチがあります。

これは複雑になり始めます。

もっと良いアプローチは、ツリー内の階層に基づいて「リーフ」IDを割り当てることです。したがって、これがバイナリツリーの場合、 "10011"は右ブランチ、左ブランチ、左ブランチ、右ブランチ、右ブランチのノードになります。そこに情報を保管します。 。 。子どもがいるかどうか、何か他のものがあるかどうかなど。親を取得するのは簡単です。最後の桁を切り捨てるだけでよいからです。

これが非バイナリツリーにどのように一般化されるかを見ることができます。任意の数の子供を持つことは少し挑戦をもたらす可能性があります。

私はこれが "祖先の配列"アプローチに関係していると思います。

私はそれについて考えると、これはかなりうまくいくと思います。私は、あなたが欲しいアクションごとに別々のストアドプロシージャを定義することを示唆している：

usp_tree_FetchNode（NODEID） usp_tree_GetParent（NODEID） usp_tree_NodeDelete（NODEID） usp_tree_FetchSubTree（NODEID） などなどなど

SQLは実際にオブジェクト指向プログラミングをサポートしていませんが、クリーンな命名規則と優れた関数ラッパーを使用してコードを編成できます。

実際にはこれがうまくいくと思いますし、コードを開発するにはかなり良い方法です。優れた副作用の1つは、アプリケーション外のツリーを分析できることで、将来の拡張が示唆される可能性があります。