ツリー構造

based on v21 (2010-10-03更新) - オリジナル

パターン

一つのドキュメントにすべてのツリー構造を入れる
親へのリンクを持つ
子へのリンクを持つ
先祖を配列で持つ
Materialized Paths (それぞれのノードにすべての経路を持つ)
acts_as_nested_set

参照

ツリー構造をどう保存するのがいいのかというのは、どういう操作を実行したいのかということによって変わってきます。下記の色々な方法を参考にしてください。実際には、多くの開発者は、"一つのドキュメントにすべてのツリー構造を入れる"、"親へのリンクを持つ"、"先祖を配列で持つ"のパターンのどれかを選びます。

パターン

一つのドキュメントにすべてのツリー構造を入れる

{
  comments: [
    {by: "mathias", text: "...", replies: []}
    {by: "eliot", text: "...", replies: [
      {by: "mike", text: "...", replies: []}
    ]}
  ]
}

利点:

1ページをフェッチするために1つのドキュメントで済む
すべてのツリーがディスクの一箇所に配置される
すべての構造を簡単に見ることができる

欠点:

検索が大変
部分的な結果を取得するのが大変
巨大なツリーを扱いづらい (1ドキュメントには4MBの制限があります)

親へのリンクを持つ

親へのidを持つようなノードを、1つのコレクションに入れる単純なソリューションです。この方法の最大の問題は、すべてのサブツリーを取得するのにはデータベースと何度もやりとりをする必要があることです(または db.eval を使う)。

> t = db.tree1;

> t.find()
{ "_id" : 1 }
{ "_id" : 2, "parent" : 1 }
{ "_id" : 3, "parent" : 1 }
{ "_id" : 4, "parent" : 2 }
{ "_id" : 5, "parent" : 4 }
{ "_id" : 6, "parent" : 4 }

> // find children of node 4
> t.ensureIndex({parent:1})
> t.find( {parent : 4 } )
{ "_id" : 5, "parent" : 4 }
{ "_id" : 6, "parent" : 4 }

子へのリンクを持つ

もう一つのオプションは、ドキュメントのそれぞれのノードの中にすべての子のidを保存する方法です。この方法は、制限がありますが、サブツリー全体に対する処理が必要ではない場合には有効です。また、ノードが複数の親を持つようなグラフを保存するのにも向いています。

> t = db.tree2
> t.find()
{ "_id" : 1, "children" : [ 2, 3 ] }
{ "_id" : 2 }
{ "_id" : 3, "children" : [ 4 ] }
{ "_id" : 4 }

> // ノード3の子をすべて取得
> t.findOne({_id:3}).children
[ 4 ]

> // ノード3の親を取得
> t.ensureIndex({children:1})
> t.find({children:3})
{ "_id" : 1, "children" : [ 2, 3 ] }

先祖を配列で持つ

ノードに対するすべての親(先祖)を配列で持ちます。これは、"xに対するすべての子孫を取得"のような処理を速く簡単にできます。

> t = db.mytree;

> t.find()
{ "_id" : "a" }
{ "_id" : "b", "ancestors" : [ "a" ], "parent" : "a" }
{ "_id" : "c", "ancestors" : [ "a", "b" ], "parent" : "b" }
{ "_id" : "d", "ancestors" : [ "a", "b" ], "parent" : "b" }
{ "_id" : "e", "ancestors" : [ "a" ], "parent" : "a" }
{ "_id" : "f", "ancestors" : [ "a", "e" ], "parent" : "e" }
{ "_id" : "g", "ancestors" : [ "a", "b", "d" ], "parent" : "d" }

> t.ensureIndex( { ancestors : 1 } )

> // bのすべての子孫を取得
> t.find( { ancestors : 'b' })
{ "_id" : "c", "ancestors" : [ "a", "b" ], "parent" : "b" }
{ "_id" : "d", "ancestors" : [ "a", "b" ], "parent" : "b" }
{ "_id" : "g", "ancestors" : [ "a", "b", "d" ], "parent" : "d" }

> // fのすべての先祖を取得
> anc = db.mytree.findOne({_id:'f'}).ancestors
[ "a", "e" ]
> db.mytree.find( { _id : { $in : anc } } )
{ "_id" : "a" }
{ "_id" : "e", "ancestors" : [ "a" ], "parent" : "a" }

ensureIndex と multikey 機能で上記のクエリーを効率的に実行できます。

先祖に対する配列に加えて、ノードの直接の親を必要に応じて簡単に見つけられるように、ノードの直接の親も保存しています。

Materialized Paths (それぞれのノードにすべての経路を持つ)

Materialized paths を使うと、ツリー構造に対するクエリーを簡単にできます。それぞれのノードの中にツリー構造内でのドキュメントの位置の完全な経路を保存します。通常は、上記の"先祖に対する配列"の手法が、同じような動作をする上に、文字列の構築、正規表現、文字のエスケープをする必要がないので簡単です。 (ただし、理論的には、Materialized paths の方が わずかに 速いです)

MongoDBでこれを行う最良の方法は、文字列として経路を保存し、正規表現のクエリーを使うことです。 "^"で始まる単純な正規表現は効率的に実行されます。経路は文字列なので、区切り文字を使う必要があります。ここでは、 ',' を使います。例、

> t = db.tree
test.tree

> // すべてのツリーを取得。順序を正しくするためsort()を使います。
> t.find().sort({path:1})
{ "_id" : "a", "path" : "a," }
{ "_id" : "b", "path" : "a,b," }
{ "_id" : "c", "path" : "a,b,c," }
{ "_id" : "d", "path" : "a,b,d," }
{ "_id" : "g", "path" : "a,b,g," }
{ "_id" : "e", "path" : "a,e," }
{ "_id" : "f", "path" : "a,e,f," }
{ "_id" : "g", "path" : "a,b,g," }

> t.ensureIndex( {path:1} )

> // node 'b' とすべての子孫を取得します
> t.find( { path : /^a,b,/ } )
{ "_id" : "b", "path" : "a,b," }
{ "_id" : "c", "path" : "a,b,c," }
{ "_id" : "d", "path" : "a,b,d," }
{ "_id" : "g", "path" : "a,b,g," }

// 経路がわからない場合には、
> b = t.findOne( { _id : "b" } )
{ "_id" : "b", "path" : "a,b," }
> t.find( { path : new RegExp("^" + b.path) } )
{ "_id" : "b", "path" : "a,b," }
{ "_id" : "c", "path" : "a,b,c," }
{ "_id" : "d", "path" : "a,b,d," }
{ "_id" : "g", "path" : "a,b,g," }

Rubyでの例: http://github.com/banker/newsmonger/blob/master/app/models/comment.rb

acts_as_nested_set

http://api.rubyonrails.org/classes/ActiveRecord/Acts/NestedSet/ClassMethods.html を参照してください。

この方法は、変更が発生すると多くのドキュメントに対して更新を要求するので、滅多に変更がないデータに対して有効です。

参照

Sean Cribbs blog post (source of several ideas on this page).