无限深度章节树如何一遍建成？路径编码+单调栈

无限深度章节树如何一遍建成路径编码单调栈问题背景在文档解析场景中我们拿到的是一份扁平的文本流——段落、表格、图片、章节标题混杂在一起顺序排列。但用户最终需要的是一棵结构清晰的章节树第一章下有1.1、1.2节1.1节下可能还有更细的小节。核心挑战是如何在遍历一遍文本流的过程中把这棵树建出来最直观的想法是递归遇到章节标题递归处理其子内容。但文档可能有几十层深度递归的调用栈不可控。另一种想法是存储冗余字段在每个节点存level字段表示它的层级深度。但层级变了所有子节点的level都要更新维护成本高。我们最终采用的方案是路径编码 单调栈。两个算法配合一遍遍历完成建树查询效率 O(1)层级信息可推导无需存储。数据结构设计节点实体/** * 章节节点实体 * 存储id, documentId, parentId, title, path * 不存储level由 path 推导 */ public class ChapterNode { /** 主键 ID */ private Long id; /** 关联文档 ID */ private String documentId; /** 父节点 ID0 表示根节点 */ private Long parentId; /** 章节标题 */ private String title; /** 可排序路径如 /1/2/3 */ private String path; /** 内容哈希用于增量更新检测 */ private String contentHash; /** 状态pending/processing/done */ private String status; /** 章节来源类型 */ private String chapterSource; /** 删除标记0-未删除1-已删除 */ private Integer deleted; // createTime, updateTime 等时间字段省略... }关键设计决策字段存储策略原因level不存储由path.split(/).length - 1推导path存储层级信息载体支持排序和前缀查询parentId存储快速定位父节点双保险算法一路径编码设计思路路径格式父路径 / 序号/ → 根节点 /1 → 根节点下的第1个章节 /2 → 根节点下的第2个章节 /1/1 → /1 的第1个子章节 /1/2 → /1 的第2个子章节 /1/1/1 → /1/1 的第1个子章节路径生成代码/** * 创建章节节点 * * param documentId 文档 ID * param header 章节标题项来自解析器 * param ancestorStack 祖先栈单调栈 * param nodeIndex 节点序号计数器全局递增 * return 章节节点实体 */ private ChapterNode createChapterNode(String documentId, SectionHeaderItem header, DequeChapterNode ancestorStack, int[] nodeIndex) { // 1. 生成章节路径 // 格式父路径 / 序号 // 例如/ / 1 /1 // /1 / 2 /1/2 String path null; if (ancestorStack.peek() ! null) { path ancestorStack.peek().getPath() / nodeIndex[0]; } // 2. 获取父节点 ID Long parentId null; if (ancestorStack.peek() ! null) { parentId ancestorStack.peek().getId(); } // 3. 使用 Builder 创建节点 return ChapterNode.builder() .documentId(documentId) .parentId(parentId) .title(header.getText()) .path(path) .status(PENDING) .deleted(0) .build(); }为什么这样设计1. 唯一标识每个节点有唯一路径即使标题相同路径也不同。2. 层级可推导/** * 从 path 推导层级深度 * * param path 章节路径格式/1/2/3 * return 层级深度从 0 开始 * * 示例 * - / → 0根节点 * - /1 → 1 * - /1/1 → 2 * - /1/1/1 → 3 */ public static int calculateLevel(String path) { if (path null || path.isEmpty() || path.equals(/)) { return 0; } // 统计 / 分隔后的段数减去开头的空段 return path.split(/).length - 1; }3. 排序友好路径字典序 文档阅读顺序。查询直接ORDER BY path。4. 子树查询高效-- 查询某章节的所有子孙 SELECT * FROM chapter_node WHERE document_id ? AND path LIKE /1/% AND deleted 0; -- 查询某章节的直接子节点 SELECT * FROM chapter_node WHERE document_id ? AND parent_id ? AND deleted 0;算法二单调栈设计思路遍历文本流时章节标题可能随时跳层级。单调栈的设计目标栈中始终保存从根到当前章节的完整祖先链。核心实现/** * 更新祖先栈单调栈维护 * * 规则 * 1. 栈顶层级 新章节层级 → 不弹出新章节是栈顶的子章节 * 2. 栈顶层级 ≥ 新章节层级 → 弹出新章节是栈顶的兄弟或叔叔 * 3. 栈大小 1 → 停止保留根节点 * * param stack 祖先栈 * param newChapter 新章节节点 */ private void updateAncestorStack(DequeChapterNode stack, ChapterNode newChapter) { // 1. 计算新章节的层级 int currentLevel calculateLevel(newChapter.getPath()); // 2. 循环弹出层级 ≥ 新章节的节点 while (stack.size() 1) { // 保留根节点 ChapterNode top stack.peek(); int topLevel calculateLevel(top.getPath()); if (topLevel currentLevel) { // 弹出新章节是栈顶的兄弟或更低层级 stack.pop(); } else { // 找到正确的父节点 break; } } // 3. 新章节入栈 stack.push(newChapter); }完整遍历流程/** * 从 DoclingDocument 持久化章节树 * * param documentId 文档 ID * param doclingDocument Docling 解析结果 * param chapterSource 章节来源 */ public void persistFromDocling(String documentId, DoclingDocument doclingDocument, String chapterSource) { // 1. 删除旧数据幂等 chapterNodeService.deleteByDocumentId(documentId); // 2. 创建根节点 ChapterNode root createRootNode(documentId, chapterSource); chapterNodeService.insert(root); // 3. 初始化遍历变量 DequeChapterNode ancestorStack new LinkedList(); ancestorStack.push(root); // 根节点入栈 ChapterNode currentChapter null; // 当前章节用于累积文本 StringBuilder currentText new StringBuilder(); // 文本累积器 int[] nodeIndex {1}; // 全局节点计数器 int[] blockOrder {1}; // 内容块顺序 // 4. 遍历文本流 for (BaseTextItem item : doclingDocument.getTexts()) { // 跳过非 BODY 层 if (item.getContentLayer() ! ContentLayer.BODY) { continue; } // 处理章节标题 if (item instanceof SectionHeaderItem header) { // 保存上一个章节的文本内容块 if (currentChapter ! null !currentText.isEmpty()) { saveTextBlock(currentChapter.getId(), currentText.toString(), blockOrder[0]); } // 创建新章节节点 currentChapter createChapterNode(documentId, header, ancestorStack, nodeIndex); chapterNodeService.insert(currentChapter); // 更新单调栈 updateAncestorStack(ancestorStack, currentChapter); // 重置文本累积器 currentText new StringBuilder(); } else { // 累积普通文本段落、表格等 String text item.getText(); if (text ! null !text.isEmpty()) { if (currentText.length() 0) { currentText.append(\n); } currentText.append(text); } } } // 5. 保存最后一个章节的内容块 if (currentChapter ! null currentText.length() 0) { saveTextBlock(currentChapter.getId(), currentText.toString(), blockOrder[0]); } }运行示例文档结构根节点 (level 0) ├── 第一章 (level 1) │ ├── 1.1 节 (level 2) │ └── 1.2 节 (level 2) └── 第二章 (level 1)栈的变化过程初始[根/] 遇到第一章 level1 栈顶 level0 1 → 不弹出 入栈 → [根/, 第一章/1] 遇到1.1节 level2 栈顶 level1 2 → 不弹出 入栈 → [根/, 第一章/1, 1.1节/1/1] 遇到1.2节 level2 栈顶 level2 ≥ 2 → 弹出 1.1节 栈顶 level1 2 → 停止 入栈 → [根/, 第一章/1, 1.2节/1/2] 遇到第二章 level1 栈顶 level2 ≥ 1 → 弹出 1.2节 栈顶 level1 ≥ 1 → 弹出 第一章 栈顶 level0 1 → 停止 入栈 → [根/, 第二章/2]关键点栈顶永远是正确的父节点peek()即可O(1) 复杂度。算法三层级推导实现代码/** * 计算章节层级 * 独立工具方法可在任意位置调用 */ public static int calculateLevel(String path) { if (path null || path.isEmpty() || path.equals(/)) { return 0; } return path.split(/).length - 1; } /** * 在聚合对象中按需计算层级 */ public class ChapterAggregate { private ChapterNode node; /** * 动态获取层级不存储 */ public Integer getLevel() { if (node ! null node.getPath() ! null) { return calculateLevel(node.getPath()); } return null; } }为什么不存储 level 字段问题说明数据冗余level 已编码在 path存两份浪费更新传播移动节点需改 path level子节点也要改一致性风险path 和 level 可能不一致多一个出错点不存储的好处好处说明单一数据源层级只存在于 path无不一致可能移动简单只改 path 和 parentId其他推导计算成本低split在短字符串上极快简要数据库表结构CREATE TABLE chapter_node ( id BIGINT PRIMARY KEY AUTO_INCREMENT, document_id VARCHAR(64) NOT NULL COMMENT 文档ID, parent_id BIGINT DEFAULT 0 COMMENT 父节点ID0表示根节点, title VARCHAR(512) COMMENT 章节标题, path VARCHAR(255) NOT NULL COMMENT 可排序路径如/1/2/3, content_hash VARCHAR(64) COMMENT 内容SHA256哈希, status VARCHAR(32) DEFAULT PENDING COMMENT 状态, chapter_source VARCHAR(64) COMMENT 章节来源类型, deleted TINYINT DEFAULT 0 COMMENT 删除标记, create_time DATETIME DEFAULT CURRENT_TIMESTAMP, update_time DATETIME ON UPDATE CURRENT_TIMESTAMP, INDEX idx_document_id (document_id), INDEX idx_parent_id (parent_id), INDEX idx_path (path) ) COMMENT 章节节点表;索引设计索引用途idx_document_id按文档查询章节树idx_parent_id查询直接子节点idx_path前缀查询子树、排序复杂度分析时间复杂度操作复杂度说明建树O(n)一遍遍历每个节点常数时间获取父节点O(1)栈顶peek()计算层级O(k)k 是路径深度通常 10子树查询O(1)*LIKE 查询索引命中空间复杂度数据结构复杂度说明单调栈O(h)h 是最大层级深度与节点数无关路径存储O(h)每节点存一个路径字符串方案对比方案建树查询父节点存储维护递归O(n) 不可控需回溯无中存 levelO(n)O(1)level 字段高更新传播路径编码单调栈O(n) 可控O(1)无低总结这套算法组合的核心价值一遍遍历建树O(n) 时间每个节点只进出栈一次O(1) 获取父节点栈顶永远是对的无需回溯无冗余存储层级推导计算不占字段任意层级支持不用预知最大深度动态调整查询友好路径支持前缀匹配子树查询一条 SQL设计选择本质上是权衡。我们选择用路径字符串承载层级信息换取查询效率和维护简便。这套方案在文档解析场景表现稳定十层深的章节树也能高效处理。