Good Overviews
(良好的概述)
Generally speaking, you're making a decision between fast read times (for example, nested set) or fast write times (adjacency list).
(一般来说,您要在快速读取时间(例如,嵌套集)或快速写入时间(邻接列表)之间做出决定。)
Usually, you end up with a combination of the options below that best fit your needs.(通常,您最终会得到以下最适合您的选项的组合。)
The following provides some in-depth reading:(下面提供一些深入的阅读:)
- One more Nested Intervals vs. Adjacency List comparison : the best comparison of Adjacency List, Materialized Path, Nested Set and Nested Interval I've found.
(嵌套间隔与邻接列表的另一个比较 :邻接列表,物化路径,嵌套集和嵌套间隔的最佳比较 。)
- Models for hierarchical data : slides with good explanations of tradeoffs and example usage
(分层数据模型 :幻灯片,其中对折衷和示例用法进行了很好的解释)
- Representing hierarchies in MySQL : very good overview of Nested Set in particular
(在MySQL中表示层次结构 :特别是对嵌套集的很好概述)
- Hierarchical data in RDBMSs : most comprehensive and well-organized set of links I've seen, but not much in the way of explanation
(RDBMS中的分层数据 :我见过的最全面,组织最完整的链接集,但解释方式不多)
Options
(选件)
Ones I am aware of and general features:
(我知道的和一般功能:)
- Adjacency List :
(邻接表 :)
- Columns: ID, ParentID
(列:ID,ParentID)
- Easy to implement.
(易于实现。)
- Cheap node moves, inserts, and deletes.
(廉价节点移动,插入和删除。)
- Expensive to find the level, ancestry & descendants, path
(昂贵的查找级别,祖先和后代,路径)
- Avoid N+1 via Common Table Expressions in databases that support them
(在支持N + 1的数据库中通过公用表表达式避免N + 1)
- Columns: ID, ParentID
- Nested Set (aka Modified Preorder Tree Traversal )
(嵌套集 (又名修改后的预排序树遍历 ))
- Columns: Left, Right
(列:左,右)
- Cheap ancestry, descendants
(廉价祖先,后裔)
- Very expensive
O(n/2)
moves, inserts, deletes due to volatile encoding(由于易失性编码,非常昂贵的
O(n/2)
移动,插入,删除)
- Columns: Left, Right
- Bridge Table (aka Closure Table /w triggers )
- Uses separate join table with: ancestor, descendant, depth (optional)
(使用单独的联接表,并带有:祖先,后代,深度(可选))
- Cheap ancestry and descendants
(便宜的祖先和后裔)
- Writes costs
O(log n)
(size of subtree) for insert, updates, deletes(写入成本
O(log n)
(子树的大小)以进行插入,更新,删除) - Normalized encoding: good for RDBMS statistics & query planner in joins
(标准化编码:适合联接中的RDBMS统计和查询计划程序)
- Requires multiple rows per node
(每个节点需要多行)
- Uses separate join table with: ancestor, descendant, depth (optional)
- Lineage Column (aka Materialized Path , Path Enumeration)
- Column: lineage (eg /parent/child/grandchild/etc...)
(栏:沿袭(例如/ parent / child / grandchild / etc ...))
- Cheap descendants via prefix query (eg
LEFT(lineage, #) = '/enumerated/path'
)(通过前缀查询的廉价后代(例如,
LEFT(lineage, #) = '/enumerated/path'
)) - Writes costs
O(log n)
(size of subtree) for insert, updates, deletes(写入成本
O(log n)
(子树的大小)以进行插入,更新,删除) - Non-relational: relies on Array datatype or serialized string format
(非关系:依赖于数组数据类型或序列化的字符串格式)
- Column: lineage (eg /parent/child/grandchild/etc...)
- Nested Intervals
(嵌套间隔)
- Like nested set, but with real/float/decimal so that the encoding isn't volatile (inexpensive move/insert/delete)
(类似于嵌套集,但具有实数/浮点数/十进制数,因此编码不会不稳定(廉价的移动/插入/删除))
- Has real/float/decimal representation/precision issues
(有实数/浮点数/小数表示/精度问题)
- Matrix encoding variant adds ancestor encoding (materialized path) for "free", but with added trickiness of linear algebra.
(矩阵编码变体为“自由”添加了祖先编码(物化路径),但增加了线性代数的技巧。)
- Like nested set, but with real/float/decimal so that the encoding isn't volatile (inexpensive move/insert/delete)
- Flat Table
(平面桌)
- A modified Adjacency List that adds a Level and Rank (eg ordering) column to each record.
(修改后的邻接表,将“级别”和“等级”(例如,排序)列添加到每个记录。)
- Cheap to iterate/paginate over
(便宜地迭代/分页)
- Expensive move and delete
(昂贵的移动和删除)
- Good Use: threaded discussion - forums / blog comments
(很好的用途:主题讨论-论坛/博客评论)
- A modified Adjacency List that adds a Level and Rank (eg ordering) column to each record.
- Multiple lineage columns
(多个谱系列)
- Columns: one for each lineage level, refers to all the parents up to the root, levels down from the item's level are set to NULL
(列:每个谱系级别都有一列,指的是直到根目录的所有父级,从项的级别向下的级别都设置为NULL)
- Cheap ancestors, descendants, level
(廉价祖先,后代,等级)
- Cheap insert, delete, move of the leaves
(便宜的插入,删除,移动叶子)
- Expensive insert, delete, move of the internal nodes
(内部节点的昂贵插入,删除,移动)
- Hard limit to how deep the hierarchy can be
(严格限制层次结构的深度)
- Columns: one for each lineage level, refers to all the parents up to the root, levels down from the item's level are set to NULL
Database Specific Notes
(数据库特定说明)
MySQL
(的MySQL)
Oracle
(甲骨文)
- Use CONNECT BY to traverse Adjacency Lists
(使用<a href="https://stackoom.com/link/aHR0cDovL