0

I'm in the process of building a tree structure, which should support the following requirements:

  1. It should be possible to find the root of the tree
  2. The tree will most often be traversed from root->leaf (I may get a specific node based on its document Id, and populate the tree based off that node)
  3. It will be common to move child notes between parents
  4. It will be common to rename individual nodes

Since I'm working with a document database, I have a hard time figuring out how to model this the best possible way.

Initially I went with a general tree-structure that only keeps child references in the parents, i.e.:

{
    ... properties;
    "children": ["child_id_#", "child_id_#"] 
}

The above almost fulfills my requirements, to summarize:

  • I can easily build the tree root->leaf (from any given node in the tree)
  • Moving branches between parents is very easy
  • Renaming nodes is easy

However, one thing that the above structure doesn't give away is the ability to find the absolute root of the tree - I simply can't find any efficient way to query the root document from the backend, without using a lot of request units.

Opposed to the above mentioned structure, a structure with parent references solves the problem with finding the absolute root of the tree with ease - Simply I will just have to find the document without any parent references.

For obvious reasons, I do however not want to proceed with a leaf->root structure such as a general tree with parent references, because it doesn't support my 2nd requirement very well.

My final guess would be to go beyond general structures (that I could find on my own) and implement both, that is:

{
    ... properties;
    "parent": #parent_id
    "children": ["child_id_#", "child_id_#"] 
}

It requires a bit more handling in my backend - But I believe it solves my issue as it fulfills my requirements.

I did look into the tutorials from MongoDB and in particular I was considering materialized paths as well - But I somewhat ruled this out, as I believe it doesn't support renaming parent nodes, and moving branches very well (Especially if the tree becomes very large, it will become expensive in terms of request units, because the paths for multiple nodes has to be edited)

My question(s) is therefore:

  • Do you believe that my reasoning is valid?
  • Do you see this working (i.e. keeping both children and parent references in each document)
  • Could this be done even better?
1
  • I think your second schema, with both a parent and children field, is the way to go to fulfill all your requirements. And it shouldn't be too hard, when relocating nodes, to change the parentId of the root node that's being moved. That said, are you sure mongodb is the right tool for this? If you need a pure tree, a graph db, or even a regular SQL DB that allows you to do self-joins easily might be more appropriate. Generally speaking, if you find yourself doing a lot of joins on a document DB, then it may not be the right tool to use.
    – Hashcut
    Aug 30 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.