使用 MongoDB 存储类似树的层次结构

• 下载源码 - 214.7 KB

引言

在实际生活中，几乎任何项目都会处理树状结构。各种分类法、网站结构等都需要对层级关系进行建模。在本文中，我将通过 MongoDB 数据库的示例，介绍处理层级数据的五种典型方法中的前三种。这些方法是：

• 使用子节点引用建模树状结构
• 使用父节点引用建模树状结构
• 使用祖先节点数组建模树状结构
• 使用物化路径建模树状结构
• 使用嵌套集建模树状结构

注意：本文的灵感来自于 10gen 的另一篇文章《在 MongoDB 中建模树状结构》，但并非复制。它提供了关于树管理典型操作的额外示例。请参考 10gen 的文章以更深入地理解该方法。

背景

作为演示数据集，我使用了一些假的电子商店商品分类。

需要解决的挑战

在典型的网站场景中，我们应该能够：

• 操作树（在特定父节点下插入新节点、更新/删除现有节点、移动节点到树中的其他位置）
• 获取到节点的路径（例如，为了构建面包屑导航）
• 获取节点的所有后代（例如，为了选择更广泛类别下的商品，如“手机及配件”，其中应包含所有子类别下的商品。

在下面的每个示例中，我们都将：

• 在 electronics（电子产品）下添加一个名为 'LG' 的新节点
• 将 'LG' 节点移动到 Cell_Phones_And_Smartphones（手机及智能手机）节点下
• 从树中删除 'LG' 节点
• 获取 Electronics（电子产品）节点的子节点
• 获取 'Nokia' 节点的路径
• 获取 'Cell_Phones_and_Accessories'（手机及配件）节点的所有后代

请参考上图以获得视觉表示。

带父节点引用的树状结构

这是最常用的方法。对于每个节点，我们存储（ID，ParentReference，Order）。

树的操作

相当简单，但改变节点在同级节点中的位置需要额外的计算。您可能希望为 order 设置很大的数字，例如 item position * 10^6，以便能够将新节点顺序设置为截断（较低同级节点的 order - 较高同级节点的 order）/2 - 这将为您提供足够的空间，直到您需要遍历整个树并将 order 默认值再次设置为大数字。

添加新节点

优点：只需一次 insert 操作即可引入节点。

var existingelemscount = db.categoriesPCO.find({parent:'Electronics'}).count();
var neworder = (existingelemscount+1)*10;
db.categoriesPCO.insert({_id:'LG', parent:'Electronics', 
                         someadditionalattr:'test', order:neworder})
//{ "_id" : "LG", "parent" : "Electronics", 
//      "someadditionalattr" : "test", "order" : 40 } 

更新/移动节点

优点：与 insert 一样 - 只需一次 update 操作即可修改节点。

existingelemscount = db.categoriesPCO.find({parent:'Cell_Phones_and_Smartphones'}).count();
neworder = (existingelemscount+1)*10;
db.categoriesPCO.update({_id:'LG'},
{$set:{parent:'Cell_Phones_and_Smartphones', order:neworder}});
//{ "_id" : "LG", "order" : 60, "parent" : 
//          "Cell_Phones_and_Smartphones", "someadditionalattr" : "test" }  

节点删除

优点：只需一次操作即可从树中删除节点。

db.categoriesPCO.remove({_id:'LG'});  

获取排序后的节点子节点

优点：所有 childs（子节点）都可以通过一次调用从数据库检索并排序。

db.categoriesPCO.find({$query:{parent:'Electronics'}, $orderby:{order:1}})
//{ "_id" : "Cameras_and_Photography", "parent" : "Electronics", "order" : 10 }
//{ "_id" : "Shop_Top_Products", "parent" : "Electronics", "order" : 20 }
//{ "_id" : "Cell_Phones_and_Accessories", "parent" : "Electronics", "order" : 30 }

获取所有节点后代

缺点：不幸的是，需要递归调用数据库。

var descendants=[]
var stack=[];
var item = db.categoriesPCO.findOne({_id:"Cell_Phones_and_Accessories"});
stack.push(item);
while (stack.length>0){
    var currentnode = stack.pop();
    var children = db.categoriesPCO.find({parent:currentnode._id});
    while(true === children.hasNext()) {
        var child = children.next();
        descendants.push(child._id);
        stack.push(child);
    }
}

descendants.join(",")
//Cell_Phones_and_Smartphones,Headsets,Batteries,Cables_And_Adapters,
//Nokia,Samsung,Apple,HTC,Vyacheslav

获取节点路径

缺点：不幸的是，也需要递归操作才能获取路径。

var path=[]
var item = db.categoriesPCO.findOne({_id:"Nokia"})
while (item.parent !== null) {
    item=db.categoriesPCO.findOne({_id:item.parent});
    path.push(item._id);
}

path.reverse().join(' / ');
//Electronics / Cell_Phones_and_Accessories / Cell_Phones_and_Smartphones 

索引

建议索引字段为 parent 和 order。

db.categoriesPCO.ensureIndex( { parent: 1, order:1 } )  

带子节点引用的树状结构

对于每个节点，我们存储（ID，ChildReferences）。

请注意，在这种情况下，我们不需要 order 字段，因为 Childs（子节点）集合已经提供了此信息。大多数语言都尊重数组顺序。如果您的语言不尊重，您可能需要考虑额外的编码来保留顺序，但这会使事情变得更复杂。

添加新节点

注意：插入节点需要一次 insert 操作和一次更新操作。

db.categoriesCRO.insert({_id:'LG', childs:[]});
db.categoriesCRO.update({_id:'Electronics'},{  $addToSet:{childs:'LG'}});
//{ "_id" : "Electronics", "childs" : 
//[     "Cameras_and_Photography", "Shop_Top_Products", "Cell_Phones_and_Accessories", "LG" ] } 

更新/移动节点

更改同一父节点下的节点顺序需要一次更新操作，将节点移动到另一个父节点下需要两次更新操作。

在同一父节点下重新排列顺序

db.categoriesCRO.update({_id:'Electronics'},
{$set:{"childs.1":'LG',"childs.3":'Shop_Top_Products'}});
//{ "_id" : "Electronics", "childs" : 
//[     "Cameras_and_Photography",     "LG",     
//"Cell_Phones_and_Accessories",     "Shop_Top_Products" ] } 

移动节点

db.categoriesCRO.update({_id:'Cell_Phones_and_Smartphones'},{  $addToSet:{childs:'LG'}});
db.categoriesCRO.update({_id:'Electronics'},{$pull:{childs:'LG'}});
//{ "_id" : "Cell_Phones_and_Smartphones", 
//"childs" : [ "Nokia", "Samsung", "Apple", "HTC", "Vyacheslav", "LG" ] } 

节点删除

节点删除也需要两次操作：一次 update 和一次 remove。

db.categoriesCRO.update({_id:'Cell_Phones_and_Smartphones'},{$pull:{childs:'LG'}})
db.categoriesCRO.remove({_id:'LG'}); 

获取排序后的节点子节点

缺点：需要额外的客户端排序（按父数组序列）。取决于结果集，这可能会影响代码的速度。

var parent = db.categoriesCRO.findOne({_id:'Electronics'})
db.categoriesCRO.find({_id:{$in:parent.childs}}) 

结果集

{ "_id" : "Cameras_and_Photography", "childs" : [     "Digital_Cameras",     
"Camcorders",     "Lenses_and_Filters",     "Tripods_and_supports",     
"Lighting_and_studio" ] }
{ "_id" : "Cell_Phones_and_Accessories", "childs" : [     "Cell_Phones_and_Smartphones",
"Headsets",     "Batteries",     "Cables_And_Adapters" ] }
{ "_id" : "Shop_Top_Products", "childs" : [ "IPad", "IPhone", "IPod", "Blackberry" ] }

//parent:
{
    "_id" : "Electronics",
    "childs" : [
        "Cameras_and_Photography",
        "Cell_Phones_and_Accessories",
        "Shop_Top_Products"
    ]
} 

可以看到，我们有一个已排序的 childs 数组，可用于在客户端对结果集进行排序。

获取所有节点后代

注意：也需要递归操作，但与前一种方法相比，我们需要的数据库 select 更少。

var descendants=[]
var stack=[];
var item = db.categoriesCRO.findOne({_id:"Cell_Phones_and_Accessories"});
stack.push(item);
while (stack.length>0){
    var currentnode = stack.pop();
    var children = db.categoriesCRO.find({_id:{$in:currentnode.childs}});

    while(true === children.hasNext()) {
        var child = children.next();
        descendants.push(child._id);
        if(child.childs.length>0){
          stack.push(child);
        }
    }
}

//Batteries,Cables_And_Adapters,Cell_Phones_and_Smartphones,Headsets,Apple,HTC,Nokia,Samsung
descendants.join(",") 

获取节点路径

Path（路径）是递归计算的，因此我们需要向数据库发出连续的调用。

var path=[]
var item = db.categoriesCRO.findOne({_id:"Nokia"})
while ((item=db.categoriesCRO.findOne({childs:item._id}))) {
    path.push(item._id);
}

path.reverse().join(' / ');
//Electronics / Cell_Phones_and_Accessories / Cell_Phones_and_Smartphones 

索引

建议索引为 childs

db.categoriesCRO.ensureIndex( { childs: 1 } ) 

使用祖先节点数组的树状结构

对于每个节点，我们存储（ID，ParentReference，AncestorReferences）

添加新节点

您需要一次 insert 操作来引入新节点，但您需要调用 select 来准备 insert 的数据。

var ancestorpath = db.categoriesAAO.findOne({_id:'Electronics'}).ancestors;
ancestorpath.push('Electronics')
db.categoriesAAO.insert({_id:'LG', parent:'Electronics',ancestors:ancestorpath});
//{ "_id" : "LG", "parent" : "Electronics", "ancestors" : [ "Electronics" ] } 

更新/移动节点

移动节点需要一次 select 和一次 update 操作。

ancestorpath = db.categoriesAAO.findOne({_id:'Cell_Phones_and_Smartphones'}).ancestors;
ancestorpath.push('Cell_Phones_and_Smartphones')
db.categoriesAAO.update({_id:'LG'},
{$set:{parent:'Cell_Phones_and_Smartphones', ancestors:ancestorpath}});
//{ "_id" : "LG", "ancestors" : [     "Electronics",     "Cell_Phones_and_Accessories",
//     "Cell_Phones_and_Smartphones" ], "parent" : "Cell_Phones_and_Smartphones" } 

节点删除

节点删除通过一次操作完成。

db.categoriesAAO.remove({_id:'LG'}); 

获取无序节点子节点

注意：除非您引入 order 字段，否则无法获得有序的节点子节点列表。如果您需要顺序，应考虑另一种方法。

db.categoriesAAO.find({$query:{parent:'Electronics'}}) 

获取所有节点后代

有两种方法可以获取所有节点后代。一种是经典的递归方法。

var ancestors = db.categoriesAAO.find({ancestors:"Cell_Phones_and_Accessories"},{_id:1});
while(true === ancestors.hasNext()) {
       var elem = ancestors.next();
       descendants.push(elem._id);
   }
descendants.join(",")
//Cell_Phones_and_Smartphones,Headsets,Batteries,Cables_And_Adapters,
//Nokia,Samsung,Apple,HTC,Vyacheslav

第二种是使用 MongoDB 2.2 中引入的聚合框架。

 var aggrancestors = db.categoriesAAO.aggregate([
    {$match:{ancestors:"Cell_Phones_and_Accessories"}},
    {$project:{_id:1}},
    {$group:{_id:{},ancestors:{$addToSet:"$_id"}}}
])

descendants = aggrancestors.result[0].ancestors
descendants.join(",")
//Vyacheslav,HTC,Samsung,Cables_And_Adapters,Batteries,Headsets,
//Apple,Nokia,Cell_Phones_and_Smartphones 

获取节点路径

此操作通过一次数据库调用完成，这是此方法的优势。

var path=[]
var item = db.categoriesAAO.findOne({_id:"Nokia"})
item
path=item.ancestors;
path.join(' / ');
//Electronics / Cell_Phones_and_Accessories / Cell_Phones_and_Smartphones 

索引

建议索引为 ancestors

db.categoriesAAO.ensureIndex( { ancestors: 1 } ) 

代码示例

代码可从仓库 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 Web shell。

关注点

请注意，MongoDB 不提供 ACID 事务。这意味着，对于拆分为单独 update 命令的 update 操作，您的应用程序应实现额外的代码来支持您代码特定的事务。

10gen 的正式建议如下：

• 父节点引用模式提供了一种简单的树存储解决方案，但需要多次查询才能检索子树。
• 子节点引用模式为树存储提供了合适的解决方案，只要不需要对子树进行任何操作。该模式也可能为存储节点可能有多个父节点的图提供合适的解决方案。
• 祖先节点数组模式 - 除非您需要不断获取节点路径，否则没有特定优势。

您可以自由混合使用这些模式（通过引入 order 字段等），以匹配您的应用程序所需的数据操作。

我已经准备了以下关于如何在 MongoDB 中存储树状结构的示例集。

您可能想查看 本文，它描述了嵌套集、物化路径和组合方法。

历史

• 2013 年 1 月 4 日：初始版本