树形结构建模（父引用、子引用、路径枚举）

树形结构建模（父引用、子引用、路径枚举）

MongoDB作为文档型数据库，处理树形结构数据时提供了多种建模方案。父引用、子引用和路径枚举是三种典型方法，每种方案在不同查询场景下各有优劣。

父引用模式

父引用模式通过在子节点中存储父节点ID来建立层级关系。这种模式适合深度不确定且频繁更新子节点的场景。

// 父引用模式示例
{
  _id: "node1",
  name: "根节点",
  parentId: null  // 根节点无父节点
},
{
  _id: "node2",
  name: "子节点A",
  parentId: "node1"  // 指向父节点
},
{
  _id: "node3",
  name: "子节点B",
  parentId: "node1"
}

查询所有子节点的典型操作：

// 查找某个节点的直接子节点
db.nodes.find({ parentId: "node1" })

// 递归查询所有后代节点需要应用层处理
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
}

子引用模式

子引用模式与父引用相反，在父节点中存储所有子节点ID数组。这种方案适合读取频繁但更新较少的场景。

// 子引用模式示例
{
  _id: "node1",
  name: "根节点",
  children: ["node2", "node3"]  // 存储子节点ID数组
},
{
  _id: "node2",
  name: "子节点A",
  children: []
},
{
  _id: "node3",
  name: "子节点B",
  children: ["node4"]
},
{
  _id: "node4",
  name: "孙子节点",
  children: []
}

查询操作的示例：

// 获取节点所有直接子节点
const parent = db.nodes.findOne({ _id: "node1" })
const children = db.nodes.find({ _id: { $in: parent.children } }).toArray()

// 获取完整树结构需要递归查询
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
}

路径枚举模式

路径枚举通过在节点中存储从根到当前节点的完整路径来实现快速祖先查询。适合需要频繁查询路径和祖先的场景。

// 路径枚举模式示例
{
  _id: "node1",
  name: "根节点",
  path: null  // 根节点路径为空
},
{
  _id: "node2",
  name: "子节点A",
  path: "node1"  // 路径使用分隔符连接
},
{
  _id: "node3",
  name: "子节点B",
  path: "node1"
},
{
  _id: "node4",
  name: "孙子节点",
  path: "node1,node3"  // 完整路径
}

路径查询的高效实现：

// 查找某个节点的所有祖先
const node = db.nodes.findOne({ _id: "node4" })
const ancestorIds = node.path.split(',')  // ["node1", "node3"]
const ancestors = db.nodes.find({ 
  _id: { $in: ancestorIds } 
}).toArray()

// 查找所有后代节点可以使用正则匹配
db.nodes.find({ 
  path: { $regex: /^node1(,|$)/ } 
})

// 查找子树所有节点
db.nodes.find({
  $or: [
    { _id: "node1" },
    { path: { $regex: /^(node1,|node1$)/ } }
  ]
})

混合模式实践

实际项目中常组合使用多种模式。例如同时使用父引用和路径枚举：

{
  _id: "node1",
  name: "根节点",
  parentId: null,
  path: null,
  children: ["node2", "node3"],
  depth: 0
},
{
  _id: "node2",
  name: "子节点A",
  parentId: "node1",
  path: "node1",
  children: [],
  depth: 1
}

这种混合方案支持复杂查询：

// 查询特定深度的所有节点
db.nodes.find({ depth: 2 })

// 同时利用path和parentId建立索引
db.nodes.createIndex({ path: 1 })
db.nodes.createIndex({ parentId: 1 })

// 获取节点到根的路径
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
}

性能优化考量

1. 索引策略：

   // 父引用模式必须建立父ID索引
   db.nodes.createIndex({ parentId: 1 })
   
   // 路径枚举模式需要路径索引
   db.nodes.createIndex({ path: 1 })
   

2. 批量更新问题：

   // 移动子树时需要更新所有后代路径
   function updateSubtreePath(oldPath, newPath) {
     // 更新当前节点
     db.nodes.updateOne(
       { path: oldPath },
       { $set: { path: newPath } }
     )
     
     // 更新所有后代节点
     db.nodes.updateMany(
       { path: { $regex: `^${oldPath},` } },
       [{ $set: { 
         path: { 
           $concat: [
             newPath, 
             { $substr: [ "$path", oldPath.length, 10000 ] } 
           ] 
         } 
       } }]
     )
   }
   

3. 物化路径设计：

   // 使用固定长度编码优化路径存储
   {
     _id: "node4",
     path: "01.03",  // 01=node1, 03=node3
     pathCodes: ["01", "03"]
   }
   
   // 查询时可以使用数组操作
   db.nodes.find({ pathCodes: "01" })  // 所有node1的子节点
   

实际案例：评论系统实现

多级评论的典型实现方案：

// 使用父引用+路径枚举
{
  _id: "comment1",
  postId: "post123",
  author: "userA",
  text: "主评论",
  parentId: null,
  path: null,
  createdAt: ISODate("2023-01-01"),
  likes: 5
},
{
  _id: "comment2",
  postId: "post123",
  author: "userB",
  text: "回复主评论",
  parentId: "comment1",
  path: "comment1",
  createdAt: ISODate("2023-01-02"),
  likes: 2
}

常用查询示例：

// 获取文章的所有顶级评论
db.comments.find({ 
  postId: "post123", 
  parentId: null 
}).sort({ createdAt: -1 })

// 获取某条评论的所有回复（包括嵌套回复）
db.comments.find({ 
  path: { $regex: /^comment1(,|$)/ } 
}).sort({ createdAt: 1 })

// 获取评论的直系子评论
db.comments.find({ 
  parentId: "comment1" 
}).sort({ likes: -1 })

事务处理注意事项

树形结构更新通常需要事务支持：

// 移动节点的事务示例
const session = db.getMongo().startSession()
try {
  session.startTransaction()
  
  const node = db.nodes.findOne({ _id: "node4" }, { session })
  const newParent = db.nodes.findOne({ _id: "node2" }, { session })
  
  // 更新当前节点
  db.nodes.updateOne(
    { _id: "node4" },
    { $set: { parentId: "node2", path: `${newParent.path},${node._id}` } },
    { session }
  )
  
  // 更新所有后代节点路径
  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()
}