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.

If you want to enrich your career and become a professional in MongoDB, then visit Mindmajix - a global online training platform: "MongoDB Training" This course will help you to achieve excellence in this domain. 

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(“,”)

 Frequently Asked MongoDB Interview Questions

A path to a particular node

Sometimes, you might need to get the path that 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 that have a parent reference. In the next section, we will discuss tree structures that have a child reference.

Frequently asked Devops Interview Questions

In this case, an “ID” and a “ChildReference” for each node will be stored. An ordered 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 on the client-side will be needed in the parent array sequence.

Related blog: Sorting of data

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(“,”)

A path to a Node

If you need to obtain a path that 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, parent reference, 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 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 ordered 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 aggregation framework which is well known in MongoDB. This is shown below:

Related blog: MongoDB Tutorial for Beginners

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’});