在数据库中存储复合模式（分层数据）

Question

如何在关系型数据库中保存复合模式的“最佳实践”是什么？

我们一直在使用修改的先序树遍历（Modified Preorder Tree Traversal）。这很快地构建了整个树，但插入或删除新节点非常慢（所有左右值都需要调整）。此外，查询节点的子节点也不容易，而且很慢。

另一个我们注意到的问题是，你确实必须确保树不会变得混乱。你需要事务锁，否则左右值可能会损坏，修复损坏的左右树并不容易。

修改的先序树遍历确实非常好用，但我想知道是否有更好的替代方法。

- Lieven Cardoen

---

它有点取决于使用最多的查询类型。 - H H

Answer 1

虽然使用MPTT算法可以快速找到所有后代行，但查找所有子行可能会很慢。不过，您可以通过在表中添加一个parent_id字段来记录（是的，是冗余的）该行的父行，从而解决这个问题。然后搜索变为：

SELECT *
FROM tbl
WHERE parent_id = z

是的，parent_id 包含了冗余信息，可能会使您的表非规范化 -- 但由于任何插入/更新/删除已经需要全局更改，因此保持 parent_id 的最新状态并不需要太多额外的付出。您也可以使用一个记录行垂直级别的 level 字段，尽管在某些类型的转换下（例如将子树移动到树中的其他位置），这实际上更有可能发生变化。

普通的链接到父级表示法（即仅具有 parent_id 而没有 left_pos 或 right_pos）当然对于插入/更新密集的工作负载更快，但它只能有效地回答“查找 X 的父项”和“查找 X 的子项”这两个查询。大多数工作负载涉及的读取比写入要多得多，因此通常 MPTT 整体上更快 -- 但也许在您的情况下，您需要考虑移回到链接到父级？

- j_random_hacker

Answer 2

我听说在数据库中存储分层数据的最佳方法是使用字符串属性，其中内容是由冒号分隔的父级列表。

- tomjen