8

私は任意の木構造を持っています。

データ構造の例:

root
  |--node1
  |     |--node2
  |     |     |--leaf1
  |     |
  |     |--leaf2
  |
  |--node3
        |--leaf3

各ノードとリーフには、 と の 2 つのプロパティがidありnameます。

重要なクエリ:

1.:リーフ ID が与えられます。クエリは、ルートからそのリーフまでのパス全体を、すべてのノードidとnameプロパティとともに返す必要があります。

戻り値がノードの並べ替えられた配列であるか、ノードがネストされているオブジェクトであるかは重要ではありません。

例:id ofが指定されている場合leaf2、クエリは次を返す必要がありますroot(id, name), node1(id, name), leaf2(id, name)。

2.:与えられた任意のノードid: (サブ) ツリー全体を取得します。ここでは、各ノードがchildren配列を持つ単一のオブジェクトを取得すると便利です。

思考、試行錯誤:

1.:最初は単純にツリーを単一の JSON ドキュメントとしてモデル化しようとしましたが、そうするとクエリが不可能になり、リーフがどのネスト レベルにあるかを調べる方法がありません。また、ルートからリーフまでの s のパス全体がわかっている場合はid、複数の位置演算子を含むプロジェクションを使用する必要があり、現時点では MongoDB ではサポートされていません。idsさらに、ネストが無限になる可能性があるため、リーフにインデックスを付けることはできません。

2.:次のアイデアは、各ノードがノードの祖先を含む配列を持つフラットなデータ設計を使用することでしたids:

{
  id: ...,
  name: ...,
  ancestors: [ rootId, node1Id, ... ]
}

この方法では、ルートからノードまたはリーフまでのパス全体を取得するために、2 つのクエリを実行する必要があります。これは非常に優れています。

質問:

データ モデルを選択した場合2.: ツリー全体またはサブツリーを取得するにはどうすればよいですか?

すべての子孫を取得するのは簡単です: find({ancestors:"myStartingNodeId"}). しかし、それらはもちろんソートまたはネストされません。

この問題を解決するために、集計フレームワークまたはまったく異なるデータ モデルを使用する方法はありますか?

ありがとうございました！

4

3 に答える 3

4

これが私が最終的に思いついたデータ構造です。読み取りクエリ用に最適化されています。一部の書き込みクエリ (サブツリーの移動など) は面倒な場合があります。

{
  id: "...",
  ancestors: ["parent_node_id", ..., "root_node_id"], // order is important!
  children: ["child1_id", "child2_id", ...]
}

利点：

  • サブツリーのすべてのドキュメントを簡単に取得

  • あるノードからルートまでのすべてのドキュメントを簡単に取得できます

  • ドキュメントがノードの親/子/祖先/子孫であるかどうかを簡単に確認できます

  • 子供たちは分類されます。children配列の順序を変更することで簡単に移動できます

それの使い方：

  • ID で取得:findOne({ id: "..." })

  • 親を取得:findOne({ children: "..." })

  • すべての祖先を取得する: 最初にGet by IDを実行し、次に祖先配列を取得して、指定された ID リストに一致するすべてのドキュメントを探します。

  • すべての子を取得:find({ 'ancestors.0': "..." })

  • すべての子孫を取得します。find({ ancestors: "..." })

  • x世代までのすべての子孫を取得します。find({ $and: [ {ancestors: "..."}, {ancestors: {$size: x}} ] })

欠点:

  • アプリケーション コードは、正しい順序に注意する必要があります。

  • アプリケーション コードは、ネストされたオブジェクトを構築する必要があります (MongoDB Aggregation フレームワークを使用すると、おそらくこれが可能になります)。

  • すべてinsertは、2 つのクエリを使用して実行する必要があります。

  • ノード間でサブツリー全体を移動すると、多くのドキュメントを更新する必要があります。

于 2016-12-14T19:15:55.487 に答える
4

MongoDB はグラフ データベースではなく、グラフ トラバーサル操作を提供しないため、直接的な解決策はありません。

ポイント 2. (先祖リストを持つノード) で説明したデータ モデルを使用して、クエリfind({ancestors:"myStartingNodeId"})を実行し、アプリケーション コードで結果を並べ替え/ネストすることができます。

もう 1 つの可能性は、_id(または他のフィールド) がフル パスを表すデータ モデルを使用すること'root.node1.node2'です。次に、グラフクエリを部分文字列クエリに変換し、 this でソートするだけで正しい順序付けを実現できます (希望) _id。

更新：ところで。MongoDB のドキュメントで説明されているいくつかのツリー構造パターンがあります: MongoDB のモデル ツリー構造

于 2015-07-25T22:51:56.633 に答える