Joe Celko 的嵌套集（修改的前序遍历）的已知限制之一是随着树增长到较大的大小，性能会显着下降。
Vadim Tropashko 提出了嵌套区间，并在本文中提供了示例和理论解释：http: //arxiv.org/html/cs.DB/0401014
这是一个可行的解决方案吗，是否有任何可行的示例（以任何语言）从本地 DB 层抽象出来？
问问题
5691 次
2 回答
7
虽然我已经看到了嵌套集的示例，但我并没有看到太多关于嵌套区间的示例，尽管理论上从一种转换到另一种应该不难。与其进行前序遍历来标记节点，不如进行广度优先递归。诀窍是找出标记节点的 n 个子节点的最有效方法。由于 a/b 和 c/d 之间的节点是 (a+c)/(b+d)，因此病态插入（例如，从左到右插入子节点）存在创建相同指数增长的风险在索引值中，例如，使用完整的物化路径。抵消这种影响并不难 - 一次创建一个新索引，将每个索引插入到产生最低结果分母的位置。
就性能下降而言，很大程度上取决于您打算执行的操作。仍然有一些操作需要对整个树进行完全重新标记 - 嵌套集或嵌套间隔方法都最适合很少更改的结构。如果您要对层次结构进行大量结构更改，则“标准”父子表结构可能更易于使用。还要记住，使用嵌套集的整数标记比区间方法更容易一些操作（例如后代的数量）。
于 2008-12-12T21:32:48.087 回答
1
我编写了一个 gem，它抽象出所有嵌套间隔的计算，以便与 Rails 的 ActiveRecord https://github.com/clyfe/acts_as_nested_interval/在多个系统的生产中使用。
于 2012-09-25T23:36:06.663 回答