MongoDB Tree Model: Get all ancestors, Get all descendants

MongoDB is not a graph database and doesn't provide graph traversal operations, so there is no direct solution.

You can use data model you have described in point 2. (nodes with ancestor list), the query find({ancestors:"myStartingNodeId"}) and sort/nest the results in your application code.

Another possibility is to use data model where _id (or some other field) represents full path, for example 'root.node1.node2'. Then graph queries can be transformed to substring queries and correct ordering can be achieved (I hope) just by sorting by this _id.

---

Update: btw. there are some tree structure patterns described in MongoDB docs: Model Tree Structures in MongoDB

Here's what data structure I finally came up with. It's optimized for read queries. Some write queries (like moving subtrees) can be painful.

{
  id: "...",
  ancestors: ["parent_node_id", ..., "root_node_id"], // order is important!
  children: ["child1_id", "child2_id", ...]
}

Benefits:

• Easy to get all documents for a sub-tree

• Easy to get all documents from some node to the root

• Easy to check if some document is parent/child/ancestor/descendant of some node

• Children are sorted. Can be easily moved by changing the children array order

How to use it:

• Get by ID: findOne({ id: "..." })

• Get Parent: findOne({ children: "..." })

• Get all Ancestors: first do Get by ID, then grab the ancestors array and look for all documents that match the given list of IDs

• Get all Children: find({ 'ancestors.0': "..." })

• Get all Descendants: find({ ancestors: "..." })

• Get all Descendants up to x generations: find({ $and: [ {ancestors: "..."}, {ancestors: {$size: x}} ] })

Drawbacks:

• The application code has to take care of correct order.

• The application code has to build nested objects (maybe this is possible using MongoDB Aggregation framework).

• Every insert must be done using 2 queries.

• Moving whole sub-trees between nodes must update a lot of documents.