MyPage is a personalized page based on your interests.The page is customized to help you to find content that matters you the most.


I'm not curious

MongoDB and Tree Structures

Published on 29 April 17
541
0
1

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


























































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


MongoDB and Tree Structures - Image 1

MongoDB Training - Live MongoDB Online Training By Expert Trainers

https://mindmajix.com/mongodb-training

MongoDB Training - Instructor Led Live MongoDB Online Training ? 30 Hrs Project Scenarios ? Recorded Sessions ? Training Material ? Pay in Installments*

This blog is listed under Open Source and Data & Information Management Community

Related Posts:
Post a Comment

Please notify me the replies via email.

Important:
  • We hope the conversations that take place on MyTechLogy.com will be constructive and thought-provoking.
  • To ensure the quality of the discussion, our moderators may review/edit the comments for clarity and relevance.
  • Comments that are promotional, mean-spirited, or off-topic may be deleted per the moderators' judgment.
You may also be interested in
Awards & Accolades for MyTechLogy
Winner of
REDHERRING
Top 100 Asia
Finalist at SiTF Awards 2014 under the category Best Social & Community Product
Finalist at HR Vendor of the Year 2015 Awards under the category Best Learning Management System
Finalist at HR Vendor of the Year 2015 Awards under the category Best Talent Management Software
Hidden Image Url

Back to Top