一. 导言 导言 导言 导言 导言 导言 一,导言 导言 导言 导言 导言 导言

在软件开发中,等级数据无处不在:线条评论、组织图表、文件系统、产品分类和论坛讨论。 “我如何将一棵树储存在关系数据库中? ”这个永恒的问题自SQL早期以来就一直有闹鬼的开发者,坦率地说,还没有一个答案让每个人都高兴。 早在2004年就首次写了一篇关于这个主题的文章。今天,基本挑战依然未变。

为何SQL的等级结构很困难

以下是基本问题: 关系数据库考虑的是各组,而不是树木正如乔·塞尔科在他的杰出著作中所解释的 以一组思考SQL 运行在整张表格上,而不是单行。

写入 SQL 查询时,数据库引擎运行在 一组行。 它在“ 找到超过 100 个订单” 或“ 加入客户购买” 等操作中非常出色, 这些操作是符合表格工作方式的固定操作。 结果总是一组平坦的行。

但等级制度是内在的 循环循环。要找到节点的所有子孙,您需要:

1. 寻找直系子女
2. 为每个孩子寻找 他们的 儿 儿 儿 儿 儿
3. 重复一遍,直到你穿过整个小树下

这个递归的十字路口无法自然地绘制操作的地图。 您无法在一个单一、 简单的 SQL 语句中表达“ 将所有子孙都交给我, 任何深度 ” 。

• 递递递 CTE (加上SQL:1999,但计算费用昂贵)
• 多次往返访问数据库数据库
• 预先计算关系的聪明的去正常化

这系列中的每一方法 都代表了一种不同的取舍 写复杂 读复杂 和存储管理费之间的取舍。没有免费的午餐 - 你总是以一个来换另一个。关于这个主题的精确参考,请参看Joe Celko的 SQL 中智能 SQL 中的树和层次它深入地涵盖了所有这些方针。

示例:串列注释

为了让比较具体化, 我们将使用线条评论作为我们运行中的范例, 博客使用的东西。 评论线索可能看起来是这样的:

flowchart TD
    subgraph Post["Post: How to Deploy Docker Containers"]
        C1["Comment 1: Great article!<br/>depth 0"]
        C2["Comment 2: Thanks!<br/>depth 1"]
        C3["Comment 3: Very helpful indeed<br/>depth 1"]
        C4["Comment 4: Agreed!<br/>depth 2"]
        C5["Comment 5: What about Kubernetes?<br/>depth 0"]
        C6["Comment 6: That's covered in part 2<br/>depth 1"]
    end

    C1 --> C2
    C1 --> C3
    C3 --> C4
    C5 --> C6

    style Post stroke:#10b981,stroke-width:2px
    style C1 stroke:#6366f1,stroke-width:2px
    style C2 stroke:#8b5cf6,stroke-width:2px
    style C3 stroke:#8b5cf6,stroke-width:2px
    style C4 stroke:#a855f7,stroke-width:2px
    style C5 stroke:#6366f1,stroke-width:2px
    style C6 stroke:#8b5cf6,stroke-width:2px

我们需要支持这些行动:

• 获取所有文章的备注@ option: group (保持线形结构)
• 把所有祖先都带走 批注( breadcrumb 线索)
• 把所有后代都带走 以便他们记诵,
• 添加新注释 (作为对现有评论的答复)
• 删除子树 (撤回评论和所有答复)
• 移动子树 (保留评论 -- -- 少见,但有时需要)

五方针方针

每种办法都在其自己的条款中详细论述。

---

1. 相邻人名单(父母参考资料)

阅读整条

最简单和最直观的方法。 每排都存储其父节点的引用。 这是大多数开发者最先达到的目标, 因为它自然地绘制了我们如何看待等级的地图。

如何运作: 每条评论均无效 ParentCommentId 。根条注释有NULL,答复指向他们的父。

最佳用于: 浅层次( 低于 5-6 级) , 经常的子树移动, 当您想要 EF Core 的导航特性自然工作时 。

权衡: 获取祖先或后代需要再生CTE或多个查询。 简单写作,读深树可能缓慢。

---

2. 闭幕表

阅读整条

预估并保存每个祖先- 后代的关系。 我们不是在查询时找到关系, 而是用深度来明确存储关系 。

如何运作: A 单独单独 CommentClosure 每对配对的表格仓库( 祖先_ id, 后裔_ id, 深度) 。 评注1下通过评注3提出的第 4 条评注将包含以下条目:( 1 4 4 2), ( 3 4 1), (4 4 0) 。

最佳用于: 当您在任意深度需要查询时, 当您很少移动子树时, 使用重读应用程序 。

权衡: 更复杂的插入(必须添加关闭条目),储存随着深度的增加而增加,移动亚树需要重建关闭。

---

3. 定点路径

阅读整条

将完整的祖先储存为定界的字符串。 把它视为存储完整的邮政地址, 而不仅仅是街道名称 。

如何运作: 每条评论都有: Path 类似“ 1/3/ 7” 的列表示“ 根为 1, 父为 1, 父为 3, 这是 7 ” 。 祖先可以从字符串中解析; 后代也可以通过类似查询找到 。

最佳用于: 面包屑一代,当祖先比后代受到更多询问时, 当你想要人类可以读取的调试路径时。

权衡: 没有正确的索引,查询会很慢,路径字符串有长度限制,移动子树需要更新所有后代路径。

---

4. 括号套件

阅读整条

从深度第一穿行中指定每个左节点和右边边界编号。 所有子孙都有价值 之间 父母的界限。

如何运作: 每项评论的评论和评论 Left 和 Right 值为 L=4, R=7的节点包含所有节点,其中4 < 左右 < 7 以简单范围查询方式发现后代。

最佳用于: 阅读重, 写出非常罕见的情景, 如分类树。 极适合“ 将整个子树排列为显示顺序” 查询 。

权衡: 插入需要更新许多行( 将全部值转换为空格) , 移动子树是复杂的 。 不适合经常写入 。

---

5. PostgreSQL ltree

阅读整条

PostgreSQL 本地的等级数据扩展。 类似已实现路径, 但数据库级别优化和强力模式匹配 。

如何运作: 用途和用途 ltree “1.3.7”等路径的数据类型。 GST 索引能够使用诸如“1.3.7”等操作员有效查询祖先/后代。 @> 和 <@.

最佳用于: PostgreSQL - 仅适用于性能很重要的部署, 需要模式匹配查询时, 需要最佳实际路径时 。

权衡: 仅 PostgreSQL , 添加数据库扩展依赖性。 注意: The Npgsql 服务提供商支持 LINQ 翻译 树的树,因树的果实,因树的果实和树的果实,因树的果实和树的果实, LTree 类型,尽管循环 CTE仍然需要原始 SQL 。

---

比较比较摘要

|----------|--------|---------------|-----------------|--------------|---------|-----------------| | 相邻名单 O(1) O(n) 与 CTE O(d) 和 CTE O(1) | 结束日期表 O(d) O(1) O(1) O(1) O(s x d) O(n x d) Good | 定文件路径 * O(1) * O(1) * O(1)* * O(1) O(s) * O(d) / 节点 * 好 * | 嵌套套套 O(n) O(1) O(1) O(n) | 树树 * O(1) O(1) O(1) O(1) * O(s) * O(d) * 每一个节点 * 好 (通过) LTree 类型)

n = 总节点,d = 深度,s = 亚树大小 *使用正确的索引

决策流程图

flowchart TD
    Start([Start]) --> Q1{Shallow tree?<br/>< 5 levels}
    Q1 -->|Yes| Q2{Need EF Core<br/>navigation properties?}
    Q2 -->|Yes| AL[Adjacency List]
    Q2 -->|No| Q3{Performance<br/>critical?}
    Q3 -->|No| AL
    Q3 -->|Yes| MP[Materialised Path]

    Q1 -->|No| Q4{Read-heavy?}
    Q4 -->|Yes| Q5{Writes rare?}
    Q5 -->|Yes| NS[Nested Sets]
    Q5 -->|No| CT[Closure Table]

    Q4 -->|No| Q6{PostgreSQL only?}
    Q6 -->|Yes| LT[ltree]
    Q6 -->|No| Q7{Need breadcrumbs?}
    Q7 -->|Yes| MP
    Q7 -->|No| CT

    style Start stroke:#10b981,stroke-width:2px
    style AL stroke:#6366f1,stroke-width:2px
    style MP stroke:#8b5cf6,stroke-width:2px
    style NS stroke:#ec4899,stroke-width:2px
    style CT stroke:#f59e0b,stroke-width:2px
    style LT stroke:#14b8a6,stroke-width:2px

真实世界的选择:这个博客

这个博客使用 结束日期表 理由:

1. 阅读意见的次数远多于书面
2. 我们需要高效显示嵌套的批注线索
3. 深度限制查询对业绩很重要(我们上限为5级深)
4. 提出进取意见的情况很少(调节器偶尔需要这样做)

见见 第1.2部分:最后表格 的完整执行细节。

系列导航

• 第1部分:概览 (本条)
• 第1.1部分:相邻清单 - 简单父参考书
• 第1.2部分:最后表格 - 预计关系
• 第1.3部分:具体路径 - 路径字符串
• 第1.4部分:内嵌套件 - 左/右边界
• 第1.5部分:树 - PostgreSQL本地扩展
• 第2部分:Raw SQL和Dapper(即将推出)