2

Let's say we have a tree structure like:

  • node 0
    • node 0.0
    • node 0.1
      • node 0.1.0
      • node 0.1.1
        • node 0.1.1.0
        • ...

Each node stores it's path like 0.1.1.0 where digit is an id field(it can be mongodb ObjectId for example) and . is a separator(it can be # for example).

Let's say I want to get all descendants of some node, then I can use regex like:

^{node.path}{separator}(Mongodb: { $match: { path: { $regex: '^' + node.path + '#' } } }

Now let's say I want to get not all but only n-depth descendants, like:

  • only immediate children, depth 1
  • only immediate children and their immediate children, depth 2
  • ..., depth n

Question is how to do this query as efficient as possible, practically with Mongodb.

Current approach I found working is to do second $match(I even somehow cant combine it into one $match stage currently) after all descendants $match:

const baseRegex = { $regex: '^' + node.path + '#' }

aggregation pipeline code...

{ $match: { path: baseRegex} },
{ $match: { path: { $not: { $regex: baseRegex.$regex + '([^#]*#){${depth}}[^#]*$' } } } }

aggregation pipeline code...

Can you please help me to find better approach, ideally with just one simple regex in one $match stage?

Tamal Govinda das
  • 575
  • 5
  • 11
  • I would say a more suitable approach for mongodb is to store individual nodes as single documents and use [$graphLookup](https://www.mongodb.com/docs/manual/reference/operator/aggregation/graphLookup/) to build the tree when needed. For problems related to depth, you can leverage the `maxDepth` clause in `$graphLookup`. – ray Feb 12 '23 at 13:46

1 Answers1

0

It seems I found a really nice solution, but it needs an introduction of new field.

As materialized path pattern already assumes path field maintance burden, we can safely add new level field and sync it alongside path like level = path ? path.split(separator).length : 0.

Level field just knows how deep node is inside the tree, root node will have level 0, it's direct children level 1 and so on.

Now task to get n-depth descendants becomes trivial and can utilize exact index match in Mongodb with implementation like:

nodeSchema.index({ level: 1, path: 1 })
...
const baseRegex = { $regex: '^' + node.path + '#' }
{ $match: { path: baseRegex, level: { $lte: node.level + depth } } }

I think level field can be useful in some sort scenarios too.

PS First I set index to { path: 1, level: 1 } and discovered that somehow it is not used by Mongodb but { level: 1, path: 1 } works like a charm.

Tamal Govinda das
  • 575
  • 5
  • 11