好的概述
一般来说,您要在快速读取时间(例如,嵌套集)或快速写入时间(邻接列表)之间做出决定.通常,您最终会得到最适合您需求的以下选项组合.以下提供了一些深入阅读:
选项
我知道和一般的功能:
- 邻接清单:
- 列:ID,ParentID
- 易于实施.
- 便宜节点移动,插入和删除.
- 昂贵的找到水平,血统和后代,路径
- 在支持它们的数据库中通过公用表表达式避免使用N + 1
- 嵌套集(又名修改的预订树遍历)
- 列:左,右
- 便宜的血统,后代
- 非常昂贵的
O(n/2)移动,插入,由于易失性编码而删除
- 桥表(又名闭包表/ w触发器)
- 使用单独的连接表:祖先,后代,深度(可选)
- 廉价的血统和后代
- 写入
O(log n)插入,更新,删除的成本(子树的大小)
- 规范化编码:适用于连接中的RDBMS统计信息和查询规划器
- 每个节点需要多行
- 谱系列(又名物化路径,路径枚举)
- 专栏:血统(例如/父母/孩子/孙子/等......)
- 廉价后代通过前缀查询(例如
LEFT(lineage, #) = '/enumerated/path')
- 写入
O(log n)插入,更新,删除的成本(子树的大小)
- 非关系型:依赖于Array数据类型或序列化字符串格式
- 嵌套间隔
- 像嵌套集一样,但是使用实数/浮点数/小数,这样编码就不易变(廉价的移动/插入/删除)
- 有实/浮/十进制表示/精度问题
- 矩阵编码变体为"自由"添加了祖先编码(物化路径),但增加了线性代数的诡计.
- 平表
- 修改的Adjacency List,为每条记录添加Level和Rank(例如排序)列.
- 便宜迭代/分页
- 昂贵的移动和删除
- 好用:线程讨论 - 论坛/博客评论
- 多个谱系列
- 列:每个谱系级别一个,指向根目录的所有父级,从项目级别向下的级别设置为NULL
- 便宜的祖先,后代,水平
- 便宜的插入,删除,移动的叶子 …