在已知的限制Joe Celko的嵌套集(修改的预订遍历)中,随着树长到一个大的大小,性能显着降低.
Vadim Tropashko提出了嵌套间隔,并提供了本文的例子和理论解释：http://arxiv.org/html/cs.DB/0401014
这是一个可行的解决方案,是否有任何可行的示例(以任何语言)从本机DB层抽象出来？
解决方法
While I’ve seen examples for nested sets,我没有看到太多的嵌套间隔,虽然在理论上不应该是难以从一个转换到另一个.不要做预先遍历来标记节点,而是做广义优先递归.诀窍是找出最有效的方法来标注节点的子节点.由于a / b和c / d之间的节点是(ac)/(bd),所以插入错误的插入(例如将孩子从左到右插入)存在在索引值中产生相同指数增长的风险例如,使用完整的
materialized path.这不是很难抵消这种影响 – 一次创建一个新的索引,将每个索引插入到生成最小分母的位置.
就性能下降而言,很大程度上取决于您打算做的操作.仍然有一些操作需要完全重新整理整个树 – 嵌套集合或嵌套间隔方法对于很少更改的结构最有效.如果您对层次结构进行了大量的结构更改,那么“标准”父子表的结构可能会更容易使用.还要记住,与间隔方法相比,某些操作(如后代数量)比嵌套集合的整数标签容易得多.
