Trees in MongoDB

[Voltron]

First of, thanks to Sean Cribs, he posed the question so well in his
blog entry here(http://seancribbs.com/tech/2009/09/28/modeling-a-tree-
in-a-document-database/)

I am facing the problem of creating trees in MongoDB too at the
moment, based on the methods detailed by Sean, what would be the
method to choose for MongoDb and where would one place the indexes?
Are there other ways?

Sean did not get many answers, so I decided to ask the MongoDB devs
and users directly.


Thanks

[Mathias Stearn]

One method that he didn't cover is storing fully-qualified paths. This gives you efficient subtree querying and each node knows all of it's parents. I haven't benchmarked this, but I think it will work well for low-depth trees. I'll use ':' as the path separator so that it can be used unescaped in a regex.

first insert documents like this and add an index on "path" (or just put it in the _id field which is automatically indexed) :

{path: "a", data: STUFF}

{path: "a:b"}

{path: "a:c"}

{path: "a:c:d"}

{path: "e"}

You could then fetch the subtree rooted at "a" using find({path: /^a/}). Mongo uses an index for all prefix queries so that will be very efficient. 

If you are at node "a:c:d" and want the parent objects you can get that with find({path: {$in: {'a', 'a:d'}}}).

I haven't benchmarked this against the other methods, but for subtree searches this should be pretty good. Also, it should ensure a good locality to your subtrees if you use the path as the shard-key.

If you have deep trees then either the parent_id or the child list method would work well but will require many round trips (one per level) to fetch whole sub-trees. Just make sure you index the children and parent_id fields. You could always start by using all three methods and then see what works best for you.

-Mathias

[Voltron]

Thanks Mathias!