Tree structure modeling (parent reference, child reference, path enumeration)

Tree Structure Modeling (Parent Reference, Child Reference, Path Enumeration)

As a document-oriented database, MongoDB provides multiple modeling solutions for handling tree-structured data. Parent reference, child reference, and path enumeration are three typical methods, each with its own advantages and disadvantages in different query scenarios.

Parent Reference Pattern

The parent reference pattern establishes hierarchical relationships by storing the parent node ID in child nodes. This pattern is suitable for scenarios with uncertain depth and frequent updates to child nodes.

// Parent reference pattern example
{
  _id: "node1",
  name: "Root Node",
  parentId: null  // Root node has no parent
},
{
  _id: "node2",
  name: "Child Node A",
  parentId: "node1"  // Points to the parent node
},
{
  _id: "node3",
  name: "Child Node B",
  parentId: "node1"
}

Typical operations for querying all child nodes:

// Find direct child nodes of a specific node
db.nodes.find({ parentId: "node1" })

// Recursive query for all descendant nodes requires application-layer processing
function findAllDescendants(parentId) {
  const descendants = []
  const queue = [parentId]
  
  while(queue.length > 0) {
    const currentId = queue.shift()
    const children = db.nodes.find({ parentId: currentId }).toArray()
    descendants.push(...children.map(c => c._id))
    queue.push(...children.map(c => c._id))
  }
  
  return descendants
}

Child Reference Pattern

The child reference pattern is the opposite of the parent reference pattern, storing an array of all child node IDs in the parent node. This solution is suitable for scenarios with frequent reads but infrequent updates.

// Child reference pattern example
{
  _id: "node1",
  name: "Root Node",
  children: ["node2", "node3"]  // Stores an array of child node IDs
},
{
  _id: "node2",
  name: "Child Node A",
  children: []
},
{
  _id: "node3",
  name: "Child Node B",
  children: ["node4"]
},
{
  _id: "node4",
  name: "Grandchild Node",
  children: []
}

Example query operations:

// Get all direct child nodes of a node
const parent = db.nodes.findOne({ _id: "node1" })
const children = db.nodes.find({ _id: { $in: parent.children } }).toArray()

// Recursive query is required to get the complete tree structure
async function getTree(nodeId) {
  const node = await db.nodes.findOne({ _id: nodeId })
  if (!node.children || node.children.length === 0) return node
  
  const children = await db.nodes.find({ 
    _id: { $in: node.children } 
  }).toArray()
  
  node.children = await Promise.all(
    children.map(child => getTree(child._id))
  )
  return node
}

Path Enumeration Pattern

Path enumeration achieves fast ancestor queries by storing the complete path from the root to the current node in each node. It is suitable for scenarios requiring frequent path and ancestor queries.

// Path enumeration pattern example
{
  _id: "node1",
  name: "Root Node",
  path: null  // Root node path is empty
},
{
  _id: "node2",
  name: "Child Node A",
  path: "node1"  // Path uses a separator
},
{
  _id: "node3",
  name: "Child Node B",
  path: "node1"
},
{
  _id: "node4",
  name: "Grandchild Node",
  path: "node1,node3"  // Complete path
}

Efficient implementation of path queries:

// Find all ancestors of a specific node
const node = db.nodes.findOne({ _id: "node4" })
const ancestorIds = node.path.split(',')  // ["node1", "node3"]
const ancestors = db.nodes.find({ 
  _id: { $in: ancestorIds } 
}).toArray()

// Find all descendant nodes using regex matching
db.nodes.find({ 
  path: { $regex: /^node1(,|$)/ } 
})

// Find all nodes in a subtree
db.nodes.find({
  $or: [
    { _id: "node1" },
    { path: { $regex: /^(node1,|node1$)/ } }
  ]
})

Hybrid Pattern in Practice

In real-world projects, multiple patterns are often combined. For example, using both parent reference and path enumeration:

{
  _id: "node1",
  name: "Root Node",
  parentId: null,
  path: null,
  children: ["node2", "node3"],
  depth: 0
},
{
  _id: "node2",
  name: "Child Node A",
  parentId: "node1",
  path: "node1",
  children: [],
  depth: 1
}

This hybrid solution supports complex queries:

// Query all nodes at a specific depth
db.nodes.find({ depth: 2 })

// Create indexes for both path and parentId
db.nodes.createIndex({ path: 1 })
db.nodes.createIndex({ parentId: 1 })

// Get the path from a node to the root
function getPath(nodeId) {
  const path = []
  let currentId = nodeId
  
  while(currentId) {
    const node = db.nodes.findOne({ _id: currentId })
    path.unshift(node._id)
    currentId = node.parentId
  }
  
  return path
}

Performance Optimization Considerations

1. Indexing Strategy:

   // Parent reference pattern requires a parent ID index
   db.nodes.createIndex({ parentId: 1 })
   
   // Path enumeration pattern requires a path index
   db.nodes.createIndex({ path: 1 })
   

2. Bulk Update Issues:

   // When moving a subtree, update all descendant paths
   function updateSubtreePath(oldPath, newPath) {
     // Update the current node
     db.nodes.updateOne(
       { path: oldPath },
       { $set: { path: newPath } }
     )
     
     // Update all descendant nodes
     db.nodes.updateMany(
       { path: { $regex: `^${oldPath},` } },
       [{ $set: { 
         path: { 
           $concat: [
             newPath, 
             { $substr: [ "$path", oldPath.length, 10000 ] } 
           ] 
         } 
       } }]
     )
   }
   

3. Materialized Path Design:

   // Use fixed-length encoding to optimize path storage
   {
     _id: "node4",
     path: "01.03",  // 01=node1, 03=node3
     pathCodes: ["01", "03"]
   }
   
   // Use array operations for queries
   db.nodes.find({ pathCodes: "01" })  // All child nodes of node1
   

Practical Case: Comment System Implementation

Typical implementation of multi-level comments:

// Using parent reference + path enumeration
{
  _id: "comment1",
  postId: "post123",
  author: "userA",
  text: "Main comment",
  parentId: null,
  path: null,
  createdAt: ISODate("2023-01-01"),
  likes: 5
},
{
  _id: "comment2",
  postId: "post123",
  author: "userB",
  text: "Reply to main comment",
  parentId: "comment1",
  path: "comment1",
  createdAt: ISODate("2023-01-02"),
  likes: 2
}

Common query examples:

// Get all top-level comments for a post
db.comments.find({ 
  postId: "post123", 
  parentId: null 
}).sort({ createdAt: -1 })

// Get all replies to a comment (including nested replies)
db.comments.find({ 
  path: { $regex: /^comment1(,|$)/ } 
}).sort({ createdAt: 1 })

// Get direct child comments of a comment
db.comments.find({ 
  parentId: "comment1" 
}).sort({ likes: -1 })

Transaction Handling Considerations

Tree structure updates typically require transaction support:

// Example transaction for moving a node
const session = db.getMongo().startSession()
try {
  session.startTransaction()
  
  const node = db.nodes.findOne({ _id: "node4" }, { session })
  const newParent = db.nodes.findOne({ _id: "node2" }, { session })
  
  // Update the current node
  db.nodes.updateOne(
    { _id: "node4" },
    { $set: { parentId: "node2", path: `${newParent.path},${node._id}` } },
    { session }
  )
  
  // Update paths of all descendant nodes
  const oldPathPrefix = node.path ? `${node.path},${node._id}` : node._id
  const newPathPrefix = newParent.path ? `${newParent.path},${node._id}` : node._id
  
  const descendants = db.nodes.find(
    { path: { $regex: `^${oldPathPrefix}` } },
    { session }
  ).toArray()
  
  descendants.forEach(descendant => {
    const newPath = descendant.path.replace(oldPathPrefix, newPathPrefix)
    db.nodes.updateOne(
      { _id: descendant._id },
      { $set: { path: newPath } },
      { session }
    )
  })
  
  await session.commitTransaction()
} catch (error) {
  await session.abortTransaction()
  throw error
} finally {
  session.endSession()
}