在关系型数据库的设计中绝大多数数据模型都可以被表示为扁平的二维表结构。然而在实际的业务场景中经常会遇到具有层级关系的数据形态。评论系统就是其中一个典型的例子用户可以对文章发表评论其他用户可以对这条评论进行回复后续的用户还可以继续对回复进行回复。这种结构在数据结构中被称为“树Tree”。关系型数据库如 MySQL本身是基于集合论设计的天然并不直接支持树形结构的操作。因此在关系型数据库中存储树形结构需要借助特定的表结构设计与查询模式。本文将以评论系统为例详细阐述三种常见的树形结构存储方案邻接表Adjacency List、闭包表Closure Table以及物化路径Materialized Path。一、 业务场景与树形结构定义为了在后续的讲解中保持一致性我们首先定义一个评论系统的基础场景。假设一篇文章下有如下的评论回复层级评论A (id1) ├── 评论B (id2) - 回复评论A │ └── 评论D (id4) - 回复评论B └── 评论C (id3) - 回复评论A └── 评论E (id5) - 回复评论C在这个结构中“评论 A”是根节点它没有父节点。“评论 B”和“评论 C”是“评论 A”的子节点。“评论 D”是“评论 B”的子节点同时也是“评论 A”的后代节点。树的深度反映了回复的层级。对于这种结构评论系统的核心需求通常包括查询某条评论的所有直接回复。查询某条评论及其下属的所有层级的回复即获取整棵子树。查询某条评论的完整回复链路即从当前节点溯源到根节点。新增评论或回复。删除某条评论及其所有的下属回复。二、 方案一邻接表1. 理论概念邻接表是树形结构最直观、最简单的表示方法。在理论模型中邻接表的核心思想是每个节点只需要知道自己的直接父节点是谁。通过在每个节点上附加一个指针或引用指向其父节点就能将所有的节点连接成一棵完整的树。对于根节点由于其没有父节点该指针通常为空NULL。这种方式在空间利用率上极高因为每个节点只存储了一条额外的边信息。2. MySQL 中的实现在 MySQL 中邻接表的实现非常直接在评论表中增加一个parent_id字段用于存储当前评论的父评论的id。如果是顶级评论parent_id设为NULL。表结构设计-- 创建邻接表结构的评论表CREATETABLEcomment_adj(idINTAUTO_INCREMENTPRIMARYKEYCOMMENT评论主键ID,contentVARCHAR(500)NOTNULLCOMMENT评论内容,parent_idINTDEFAULTNULLCOMMENT父评论ID,created_atDATETIMEDEFAULTCURRENT_TIMESTAMPCOMMENT创建时间,-- 为了加速根据父节点查找子节点的查询可以在parent_id上建立索引INDEXidx_parent_id(parent_id))ENGINEInnoDBDEFAULTCHARSETutf8mb4COMMENT评论表_邻接表结构;插入数据插入数据非常简单只需要指定被回复的评论的 ID 即可。-- 插入顶级评论A (id1会自动生成)INSERTINTOcomment_adj(content,parent_id)VALUES(评论A,NULL);-- 插入评论B回复评论A (假设评论A的id为1)INSERTINTOcomment_adj(content,parent_id)VALUES(评论B,1);-- 插入评论C回复评论AINSERTINTOcomment_adj(content,parent_id)VALUES(评论C,1);-- 插入评论D回复评论B (假设已知评论B的id为2)INSERTINTOcomment_adj(content,parent_id)VALUES(评论D,2);-- 插入评论E回复评论C (假设已知评论C的id为3)INSERTINTOcomment_adj(content,parent_id)VALUES(评论E,3);查询操作1查询某条评论的直接子评论这是邻接表最擅长的操作只需进行一次简单的条件过滤。-- 查询评论A(id1)的直接回复SELECTid,content,created_atFROMcomment_adjWHEREparent_id1;2查询某条评论的所有后代评论获取子树在 MySQL 8.0 之前由于不支持递归查询邻接表要查询所有后代节点非常困难通常需要在应用程序代码中编写递归逻辑或者限制树的最大深度并通过多次LEFT JOIN来实现。但在 MySQL 8.0 引入了公共表表达式CTE, Common Table Expressions之后可以通过WITH RECURSIVE语法在数据库引擎层面完成递归查询。-- 查询评论A(id1)的所有后代评论WITHRECURSIVE CommentCTEAS(-- 基础成员 (Anchor Member)先查出起始节点或其直接子节点-- 这里我们从id1的直接子节点开始查起SELECTid,content,parent_idFROMcomment_adjWHEREparent_id1UNIONALL-- 递归成员 (Recursive Member)将表自身与CTE结果集连接-- 每次递归找到属于上一级结果集的子节点SELECTc.id,c.content,c.parent_idFROMcomment_adj cINNERJOINCommentCTE cteONc.parent_idcte.id)SELECTid,content,parent_idFROMCommentCTE;CTE 的 “递归”本质是用 “上一轮查到的子节点” 作为 “这一轮的父节点”重复查询其子节点直到查不到新的子节点为止。可以用 Java 伪代码更直观地体现这个循环逻辑// 锚点成员初始父节点的子节点ListRecordcteResult查询comment_adj表中parent_id1的记录;if(cteResult.isEmpty()){// 终止返回空结果return空集合;}// 递归循环while(true){// 取上一轮的所有id作为本轮要查的父idListLongparentIds从cteResult中提取所有id字段;// 查这些父id的子节点ListRecordnewRecords查询comment_adj表中parent_id在parentIds中的记录;// 终止条件本轮无新记录if(newRecords.isEmpty()){break;}// 合并新结果到总结果模拟UNION ALLcteResult.addAll(newRecords);}// 输出最终结果returncteResult;3查询某条评论的溯源路径获取所有祖先节点同样使用递归 CTE只不过方向变为由子节点向父节点查找。-- 查询评论D(id4)的所有祖先路径直到顶级评论WITHRECURSIVE AncestorCTEAS(-- 基础成员定位起始评论SELECTid,content,parent_idFROMcomment_adjWHEREid4UNIONALL-- 递归成员根据当前节点的parent_id查找父节点的idSELECTc.id,c.content,c.parent_idFROMcomment_adj cINNERJOINAncestorCTE cteONcte.parent_idc.id)SELECTid,content,parent_idFROMAncestorCTE;删除操作删除操作在邻接表中相对复杂。如果要删除一条评论通常也需要删除它的所有后代评论否则会产生“孤儿节点”。通过递归 CTE 可以找到所有需要删除的 ID然后执行删除-- MySQL支持将CTE的结果用于DELETE操作中但语法需要嵌套子查询-- 删除评论A(id1)及其所有后代DELETEFROMcomment_adjWHEREidIN(WITHRECURSIVE CommentCTEAS(SELECTidFROMcomment_adjWHEREid1UNIONALLSELECTc.idFROMcomment_adj cINNERJOINCommentCTE cteONc.parent_idcte.id)SELECTidFROMCommentCTE);3. 邻接表总结优点概念极简易于理解添加新节点的性能极好只需INSERT一行查询直接父子关系的效率极高。缺点在不支持递归查询的数据库版本中处理多层级树非常困难即使支持递归查询当树的层级过深或节点过多时递归 CTE 的计算开销也会比较大。三、 方案二闭包表1. 理论概念闭包表的理论基础是不再局限于存储直接的父子关系而是将树中所有节点之间的连接关系不论跨越多少层级都全面记录下来。如果节点 A 是节点 C 的祖先尽管它们之间可能隔着节点 B闭包表也会直接记录一条从 A 到 C 的边。此外闭包表通常还会记录节点到自身的路径。为了实现这一点闭包表结构需要两张表实体表用于存储节点的具体业务信息如评论内容、发布时间等。关系表路径表用于存储节点与节点之间的层级连接关系。2. MySQL 中的实现表结构设计我们需要分别建立评论表和评论关系表。为了提供更多的查询便利性通常在关系表中增加一个depth深度字段表示祖先到后代之间跨越的层级数量。-- 1. 评论实体表不需要parent_id完全扁平化CREATETABLEcomment_entity(idINTAUTO_INCREMENTPRIMARYKEYCOMMENT评论主键ID,contentVARCHAR(500)NOTNULLCOMMENT评论内容,created_atDATETIMEDEFAULTCURRENT_TIMESTAMPCOMMENT创建时间)ENGINEInnoDBDEFAULTCHARSETutf8mb4COMMENT评论表_实体表;-- 2. 评论关系表闭包表核心CREATETABLEcomment_closure(ancestorINTNOTNULLCOMMENT祖先节点ID,descendantINTNOTNULLCOMMENT后代节点ID,depthINTNOTNULLCOMMENT深度差0表示自己到自己1表示直接父子以此类推,PRIMARYKEY(ancestor,descendant),-- 联合主键保证唯一性INDEXidx_descendant(descendant)-- 用于反向查询祖先)ENGINEInnoDBDEFAULTCHARSETutf8mb4COMMENT评论表_闭包关系表;插入数据闭包表的插入逻辑需要两步首先在实体表中插入业务数据获取新的 ID然后在关系表中插入该节点与其他节点的关系。插入关系表的规则是插入一条自己到自己的关系depth0。找到父节点在关系表作为后代节点的所有记录复制这些记录将记录中的后代节点替换为新插入的节点 ID并将 depth 加 1。-- -- 插入顶级评论A (假设生成id1)-- INSERTINTOcomment_entity(content)VALUES(评论A);-- 关系表插入自己到自己的关系INSERTINTOcomment_closure(ancestor,descendant,depth)VALUES(1,1,0);-- -- 插入评论B回复评论A (假设生成id2)-- INSERTINTOcomment_entity(content)VALUES(评论B);-- 闭包表插入逻辑-- 找到祖先包含被回复节点(id1)的所有路径生成新的路径INSERTINTOcomment_closure(ancestor,descendant,depth)SELECTancestor,2,depth1FROMcomment_closureWHEREdescendant1UNIONALL-- 插入自己到自己的记录SELECT2,2,0;-- -- 插入评论D回复评论B (假设生成id4)-- INSERTINTOcomment_entity(content)VALUES(评论D);INSERTINTOcomment_closure(ancestor,descendant,depth)SELECTancestor,4,depth1FROMcomment_closureWHEREdescendant2UNIONALLSELECT4,4,0;经过上述操作关系表中的数据将会呈现出详尽的对应关系。例如对于节点 4它不仅有(4,4,0)还有(2,4,1)和(1,4,2)。查询操作闭包表将复杂的树形遍历转换为了普通的关系表JOIN查询这是它最大的优势。不需要任何递归即可完成深层查询。1查询某条评论的所有后代评论获取子树只需要在关系表中查出以目标评论为祖先节点的所有关系。-- 查询评论A(id1)的所有后代评论按深度排序SELECTe.id,e.content,c.depthFROMcomment_entity eINNERJOINcomment_closure cONe.idc.descendantWHEREc.ancestor1ANDc.depth0-- 排除自己ORDERBYc.depthASC;2查询某条评论的直接回复只需要限制深度为 1 即可。-- 查询评论A(id1)的直接子节点SELECTe.id,e.contentFROMcomment_entity eINNERJOINcomment_closure cONe.idc.descendantWHEREc.ancestor1ANDc.depth1;3查询某条评论的完整溯源路径将条件反转在关系表中查找以目标节点为后代的所有记录。-- 查询评论D(id4)的所有祖先节点SELECTe.id,e.content,c.depthFROMcomment_entity eINNERJOINcomment_closure cONe.idc.ancestorWHEREc.descendant4ANDc.depth0ORDERBYc.depthDESC;-- 按照层级从上往下排列删除操作闭包表的删除十分彻底一条 SQL 就可以删除指定节点及其所有的后代关系。如果要删除评论 B(id2) 及其下属的评论 D步骤如下-- 1. 查出所有需要删除的节点IDid2及其所有后代并在实体表中删除DELETEFROMcomment_entityWHEREidIN(SELECTdescendantFROMcomment_closureWHEREancestor2);-- 2. 清除关系表中涉及这些节点的关联信息-- 只要关系中的后代节点属于以2为祖先的子树中就需要被删除DELETEFROMcomment_closureWHEREdescendantIN(-- 内层查询ancestor2的所有descendant-- 外层封装成临时表temp避免同表修改冲突SELECTdescendantFROM(SELECTdescendantFROMcomment_closureWHEREancestor2)AStemp);3. 闭包表总结优点无论树的层级有多深所有的树查询查找祖先、查找后代、计算深度都被转化为了简单的纯粹的关联查询JOIN不需要依赖具体数据库的递归功能查询速度非常快灵活性极高。缺点空间换时间的极端体现。对于拥有 N 个节点的树如果是呈直线型的最坏情况关系表中将有O(N2)O(N^2)O(N2)条记录每次插入节点需要插入与其深度相同数量的关系记录在树庞大时关系表的数据量会急剧膨胀。四、 方案三物化路径1. 理论概念物化路径的设计思路类似于文件系统的目录路径如/usr/local/bin。在理论模型中物化路径将树从根节点到当前节点所经过的所有节点标识依次拼接成一个长字符串作为一个单独的属性存储在节点上。通过解析这个长字符串我们可以直接知道当前节点在树中的确切位置它的直接父节点是谁它所有的祖先节点是谁。同样利用字符串前缀匹配我们也能轻易找到它的所有后代节点。2. MySQL 中的实现在 MySQL 中可以通过向业务表中添加一个path路径字符串字段来实现。为了便于后续的查询与字符串处理路径字符串的格式必须设计规范。常见的格式约定是在节点 ID 前后都加上统一的分隔符例如/1/2/4/。之所以要在结尾也加上分隔符是为了防止类似LIKE /1/2%的查询错误地匹配到/1/20/。表结构设计-- 创建物化路径结构的评论表CREATETABLEcomment_path(idINTAUTO_INCREMENTPRIMARYKEYCOMMENT评论主键ID,contentVARCHAR(500)NOTNULLCOMMENT评论内容,pathVARCHAR(255)NOTNULLCOMMENT物化路径例如 /1/2/,created_atDATETIMEDEFAULTCURRENT_TIMESTAMPCOMMENT创建时间,-- 为path建立索引。因为我们常使用形如 /1/2/% 的前缀匹配查询B树索引对其非常有效INDEXidx_path(path))ENGINEInnoDBDEFAULTCHARSETutf8mb4COMMENT评论表_物化路径结构;插入数据物化路径的插入需要在应用层或数据库层获取父节点的path然后将自身生成的 ID 拼接在其后。在 MySQL 中我们可以使用事务及字符串函数完成。-- 插入顶级评论A-- 因为此时还没生成id可以先插入数据再通过主键更新其pathBEGIN;INSERTINTOcomment_path(content,path)VALUES(评论A,);UPDATEcomment_pathSETpathCONCAT(/,LAST_INSERT_ID(),/)WHEREidLAST_INSERT_ID();COMMIT;-- 此时id1的记录path为 /1/-- 插入评论B回复评论A (已知评论A的id为1path为 /1/)BEGIN;INSERTINTOcomment_path(content,path)VALUES(评论B,);-- 假设业务系统已知父节点path则可直接插入 /1/2/-- 若在数据库中操作可用如下语句UPDATEcomment_pathSETpathCONCAT((SELECTpathFROM(SELECTpathFROMcomment_pathWHEREid1)ASp),LAST_INSERT_ID(),/)WHEREidLAST_INSERT_ID();COMMIT;-- 此时id2的记录path为 /1/2/-- 插入评论D回复评论BBEGIN;INSERTINTOcomment_path(content,path)VALUES(评论D,);UPDATEcomment_pathSETpathCONCAT((SELECTpathFROM(SELECTpathFROMcomment_pathWHEREid2)ASp),LAST_INSERT_ID(),/)WHEREidLAST_INSERT_ID();COMMIT;-- 此时id4的记录path为 /1/2/4/查询操作物化路径的查询高度依赖于字符串处理和LIKE操作。1查询某条评论的所有后代评论获取子树我们知道任何后代节点的路径必然以祖先节点的路径作为前缀。因此使用LIKE可以非常高效地查出所有子树并且由于匹配模式不以通配符%开头索引idx_path是可以被有效使用的。-- 查询评论A(id1)的所有后代评论-- 假设已知评论A的path是 /1/SELECTid,content,pathFROMcomment_pathWHEREpathLIKE/1/%ANDid!1;-- 排除自身2查询某条评论的直接子评论物化路径本身并不直接体现明确的层级关系属性虽然可以通过分隔符的数量推断。要查询直接子评论我们需要通过正则表达式或计算字符串中分隔符如/的数量来判断深度。例如如果节点 A 的path是/1/长度为 3包含 2 个/那么它的直接子节点的path中必然包含 3 个/。-- 查询评论A(id1, path/1/)的直接回复-- 原理计算字符串中 / 的数量减1即为深度。子节点深度 父节点深度 1SELECTid,content,pathFROMcomment_pathWHEREpathLIKE/1/%AND(LENGTH(path)-LENGTH(REPLACE(path,/,)))-1(LENGTH(/1/)-LENGTH(REPLACE(/1/,/,)));(注这种查询方式涉及函数计算无法走普通 B 树索引此时查询效率依赖于LIKE前缀过滤出的数据集大小。实际业务中为了避免这种情况有时会结合使用物化路径和邻接表即表里既有path也有parent_id字段。)3查询某条评论的所有祖先节点在数据库层面查询祖先节点相对费力。因为当前节点如id4, path/1/2/4/包含的是祖先 ID 组成的字符串。最常见的做法是将字符串传递到应用程序中例如 Java, Python按分隔符split拆解出一个 ID 数组[1, 2, 4]然后再发起一次数据库查询SELECTid,contentFROMcomment_pathWHEREidIN(1,2);如果不依赖应用程序单纯在 MySQL 中查询-- 查询评论D(id4, path/1/2/4/)的所有祖先-- 利用INSTR或LOCATE函数判断候选记录的path是否为目标记录path的子串SELECTid,content,pathFROMcomment_pathWHERELOCATE(path,/1/2/4/)1ANDid!4;删除操作删除操作在物化路径模型中非常便捷。与查询后代逻辑相同一条包含LIKE条件的 SQL 即可删除整棵子树。-- 删除评论B(id2, path/1/2/)及其所有后代DELETEFROMcomment_pathWHEREpathLIKE/1/2/%;3. 物化路径总结优点不需要额外的关系表表结构简单对于整棵树的读取或者子树的读取非常高效依托于主键或前缀索引通过解析单条记录的path字段不用查库就能在应用程序里知道其所有祖先层级关系。缺点严重依赖字符串操作在数据库层面进行字符串的解析和函数计算时性能不佳路径字段有长度限制如VARCHAR(255)这决定了树的最大深度是有限的如果更改了某一个节点的层级移动子树需要更新该节点及其所有后代节点的路径字符串开销极大。五、 三种方案景总结采用邻接表适用于大多数常规场景特别是当不需要频繁查询深层结构或者项目使用的是支持 CTE 功能的现代数据库如 MySQL 8.0 / PostgreSQL时。在评论系统中如果你通常只展示一到两层回复像 B 站的评论区主评论下直接扁平化展示所有回复邻接表是绝对的首选因为它结构最自然插入速度最快。采用闭包表适用于对读操作查询深度、子树性能要求极高且树层级可能会非常深的场景。由于查询过程仅需要常规的 JOIN 操作不需要数据库执行繁重的递归运算。但前提是你能够接受额外的空间消耗以及稍微复杂的插入逻辑。采用物化路径适用于树结构层级不太深且读多写少特别是极少发生“移动子树”的场景。在电商分类层级、文章分类目录中非常常见。对于评论系统来说也是一个不错的折中方案特别是在将路径解析工作交托给业务代码层之后能在单一维度里实现极高的查询效率。数据库方案的选择往往不是非黑即白的。有时可以将它们结合使用例如在同一个表中同时保留parent_id发挥邻接表的直查优势和path字段发挥物化路径的范围筛选优势通过空间换取全方位的查询时间优化从而满足复杂多变的业务需求。常见的方案还有“邻接表 冗余根节点”配合上逻辑删除既规避了邻接表的劣势又保留了完整的树形结构。具体就不拓展了实际开发中的应用往往是灵活多变的。
树形结构的数据库存储方案：以评论系统为例
发布时间：2026/6/29 10:06:10
在关系型数据库的设计中绝大多数数据模型都可以被表示为扁平的二维表结构。然而在实际的业务场景中经常会遇到具有层级关系的数据形态。评论系统就是其中一个典型的例子用户可以对文章发表评论其他用户可以对这条评论进行回复后续的用户还可以继续对回复进行回复。这种结构在数据结构中被称为“树Tree”。关系型数据库如 MySQL本身是基于集合论设计的天然并不直接支持树形结构的操作。因此在关系型数据库中存储树形结构需要借助特定的表结构设计与查询模式。本文将以评论系统为例详细阐述三种常见的树形结构存储方案邻接表Adjacency List、闭包表Closure Table以及物化路径Materialized Path。一、 业务场景与树形结构定义为了在后续的讲解中保持一致性我们首先定义一个评论系统的基础场景。假设一篇文章下有如下的评论回复层级评论A (id1) ├── 评论B (id2) - 回复评论A │ └── 评论D (id4) - 回复评论B └── 评论C (id3) - 回复评论A └── 评论E (id5) - 回复评论C在这个结构中“评论 A”是根节点它没有父节点。“评论 B”和“评论 C”是“评论 A”的子节点。“评论 D”是“评论 B”的子节点同时也是“评论 A”的后代节点。树的深度反映了回复的层级。对于这种结构评论系统的核心需求通常包括查询某条评论的所有直接回复。查询某条评论及其下属的所有层级的回复即获取整棵子树。查询某条评论的完整回复链路即从当前节点溯源到根节点。新增评论或回复。删除某条评论及其所有的下属回复。二、 方案一邻接表1. 理论概念邻接表是树形结构最直观、最简单的表示方法。在理论模型中邻接表的核心思想是每个节点只需要知道自己的直接父节点是谁。通过在每个节点上附加一个指针或引用指向其父节点就能将所有的节点连接成一棵完整的树。对于根节点由于其没有父节点该指针通常为空NULL。这种方式在空间利用率上极高因为每个节点只存储了一条额外的边信息。2. MySQL 中的实现在 MySQL 中邻接表的实现非常直接在评论表中增加一个parent_id字段用于存储当前评论的父评论的id。如果是顶级评论parent_id设为NULL。表结构设计-- 创建邻接表结构的评论表CREATETABLEcomment_adj(idINTAUTO_INCREMENTPRIMARYKEYCOMMENT评论主键ID,contentVARCHAR(500)NOTNULLCOMMENT评论内容,parent_idINTDEFAULTNULLCOMMENT父评论ID,created_atDATETIMEDEFAULTCURRENT_TIMESTAMPCOMMENT创建时间,-- 为了加速根据父节点查找子节点的查询可以在parent_id上建立索引INDEXidx_parent_id(parent_id))ENGINEInnoDBDEFAULTCHARSETutf8mb4COMMENT评论表_邻接表结构;插入数据插入数据非常简单只需要指定被回复的评论的 ID 即可。-- 插入顶级评论A (id1会自动生成)INSERTINTOcomment_adj(content,parent_id)VALUES(评论A,NULL);-- 插入评论B回复评论A (假设评论A的id为1)INSERTINTOcomment_adj(content,parent_id)VALUES(评论B,1);-- 插入评论C回复评论AINSERTINTOcomment_adj(content,parent_id)VALUES(评论C,1);-- 插入评论D回复评论B (假设已知评论B的id为2)INSERTINTOcomment_adj(content,parent_id)VALUES(评论D,2);-- 插入评论E回复评论C (假设已知评论C的id为3)INSERTINTOcomment_adj(content,parent_id)VALUES(评论E,3);查询操作1查询某条评论的直接子评论这是邻接表最擅长的操作只需进行一次简单的条件过滤。-- 查询评论A(id1)的直接回复SELECTid,content,created_atFROMcomment_adjWHEREparent_id1;2查询某条评论的所有后代评论获取子树在 MySQL 8.0 之前由于不支持递归查询邻接表要查询所有后代节点非常困难通常需要在应用程序代码中编写递归逻辑或者限制树的最大深度并通过多次LEFT JOIN来实现。但在 MySQL 8.0 引入了公共表表达式CTE, Common Table Expressions之后可以通过WITH RECURSIVE语法在数据库引擎层面完成递归查询。-- 查询评论A(id1)的所有后代评论WITHRECURSIVE CommentCTEAS(-- 基础成员 (Anchor Member)先查出起始节点或其直接子节点-- 这里我们从id1的直接子节点开始查起SELECTid,content,parent_idFROMcomment_adjWHEREparent_id1UNIONALL-- 递归成员 (Recursive Member)将表自身与CTE结果集连接-- 每次递归找到属于上一级结果集的子节点SELECTc.id,c.content,c.parent_idFROMcomment_adj cINNERJOINCommentCTE cteONc.parent_idcte.id)SELECTid,content,parent_idFROMCommentCTE;CTE 的 “递归”本质是用 “上一轮查到的子节点” 作为 “这一轮的父节点”重复查询其子节点直到查不到新的子节点为止。可以用 Java 伪代码更直观地体现这个循环逻辑// 锚点成员初始父节点的子节点ListRecordcteResult查询comment_adj表中parent_id1的记录;if(cteResult.isEmpty()){// 终止返回空结果return空集合;}// 递归循环while(true){// 取上一轮的所有id作为本轮要查的父idListLongparentIds从cteResult中提取所有id字段;// 查这些父id的子节点ListRecordnewRecords查询comment_adj表中parent_id在parentIds中的记录;// 终止条件本轮无新记录if(newRecords.isEmpty()){break;}// 合并新结果到总结果模拟UNION ALLcteResult.addAll(newRecords);}// 输出最终结果returncteResult;3查询某条评论的溯源路径获取所有祖先节点同样使用递归 CTE只不过方向变为由子节点向父节点查找。-- 查询评论D(id4)的所有祖先路径直到顶级评论WITHRECURSIVE AncestorCTEAS(-- 基础成员定位起始评论SELECTid,content,parent_idFROMcomment_adjWHEREid4UNIONALL-- 递归成员根据当前节点的parent_id查找父节点的idSELECTc.id,c.content,c.parent_idFROMcomment_adj cINNERJOINAncestorCTE cteONcte.parent_idc.id)SELECTid,content,parent_idFROMAncestorCTE;删除操作删除操作在邻接表中相对复杂。如果要删除一条评论通常也需要删除它的所有后代评论否则会产生“孤儿节点”。通过递归 CTE 可以找到所有需要删除的 ID然后执行删除-- MySQL支持将CTE的结果用于DELETE操作中但语法需要嵌套子查询-- 删除评论A(id1)及其所有后代DELETEFROMcomment_adjWHEREidIN(WITHRECURSIVE CommentCTEAS(SELECTidFROMcomment_adjWHEREid1UNIONALLSELECTc.idFROMcomment_adj cINNERJOINCommentCTE cteONc.parent_idcte.id)SELECTidFROMCommentCTE);3. 邻接表总结优点概念极简易于理解添加新节点的性能极好只需INSERT一行查询直接父子关系的效率极高。缺点在不支持递归查询的数据库版本中处理多层级树非常困难即使支持递归查询当树的层级过深或节点过多时递归 CTE 的计算开销也会比较大。三、 方案二闭包表1. 理论概念闭包表的理论基础是不再局限于存储直接的父子关系而是将树中所有节点之间的连接关系不论跨越多少层级都全面记录下来。如果节点 A 是节点 C 的祖先尽管它们之间可能隔着节点 B闭包表也会直接记录一条从 A 到 C 的边。此外闭包表通常还会记录节点到自身的路径。为了实现这一点闭包表结构需要两张表实体表用于存储节点的具体业务信息如评论内容、发布时间等。关系表路径表用于存储节点与节点之间的层级连接关系。2. MySQL 中的实现表结构设计我们需要分别建立评论表和评论关系表。为了提供更多的查询便利性通常在关系表中增加一个depth深度字段表示祖先到后代之间跨越的层级数量。-- 1. 评论实体表不需要parent_id完全扁平化CREATETABLEcomment_entity(idINTAUTO_INCREMENTPRIMARYKEYCOMMENT评论主键ID,contentVARCHAR(500)NOTNULLCOMMENT评论内容,created_atDATETIMEDEFAULTCURRENT_TIMESTAMPCOMMENT创建时间)ENGINEInnoDBDEFAULTCHARSETutf8mb4COMMENT评论表_实体表;-- 2. 评论关系表闭包表核心CREATETABLEcomment_closure(ancestorINTNOTNULLCOMMENT祖先节点ID,descendantINTNOTNULLCOMMENT后代节点ID,depthINTNOTNULLCOMMENT深度差0表示自己到自己1表示直接父子以此类推,PRIMARYKEY(ancestor,descendant),-- 联合主键保证唯一性INDEXidx_descendant(descendant)-- 用于反向查询祖先)ENGINEInnoDBDEFAULTCHARSETutf8mb4COMMENT评论表_闭包关系表;插入数据闭包表的插入逻辑需要两步首先在实体表中插入业务数据获取新的 ID然后在关系表中插入该节点与其他节点的关系。插入关系表的规则是插入一条自己到自己的关系depth0。找到父节点在关系表作为后代节点的所有记录复制这些记录将记录中的后代节点替换为新插入的节点 ID并将 depth 加 1。-- -- 插入顶级评论A (假设生成id1)-- INSERTINTOcomment_entity(content)VALUES(评论A);-- 关系表插入自己到自己的关系INSERTINTOcomment_closure(ancestor,descendant,depth)VALUES(1,1,0);-- -- 插入评论B回复评论A (假设生成id2)-- INSERTINTOcomment_entity(content)VALUES(评论B);-- 闭包表插入逻辑-- 找到祖先包含被回复节点(id1)的所有路径生成新的路径INSERTINTOcomment_closure(ancestor,descendant,depth)SELECTancestor,2,depth1FROMcomment_closureWHEREdescendant1UNIONALL-- 插入自己到自己的记录SELECT2,2,0;-- -- 插入评论D回复评论B (假设生成id4)-- INSERTINTOcomment_entity(content)VALUES(评论D);INSERTINTOcomment_closure(ancestor,descendant,depth)SELECTancestor,4,depth1FROMcomment_closureWHEREdescendant2UNIONALLSELECT4,4,0;经过上述操作关系表中的数据将会呈现出详尽的对应关系。例如对于节点 4它不仅有(4,4,0)还有(2,4,1)和(1,4,2)。查询操作闭包表将复杂的树形遍历转换为了普通的关系表JOIN查询这是它最大的优势。不需要任何递归即可完成深层查询。1查询某条评论的所有后代评论获取子树只需要在关系表中查出以目标评论为祖先节点的所有关系。-- 查询评论A(id1)的所有后代评论按深度排序SELECTe.id,e.content,c.depthFROMcomment_entity eINNERJOINcomment_closure cONe.idc.descendantWHEREc.ancestor1ANDc.depth0-- 排除自己ORDERBYc.depthASC;2查询某条评论的直接回复只需要限制深度为 1 即可。-- 查询评论A(id1)的直接子节点SELECTe.id,e.contentFROMcomment_entity eINNERJOINcomment_closure cONe.idc.descendantWHEREc.ancestor1ANDc.depth1;3查询某条评论的完整溯源路径将条件反转在关系表中查找以目标节点为后代的所有记录。-- 查询评论D(id4)的所有祖先节点SELECTe.id,e.content,c.depthFROMcomment_entity eINNERJOINcomment_closure cONe.idc.ancestorWHEREc.descendant4ANDc.depth0ORDERBYc.depthDESC;-- 按照层级从上往下排列删除操作闭包表的删除十分彻底一条 SQL 就可以删除指定节点及其所有的后代关系。如果要删除评论 B(id2) 及其下属的评论 D步骤如下-- 1. 查出所有需要删除的节点IDid2及其所有后代并在实体表中删除DELETEFROMcomment_entityWHEREidIN(SELECTdescendantFROMcomment_closureWHEREancestor2);-- 2. 清除关系表中涉及这些节点的关联信息-- 只要关系中的后代节点属于以2为祖先的子树中就需要被删除DELETEFROMcomment_closureWHEREdescendantIN(-- 内层查询ancestor2的所有descendant-- 外层封装成临时表temp避免同表修改冲突SELECTdescendantFROM(SELECTdescendantFROMcomment_closureWHEREancestor2)AStemp);3. 闭包表总结优点无论树的层级有多深所有的树查询查找祖先、查找后代、计算深度都被转化为了简单的纯粹的关联查询JOIN不需要依赖具体数据库的递归功能查询速度非常快灵活性极高。缺点空间换时间的极端体现。对于拥有 N 个节点的树如果是呈直线型的最坏情况关系表中将有O(N2)O(N^2)O(N2)条记录每次插入节点需要插入与其深度相同数量的关系记录在树庞大时关系表的数据量会急剧膨胀。四、 方案三物化路径1. 理论概念物化路径的设计思路类似于文件系统的目录路径如/usr/local/bin。在理论模型中物化路径将树从根节点到当前节点所经过的所有节点标识依次拼接成一个长字符串作为一个单独的属性存储在节点上。通过解析这个长字符串我们可以直接知道当前节点在树中的确切位置它的直接父节点是谁它所有的祖先节点是谁。同样利用字符串前缀匹配我们也能轻易找到它的所有后代节点。2. MySQL 中的实现在 MySQL 中可以通过向业务表中添加一个path路径字符串字段来实现。为了便于后续的查询与字符串处理路径字符串的格式必须设计规范。常见的格式约定是在节点 ID 前后都加上统一的分隔符例如/1/2/4/。之所以要在结尾也加上分隔符是为了防止类似LIKE /1/2%的查询错误地匹配到/1/20/。表结构设计-- 创建物化路径结构的评论表CREATETABLEcomment_path(idINTAUTO_INCREMENTPRIMARYKEYCOMMENT评论主键ID,contentVARCHAR(500)NOTNULLCOMMENT评论内容,pathVARCHAR(255)NOTNULLCOMMENT物化路径例如 /1/2/,created_atDATETIMEDEFAULTCURRENT_TIMESTAMPCOMMENT创建时间,-- 为path建立索引。因为我们常使用形如 /1/2/% 的前缀匹配查询B树索引对其非常有效INDEXidx_path(path))ENGINEInnoDBDEFAULTCHARSETutf8mb4COMMENT评论表_物化路径结构;插入数据物化路径的插入需要在应用层或数据库层获取父节点的path然后将自身生成的 ID 拼接在其后。在 MySQL 中我们可以使用事务及字符串函数完成。-- 插入顶级评论A-- 因为此时还没生成id可以先插入数据再通过主键更新其pathBEGIN;INSERTINTOcomment_path(content,path)VALUES(评论A,);UPDATEcomment_pathSETpathCONCAT(/,LAST_INSERT_ID(),/)WHEREidLAST_INSERT_ID();COMMIT;-- 此时id1的记录path为 /1/-- 插入评论B回复评论A (已知评论A的id为1path为 /1/)BEGIN;INSERTINTOcomment_path(content,path)VALUES(评论B,);-- 假设业务系统已知父节点path则可直接插入 /1/2/-- 若在数据库中操作可用如下语句UPDATEcomment_pathSETpathCONCAT((SELECTpathFROM(SELECTpathFROMcomment_pathWHEREid1)ASp),LAST_INSERT_ID(),/)WHEREidLAST_INSERT_ID();COMMIT;-- 此时id2的记录path为 /1/2/-- 插入评论D回复评论BBEGIN;INSERTINTOcomment_path(content,path)VALUES(评论D,);UPDATEcomment_pathSETpathCONCAT((SELECTpathFROM(SELECTpathFROMcomment_pathWHEREid2)ASp),LAST_INSERT_ID(),/)WHEREidLAST_INSERT_ID();COMMIT;-- 此时id4的记录path为 /1/2/4/查询操作物化路径的查询高度依赖于字符串处理和LIKE操作。1查询某条评论的所有后代评论获取子树我们知道任何后代节点的路径必然以祖先节点的路径作为前缀。因此使用LIKE可以非常高效地查出所有子树并且由于匹配模式不以通配符%开头索引idx_path是可以被有效使用的。-- 查询评论A(id1)的所有后代评论-- 假设已知评论A的path是 /1/SELECTid,content,pathFROMcomment_pathWHEREpathLIKE/1/%ANDid!1;-- 排除自身2查询某条评论的直接子评论物化路径本身并不直接体现明确的层级关系属性虽然可以通过分隔符的数量推断。要查询直接子评论我们需要通过正则表达式或计算字符串中分隔符如/的数量来判断深度。例如如果节点 A 的path是/1/长度为 3包含 2 个/那么它的直接子节点的path中必然包含 3 个/。-- 查询评论A(id1, path/1/)的直接回复-- 原理计算字符串中 / 的数量减1即为深度。子节点深度 父节点深度 1SELECTid,content,pathFROMcomment_pathWHEREpathLIKE/1/%AND(LENGTH(path)-LENGTH(REPLACE(path,/,)))-1(LENGTH(/1/)-LENGTH(REPLACE(/1/,/,)));(注这种查询方式涉及函数计算无法走普通 B 树索引此时查询效率依赖于LIKE前缀过滤出的数据集大小。实际业务中为了避免这种情况有时会结合使用物化路径和邻接表即表里既有path也有parent_id字段。)3查询某条评论的所有祖先节点在数据库层面查询祖先节点相对费力。因为当前节点如id4, path/1/2/4/包含的是祖先 ID 组成的字符串。最常见的做法是将字符串传递到应用程序中例如 Java, Python按分隔符split拆解出一个 ID 数组[1, 2, 4]然后再发起一次数据库查询SELECTid,contentFROMcomment_pathWHEREidIN(1,2);如果不依赖应用程序单纯在 MySQL 中查询-- 查询评论D(id4, path/1/2/4/)的所有祖先-- 利用INSTR或LOCATE函数判断候选记录的path是否为目标记录path的子串SELECTid,content,pathFROMcomment_pathWHERELOCATE(path,/1/2/4/)1ANDid!4;删除操作删除操作在物化路径模型中非常便捷。与查询后代逻辑相同一条包含LIKE条件的 SQL 即可删除整棵子树。-- 删除评论B(id2, path/1/2/)及其所有后代DELETEFROMcomment_pathWHEREpathLIKE/1/2/%;3. 物化路径总结优点不需要额外的关系表表结构简单对于整棵树的读取或者子树的读取非常高效依托于主键或前缀索引通过解析单条记录的path字段不用查库就能在应用程序里知道其所有祖先层级关系。缺点严重依赖字符串操作在数据库层面进行字符串的解析和函数计算时性能不佳路径字段有长度限制如VARCHAR(255)这决定了树的最大深度是有限的如果更改了某一个节点的层级移动子树需要更新该节点及其所有后代节点的路径字符串开销极大。五、 三种方案景总结采用邻接表适用于大多数常规场景特别是当不需要频繁查询深层结构或者项目使用的是支持 CTE 功能的现代数据库如 MySQL 8.0 / PostgreSQL时。在评论系统中如果你通常只展示一到两层回复像 B 站的评论区主评论下直接扁平化展示所有回复邻接表是绝对的首选因为它结构最自然插入速度最快。采用闭包表适用于对读操作查询深度、子树性能要求极高且树层级可能会非常深的场景。由于查询过程仅需要常规的 JOIN 操作不需要数据库执行繁重的递归运算。但前提是你能够接受额外的空间消耗以及稍微复杂的插入逻辑。采用物化路径适用于树结构层级不太深且读多写少特别是极少发生“移动子树”的场景。在电商分类层级、文章分类目录中非常常见。对于评论系统来说也是一个不错的折中方案特别是在将路径解析工作交托给业务代码层之后能在单一维度里实现极高的查询效率。数据库方案的选择往往不是非黑即白的。有时可以将它们结合使用例如在同一个表中同时保留parent_id发挥邻接表的直查优势和path字段发挥物化路径的范围筛选优势通过空间换取全方位的查询时间优化从而满足复杂多变的业务需求。常见的方案还有“邻接表 冗余根节点”配合上逻辑删除既规避了邻接表的劣势又保留了完整的树形结构。具体就不拓展了实际开发中的应用往往是灵活多变的。
![华为OD机试2025C卷-字符串变换最小次数[100分]（ Java _ Python3 _ C++ _ C语言 _ JsNode _ Go）实现100%通过率](http://pic.xiahunao.cn/yaotu/华为OD机试2025C卷-字符串变换最小次数[100分]（ Java _ Python3 _ C++ _ C语言 _ JsNode _ Go）实现100%通过率)
![华为OD机试2025C卷-内存资源分配[100分]（ Java _ Python3 _ C++ _ C语言 _ JsNode _ Go）实现100%通过率](http://pic.xiahunao.cn/yaotu/华为OD机试2025C卷-内存资源分配[100分]（ Java _ Python3 _ C++ _ C语言 _ JsNode _ Go）实现100%通过率)
