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(‘ / ‘);