Trees in MongoDB

Trees in mongodbPosted on 引用地址：%20in%20MongoDB.html 樹結(jié)構(gòu)存儲(chǔ)最好的方式常常依賴于要執(zhí)行的操作；下面討論一下不同的存儲(chǔ)方案。在實(shí)踐中，許多開發(fā)人員找到了一些使用起來很方便的模式：?jiǎn)挝臋n存儲(chǔ)整根樹(Full Tree in single Document)，父連接(P

Trees in MongoDB Posted on

引用地址：%20in%20mongodb.html

?

樹結(jié)構(gòu)存儲(chǔ)最好的方式常常依賴于要執(zhí)行的操作；下面討論一下不同的存儲(chǔ)方案。在實(shí)踐中，許多開發(fā)人員找到了一些使用起來很方便的模式：“單文檔存儲(chǔ)整根樹(Full Tree in single Document)”，“父連接(Parent Links)”和“祖先數(shù)組(Array of Ancestors)”。

1???????? 模式 1.1?????? 單文檔存儲(chǔ)整根樹(Full Tree in Signle Document)

{

? comments: [

??? {by: “mathias”, text: “…”, replies: []}

??? {by: “eliot”, text: “…”, replies: [

????? {by: “mike”, text: “…”, replies: []}

??? ]}

? ]

}

優(yōu)點(diǎn)：

缺點(diǎn)：

1.2?????? (父連接)Parent Links

用單個(gè)集合來存儲(chǔ)所有節(jié)點(diǎn)，服務(wù)器空間，每個(gè)節(jié)點(diǎn)包含他父節(jié)點(diǎn)的ID，是一種簡(jiǎn)單的解決方案。這種方法最大的問題是獲取完整子樹時(shí)需要查找多次數(shù)據(jù)庫(kù)（或使用db.eval函數(shù)）。

> 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 } 1.3?????? (子鏈接)Child Links

另一種選擇是在每個(gè)節(jié)點(diǎn)文檔中存儲(chǔ)所有子節(jié)點(diǎn)的ID。這個(gè)方法是有限制的，如果不操作完整子樹是沒有問題。他可能也是用于存儲(chǔ)一個(gè)節(jié)點(diǎn)有多個(gè)父節(jié)點(diǎn)情況的最有效方法。

> t = db.tree2 > t.find() { “_id” : 1, “children” : [ 2, 3 ] } { “_id” : 2 } { “_id” : 3, “children” : [ 4 ] } { “_id” : 4 } ? > // find immediate children of node 3 > t.findOne({_id:3}).children [ 4 ] ? > // find immediate parent of node 3 > t.ensureIndex({children:1}) > t.find({children:3}) { “_id” : 1, “children” : [ 2, 3 ] } 1.4?????? (祖先數(shù)組)Array of Ancestors

在這種方法中將一個(gè)節(jié)點(diǎn)的所有祖先節(jié)點(diǎn)存儲(chǔ)到一個(gè)數(shù)組中。這使得類似于“獲取X節(jié)點(diǎn)的所有子節(jié)點(diǎn)”的操作快且容易。

> 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 } ) ? > // find all descendents of 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” } ? > // get all ancestors of 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和MongoDB的multikey特性可以使上面的查詢更高效。

??????????????? 除了祖先數(shù)組，我們也存儲(chǔ)了節(jié)點(diǎn)的直接父節(jié)點(diǎn)，使得查找節(jié)點(diǎn)的直接父節(jié)點(diǎn)更容易。

1.5?????? 物化路徑(Materialized Path[Full Path in Each Node))

物化路徑使得對(duì)樹的特定查詢?nèi)菀住Ｎ覀冊(cè)诿總€(gè)節(jié)點(diǎn)中存儲(chǔ)文檔在樹中位置的全路徑。通常情況下上面提到的“祖先數(shù)組”方法都工作很好；當(dāng)不得不處理字符串建造、正則表達(dá)式，字符逃逸，物化路徑更容易。（理論上，物化路徑將會(huì)更快。）

MongoDB實(shí)現(xiàn)物化路徑最好的方式是將路徑存儲(chǔ)成字符串，然后采用正則表達(dá)式查詢。以“^”開頭的正則表達(dá)可以被高效執(zhí)行。把數(shù)據(jù)看作一個(gè)字符串，你需要選擇一個(gè)分隔符，我們采用“,”。舉例：

> t = db.tree test.tree ? > // get entire tree — we use sort() to make the order nice > 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} ) ? > // find the node ‘b’ and all its descendents: > 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,” } ? > // find the node ‘b’ and its descendents, where path to ‘b’ is not already known: > nodeb = t.findOne( { _id : “b” } ) { “_id” : “b”, “path” : “a,b,” } > t.find( { path : new RegExp(“^” + nodeb.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實(shí)例：

嵌套數(shù)據(jù)集：