使用 MongoDB 存储类似树的层级结构，第二部分
4.43/5 (5投票s)
存储类似树的结构的三个方法，
引言
在现实生活中，几乎任何项目都涉及树状结构。各种分类法、站点结构等都需要模拟层级关系。在本文中，我将以 MongoDB 数据库为例，演示五种典型处理层级数据的第五和第六种方法。请参考系列的第一篇文章，了解前三种方法。这些方法是
- 使用子节点引用建模树结构
- 使用父节点引用建模树结构
- 使用祖先节点数组建模树结构
- 使用物化路径建模树结构
- 使用嵌套集建模树结构
注意：本文的灵感来自于 10gen 的另一篇文章《在 MongoDB 中建模树结构》，但并非抄袭，而是提供了关于树管理典型操作的额外示例。请参考 10gen 的文章以更深入地理解该方法。
背景
作为演示数据集，我使用了一个虚构的电子商店商品分类。
需要解决的挑战
在典型的网站场景中，我们应该能够
- 操作树（在特定父节点下插入新节点、更新/删除现有节点、将节点移动到树的其他位置）
- 获取节点的路径（例如，用于构建面包屑导航）
- 获取节点的所有后代（例如，以便选择更通用类别的商品，如“手机及配件”，其中应包含所有子类别下的商品。
在下面的每个示例中，我们将
- 在 electronics（电子产品）下添加一个名为 'LG' 的新节点
- 将 'LG' 节点移动到 Cell_Phones_And_Smartphones（手机及智能手机）节点下
- 从树中删除 'LG' 节点
- 获取 Electronics（电子产品）节点的子节点
- 获取 'Nokia' 节点的路径
- 获取 'Cell_Phones_and_Accessories'（手机及配件）节点的所有后代
请参考上图以获得视觉表示。
使用物化路径的树结构
对于每个节点，我们存储 (ID, PathToNode)
这种方法与存储祖先节点数组类似，但我们存储的是 string 格式的路径。在上面的示例中，我特意使用逗号(,)作为路径元素分隔符，以便使正则表达式更简单。
添加新节点
新节点的插入通过一次 select 和一次 insert 操作完成。
var ancestorpath = db.categoriesMP.findOne({_id:'Electronics'}).path;
ancestorpath += 'Electronics,'
db.categoriesMP.insert({_id:'LG', path:ancestorpath});
//{ "_id" : "LG", "path" : "Electronics," }
更新/移动节点
节点可以使用一次 select 和一次 update 操作进行移动。
ancestorpath = db.categoriesMP.findOne({_id:'Cell_Phones_and_Smartphones'}).path;
ancestorpath +='Cell_Phones_and_Smartphones,'
db.categoriesMP.update({_id:'LG'},{$set:{path:ancestorpath}});
//{ "_id" : "LG", "path" : "Electronics,Cell_Phones_and_Accessories,
//Cell_Phones_and_Smartphones," }
删除节点
节点可以使用单个数据库查询进行删除
db.categoriesMP.remove({_id:'LG'});
获取节点子节点（无序）
请注意，除非您添加一个排序字段，否则无法获得有序的子节点列表。如果需要顺序，您应该考虑其他方法。
db.categoriesMP.find({$query:{path:'Electronics,'}})
//{ "_id" : "Cameras_and_Photography", "path" : "Electronics," }
//{ "_id" : "Shop_Top_Products", "path" : "Electronics," }
//{ "_id" : "Cell_Phones_and_Accessories", "path" : "Electronics," }
获取所有节点后代
单个 select，regexp 以 ^ 开头，允许使用索引进行匹配
var descendants=[]
var item = db.categoriesMP.findOne({_id:"Cell_Phones_and_Accessories"});
var criteria = '^'+item.path+item._id+',';
var children = db.categoriesMP.find({path: { $regex: criteria, $options: 'i' }});
while(true === children.hasNext()) {
var child = children.next();
descendants.push(child._id);
}
descendants.join(",")
//Cell_Phones_and_Smartphones,Headsets,Batteries,Cables_And_Adapters,
//Nokia,Samsung,Apple,HTC,Vyacheslav
获取节点路径
我们可以直接从节点获取路径，而无需执行额外的 select 查询。
var path=[]
var item = db.categoriesMP.findOne({_id:"Nokia"})
print (item.path)
//Electronics,Cell_Phones_and_Accessories,Cell_Phones_and_Smartphones,
索引
建议的索引是在 path 字段上建立索引
db.categoriesAAO.ensureIndex( { path: 1 } )
使用嵌套集的树结构
对于每个节点，我们存储 (ID, left, right)。
Left 字段也可以作为排序字段。
添加新节点
请参考上图。假设我们要将 LG 节点插入到 shop_top_products(14,23) 之后。
新节点的 left 值将是 24，根据遍历规则影响所有剩余的 left 值，right 值将是 25，影响包括根节点在内的所有剩余 right 值。
步骤
- 考虑遍历树中的下一个节点。
- 新节点的 left 值将是其下一个同级节点的值，right 值将是下一个同级节点 left 值加二。
- 现在，我们必须为新节点腾出空间。更新操作会影响所有祖先节点的 right 值，也会影响遍历中剩余的所有节点。
- 只有在腾出空间后，才能插入新节点。
var followingsibling = db.categoriesNSO.findOne({_id:"Cell_Phones_and_Accessories"});
var newnode = {_id:'LG', left:followingsibling.left,right:followingsibling.left+1}
db.categoriesNSO.update({right:{$gt:followingsibling.right}},{$inc:{right:2}}, false, true)
db.categoriesNSO.update({left:{$gte:followingsibling.left},
right:{$lte:followingsibling.right}},{$inc:{left:2, right:2}}, false, true)
db.categoriesNSO.insert(newnode)
让我们检查一下结果。
+-Electronics (1,46)
+---Cameras_and_Photography (2,13)
+------Digital_Cameras (3,4)
+------Camcorders (5,6)
+------Lenses_and_Filters (7,8)
+------Tripods_and_supports (9,10)
+------Lighting_and_studio (11,12)
+----Shop_Top_Products (14,23)
+------IPad (15,16)
+------IPhone (17,18)
+------IPod (19,20)
+------Blackberry (21,22)
+----LG (24,25)
+----Cell_Phones_and_Accessories (26,45)
+------Cell_Phones_and_Smartphones (27,38)
+---------Nokia (28,29)
+---------Samsung (30,31)
+---------Apple (32,33)
+---------HTC (34,35)
+---------Vyacheslav (36,37)
+-------Headsets (39,40)
+-------Batteries (41,42)
+-------Cables_And_Adapters (43,44)
删除节点
虽然在同一父节点下重新排列节点顺序与交换节点的 left 和 right 值是相同的，但正式的移动节点的方法是先从树中删除节点，然后再将其插入到新位置。注意：不移除子节点的节点删除在此文章范围内不讨论。目前，我们假设要删除的节点没有子节点，即 right-left=1。
步骤与添加节点相同 - 即，我们通过减小受影响的 left/right 值来调整空间，
然后删除原始节点。
var nodetoremove = db.categoriesNSO.findOne({_id:"LG"});
if((nodetoremove.right-nodetoremove.left-1)>0.001) {
print("Only node without childs can be removed")
exit
}
var followingsibling = db.categoriesNSO.findOne({_id:"Cell_Phones_and_Accessories"});
//update all remaining nodes
db.categoriesNSO.update({right:{$gt:nodetoremove.right}},{$inc:{right:-2}}, false, true)
db.categoriesNSO.update({left:{$gt:nodetoremove.right}},{$inc:{left:-2}}, false, true)
db.categoriesNSO.remove({_id:"LG"});
让我们检查一下结果。
+-Electronics (1,44)
+--Cameras_and_Photography (2,13)
+-----Digital_Cameras (3,4)
+-----Camcorders (5,6)
+-----Lenses_and_Filters (7,8)
+-----Tripods_and_supports (9,10)
+-----Lighting_and_studio (11,12)
+---Shop_Top_Products (14,23)
+-----IPad (15,16)
+-----IPhone (17,18)
+-----IPod (19,20)
+-----Blackberry (21,22)
+---Cell_Phones_and_Accessories (24,43)
+-----Cell_Phones_and_Smartphones (25,36)
+--------Nokia (26,27)
+--------Samsung (28,29)
+--------Apple (30,31)
+--------HTC (32,33)
+--------Vyacheslav (34,35)
+------Headsets (37,38)
+------Batteries (39,40)
+------Cables_And_Adapters (41,42)
更新/移动单个节点
节点移动可以是同一父节点内，也可以是移动到另一个父节点。如果是同一父节点且节点没有子节点，那么您只需要交换节点的 (left, right) 对。
正式的方法是删除节点并将其插入到新的目标位置，因此限制条件相同 - 只能移动没有子节点的节点。如果您需要移动子树，请考虑在新的位置下创建现有父节点的镜像，然后逐个移动节点到新父节点下。一旦所有节点都已移动，就删除过时的旧父节点。
例如，让我们将 LG 节点从插入示例中移动到 Cell_Phones_and_Smartphones 节点下，作为最后一个同级节点（即，没有下一个同级节点，如插入示例）。
步骤
- 使用上述节点删除过程从树中删除 LG 节点
- 获取新父节点的 right 值。新节点的 left 值将是父节点的 right 值，right 值将是父节点的 right 值加一。现在我们必须为新节点腾出空间：更新操作会影响进一步遍历路径上所有节点的 right 值。
var newparent = db.categoriesNSO.findOne({_id:"Cell_Phones_and_Smartphones"});
var nodetomove = {_id:'LG', left:newparent.right,right:newparent.right+1}
//3rd and 4th parameters: false stands for upsert=false and true stands for multi=true
db.categoriesNSO.update({right:{$gte:newparent.right}},{$inc:{right:2}}, false, true)
db.categoriesNSO.update({left:{$gte:newparent.right}},{$inc:{left:2}}, false, true)
db.categoriesNSO.insert(nodetomove)
让我们检查一下结果。
+-Electronics (1,46)
+--Cameras_and_Photography (2,13)
+-----Digital_Cameras (3,4)
+-----Camcorders (5,6)
+-----Lenses_and_Filters (7,8)
+-----Tripods_and_supports (9,10)
+-----Lighting_and_studio (11,12)
+---Shop_Top_Products (14,23)
+-----IPad (15,16)
+-----IPhone (17,18)
+-----IPod (19,20)
+-----Blackberry (21,22)
+---Cell_Phones_and_Accessories (24,45)
+-----Cell_Phones_and_Smartphones (25,38)
+---------Nokia (26,27)
+---------Samsung (28,29)
+---------Apple (30,31)
+---------HTC (32,33)
+---------Vyacheslav (34,35)
+---------LG (36,37)
+-------Headsets (39,40)
+-------Batteries (41,42)
+-------Cables_And_Adapters (43,44)
获取所有节点后代
这是该方法的优势所在 - 所有后代节点都可以通过一次数据库 select 查询检索。此外，通过按节点 left 值排序，数据集就可以按正确的顺序进行遍历。
var descendants=[]
var item = db.categoriesNSO.findOne({_id:"Cell_Phones_and_Accessories"});
print ('('+item.left+','+item.right+')')
var children = db.categoriesNSO.find({left:{$gt:item.left},
right:{$lt:item.right}}).sort(left:1);
while(true === children.hasNext()) {
var child = children.next();
descendants.push(child._id);
}
descendants.join(",")
//Cell_Phones_and_Smartphones,Headsets,Batteries,Cables_And_Adapters,
//Nokia,Samsung,Apple,HTC,Vyacheslav
获取节点路径
检索节点路径也非常简洁，并且可以通过单个数据库查询完成。
var path=[]
var item = db.categoriesNSO.findOne({_id:"Nokia"})
var ancestors = db.categoriesNSO.find({left:{$lt:item.left},
right:{$gt:item.right}}).sort({left:1})
while(true === ancestors.hasNext()) {
var child = ancestors.next();
path.push(child._id);
}
path.join('/')
// Electronics/Cell_Phones_and_Accessories/Cell_Phones_and_Smartphones
索引
建议的索引是在 left 和 right 值上建立索引。
db.categoriesAAO.ensureIndex( { left: 1, right:1 } )
如果您有耐心读到这里，还有一个奖励。
结合使用嵌套集和经典的父节点引用（带顺序）方法的树结构
对于每个节点，我们存储 (ID, Parent, Order, left, right)。
Left 字段也作为排序字段，因此我们可以省略 Order 字段。但另一方面，
我们可以保留它，这样在出现意外损坏时，或者例如在初始导入期间，可以使用 Parent Reference 和 Order 数据来重建 left/right 值。
添加新节点
可以通过这种方式采用嵌套集的方法来添加新节点。
var followingsibling = db.categoriesNSO.findOne({_id:"Cell_Phones_and_Accessories"});
var previoussignling = db.categoriesNSO.findOne({_id:"Shop_Top_Products"});
var neworder = parseInt((followingsibling.order + previoussignling.order)/2);
var newnode = {_id:'LG', left:followingsibling.left,
right:followingsibling.left+1, parent:followingsibling.parent, order:neworder};
db.categoriesNSO.update({right:{$gt:followingsibling.right}},{$inc:{right:2}}, false, true)
db.categoriesNSO.update({left:{$gte:followingsibling.left},
right:{$lte:followingsibling.right}},{$inc:{left:2, right:2}}, false, true)
db.categoriesNSO.insert(newnode)
插入前
+----Cameras_and_Photography (2,13) ord.[10]
+-----Shop_Top_Products (14,23) ord.[20]
+-----Cell_Phones_and_Accessories (26,45) ord.[30]
插入后
+--Electronics (1,46)
+----Cameras_and_Photography (2,13) ord.[10]
+-------Digital_Cameras (3,4) ord.[10]
+-------Camcorders (5,6) ord.[20]
+-------Lenses_and_Filters (7,8) ord.[30]
+-------Tripods_and_supports (9,10) ord.[40]
+-------Lighting_and_studio (11,12) ord.[50]
+-----Shop_Top_Products (14,23) ord.[20]
+-------IPad (15,16) ord.[10]
+-------IPhone (17,18) ord.[20]
+-------IPod (19,20) ord.[30]
+-------Blackberry (21,22) ord.[40]
+-----LG (24,25) ord.[25]
+-----Cell_Phones_and_Accessories (26,45) ord.[30]
+-------Cell_Phones_and_Smartphones (27,38) ord.[10]
+----------Nokia (28,29) ord.[10]
+----------Samsung (30,31) ord.[20]
+----------Apple (32,33) ord.[30]
+----------HTC (34,35) ord.[40]
+----------Vyacheslav (36,37) ord.[50]
+--------Headsets (39,40) ord.[20]
+--------Batteries (41,42) ord.[30]
+--------Cables_And_Adapters (43,44) ord.[40]
更新/移动单个节点
与插入方法相同。
删除节点
使用了嵌套集的方法。
获取节点子节点（有序）
现在可以通过 (Parent, Order) 对来实现
db.categoriesNSO.find({parent:"Electronics"}).sort({order:1});
/*
{ "_id" : "Cameras_and_Photography", "parent" : "Electronics",
"order" : 10, "left" : 2, "right" : 13 }
{ "_id" : "Shop_Top_Products", "parent" : "Electronics",
"order" : 20, "left" : 14, "right" : 23 }
{ "_id" : "LG", "left" : 24, "right" : 25,
"parent" : "Electronics", "order" : 25 }
{ "_id" : "Cell_Phones_and_Accessories", "parent" : "Electronics",
"order" : 30, "left" : 26, "right" : 45 }
*/
获取所有节点后代
使用了嵌套集的方法。
获取节点路径
使用了嵌套集的方法。
代码示例
代码可以从仓库下载：https://github.com/Voronenko/Storing_TreeView_Structures_WithMongoDB。
所有文件都按照以下命名约定打包：
- MODELReference.js - 包含 MODEL 方法树数据的初始化文件
- MODELReference_operating.js - 添加/更新/移动/删除/获取子节点示例
- MODELReference_pathtonode.js - 说明如何获取节点路径的代码
- MODELReference_nodedescendants.js - 说明如何检索节点所有后代代码
所有文件都已准备好在 mongo shell 中使用。您可以通过调用 mongo < file_to_execute 来运行示例，或者，如果您愿意，也可以在 shell 中或使用 RockMongo 网页 shell 进行交互式操作。
历史
- 2013 年 1 月 6 日：初版