Mindmajix

MongoDB and Tree Structures

In MongoDB, we can store tree structures. Most projects usually deal with tree structures, and this is why you need to know how to store these in MongoDB. However, when dealing with tree structures in the MongoDB, we should be able to perform operations in the tree which include inserting, updating, and removal of nodes, calculate the path which leads to a particular node, and then get all the descendants of a particular node.

For us to operate with the tree, some calculations will be needed for changing the position of a particular node together with its siblings.

Addition of a New Node

Consider the example given below:

var excount = db.categoriesPCO.find({parent:’Linux’}).count();
var norder = (excount+1)*10;
db.categoriesPCO.insert({_id:’LG’, parent:’Linux’, someadditionalattr:’test’, order:norder})
//{ “_id” : “Ubuntu”, “parent” : “Linux”, “someadditionalattr” : “test”, “order” : 40 }

That is a new node that can be added. Very simple!

Updating a Node

Consider the example given below, which shows how the updating of an existing node can be done:

excount = db.categoriesPCO.find({parent:’Linux_Distributions’}).count();
norder = (excount+1)*10;
db.categoriesPCO.update({_id:’LG’},{$set:{parent:’Linux_Distributions’, order:norder}});
//{ “_id” : “Ubuntu”, “order” : 60, “parent” : “Linux_Distributions”, “someadditionalattr” :
“test” }

If you need to remove a particular node, then use the following command:

db.categoriesPCO.remove({_id:’Ubuntu’});

If you need to get the node children in an ordered manner, then do it as shown below:

db.categoriesPCO.find({$query:{parent:’Linux’}, $orderby:{order:1}})
//{ “_id” : “Ubuntu”, “parent” : “Linux”, “order” : 10 }
//{ “_id” : “Our_Main_Products”, “parent” : “Linux”, “order” : 20 }
//{ “_id” : “Linux_Distributions”, “parent” : “Linux”, “order” : 30 }

That is how it can be done. If you need to get the descendants of a particular node, then do it as follows:

var desc=[]
var stack=[];
var it = db.categoriesPCO.findOne({_id:”Linux_Distributions”});
stack.push(it);
while (stack.length>0){
var cnode = stack.pop();
var child= db.categoriesPCO.find({parent:cnode._id});
while(true === child.hasNext()) {
var childn = child.next();
desc.push(childn._id);
stack.push(childn);
}
}
desc.join(“,”)

Path to a particular Node

Sometimes, you might need to get the path which leads to a particular node. The operation to be involved in this case will be a recursive one, as shown below:

var p =[]
var it = db.categoriesPCO.findOne({_id:”RedHat”})
while (it.parent !== null) {
it=db.categoriesPCO.findOne({_id:it.parent});
p.push(it._id);
}
p.reverse().join(‘ / ‘);

In this case, indexes can be used as follows:

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

The above operations are for tree structures which have a parent reference. In the next section, we will discuss tree structures which have a child reference.

In this case, an “ID” and a “ChildReference” for each node will be stored. An order field will not be necessary for this case, because the information is provided by the child collection. In most cases, the order of an array is preferred, but if this is not supported in your case, then an additional code will have to be written for your maintaining of the order, meaning that much complexity will be involved.

Addition of a New Node

This can be added as shown below:

db.categoriesCRO.insert({_id:’Ubuntu’, childs:[]});
db.categoriesCRO.update({_id:’Linux’},{ $addToSet:{childs:’Ubuntu’}});
//{ “_id” : “Linux”, “childs” : [ “Linux_Distributions”, “Our_Top_Products”,
“Linux_Distrutions”, “Ubuntu” ] }

If you need to move a particular node, then do it as follows:

db.categoriesCRO.update({_id: ‘Linux_Distributions’},{ $addToSet:{childs:’Ubuntu’}});
db.categoriesCRO.update({_id:’Linux’},{$pull:{childs:’Ubuntu’}});
//{ “_id” : “Linux_Distributions”, “childs” : [ “RedHat”, “Suse”, “CentOS”, “Mint”, “Kali”,
“Fedora” ] }

If you need to remove a particular node, then do it as follows:

db.categoriesCRO.update({_id:’Linux_Distributions’},{$pull:{childs:’Ubuntu’}})
db.categoriesCRO.remove({_id:’Ubuntu’});

The above code will remove the node that you specify.

If you need to get the children of a node in an ordered manner, then do it as follows:

var p = db.categoriesCRO.findOne({_id:’Linux’})
db.categoriesCRO.find({_id:{$in:p.childs}})

However, note that in the above, an additional sorting in the client side will be needed in the parent array sequence.

To get all of the descendants of a particular node, then do it as follows:

var desc=[]
var stack=[];
var it = db.categoriesCRO.findOne({_id:”Linux_Distributions”});
stack.push(it);
while (stack.length>0){
var cnode = stack.pop();
var child = db.categoriesCRO.find({_id:{$in:cnode.childs}});
while(true === child.hasNext()) {
var childn = child.next();
desc.push(childn._id);
if(childn.childs.length>0){
stack.push(childn);
}
}
}
desc.join(“,”)

Path to a Node

If you need to obtain a path which leads to a particular node, then do it as follows:

var p=[]
var it = db.categoriesCRO.findOne({_id:”Ubuntu”})
while ((it=db.categoriesCRO.findOne({childs:it._id}))) {
p.push(it._id);
}
p.reverse().join(‘ / ‘);

Indexes

It is recommended that indexes should be used on children. The following syntax should be used:

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

Tree Structure having an Array of Ancestors

In this case, an ID, ParentReferenc and an AncestorReference will be stored for each of the available nodes. The rest of the operations are discussed below:

Addition of a New Node

The new node can be added as follows in this kind of a tree structure:

var ancpath = db.categoriesAAO.findOne({_id:’Linux’}).ancestors;
ancpath.push(‘Linux’)
db.categoriesAAO.insert({_id:’Ubuntu’, parent:’Linux’,ancestors:ancpath});
//{ “_id” : “Ubuntu”, “parent” : “Linux”, “ancestors” : [ “Linux” ] }

To update a particular node, then do it as follows:

ancpath = db.categoriesAAO.findOne({_id: ‘Linux_Distributions’}).ancestors;
ancpath.push(‘Linux_Distributions’)
db.categoriesAAO.update({_id:’Ubuntu’},{$set:{parent:’Linux_Distributions’,
ancestors:ancpath}});
//{ “_id” : “Ubuntu”, “ancestors” : [ “Linux”,
“Linux_Distributions”,”Linux_Distributions” ], “parent” : “Linux_Distributions” }

If you need to remove a particular node, then use the following syntax:

db.categoriesAAO.remove({_id:’Ubuntu’});

For you to get the children of a node in an Unordered manner, then use the following syntax:

db.categoriesAAO.find({$query:{parent:’Linux’}})

Note that if you need to get the ordered children of a particular node, then an order field must be introduced. That is why you must come up with an approach which will help you to make the children ordered.

If you need to get all of the descendants of a particular node, then do it as follows:

var ancs = db.categoriesAAO.find({ancestors:”Linux_Distributions”},{_id:1});
while(true === ancs.hasNext()) {
var element = ancs.next();
desc.push(element._id);
}
desc.join(“,”)

One can also achieve the above by using the aggregations framework which is well known in MongoDB. This is shown below:

var agancestors = db.categoriesAAO.aggregate([
{$match:{ancestors:”Linux_Distributions”}},
{$project:{_id:1}},
{$group:{_id:{},ancestors:{$addToSet:”$_id”}}}
])
desce = agancestors.result[0].ancestors
desc.join(“,”)

Tree Structures with a Materialized Path

In this case, we have to store the “ID” and the “PathToNode.”

Addition of a New Node

This can be done as follows:

var ancpath = db.categoriesMP.findOne({_id:’Linux’}).path;
ancpath += ‘Linux,’
db.categoriesMP.insert({_id:’LG’, path:ancpath});
//{ “_id” : “Ubuntu”, “path” : “Linux,” }
To update or move a particular node, then do it as follows:
ancpath = db.categoriesMP.findOne({_id: ‘Linux_Distributions’}).path;
ancpath +=’ Linux_Distributions,’
db.categoriesMP.update({_id:’Ubuntu’},{$set:{path:ancpath}});
//{ “_id” : “Ubuntu”, “path” : “Linux, Linux_Distributions’, Linux_Distributions’,” }

To remove a particular node, then use the following syntax:

db.categoriesMP.remove({_id:’Ubuntu’});


0 Responses on MongoDB and Tree Structures"

Leave a Message

Your email address will not be published. Required fields are marked *

Copy Rights Reserved © Mindmajix.com All rights reserved. Disclaimer.
Course Adviser

Fill your details, course adviser will reach you.