嵌套间隔是嵌套集（修改的预订遍历）RDBMS性能降级的可行解决方案吗？ [英] Are nested intervals a viable solution to nested set (modified pre-order traversal) RDBMS performance degredation?

问题描述

在Joe Celko的嵌套集（已修改的预订遍历）的已知限制中，随着树生长到大尺寸，性能会显着降低。

Among the known limitations of Joe Celko's nested sets (modified pre-order traversal) is marked degredation in performance as the tree grows to a large size.

Vadim Tropashko提出嵌套间隔，并在本文中提供示例和理论解释： http://arxiv.org/ html / cs.DB / 0401014

Vadim Tropashko proposed nested intervals, and provides examples and theory explanation in this paper: http://arxiv.org/html/cs.DB/0401014

这是一个可行的解决方案，有没有可行的例子（任何语言）从本机DB层抽象？

Is this a viable solution, are there any viable examples (in any language) abstracted away from the native DB layer?

推荐答案

虽然我已经看到嵌套集合的例子，我没有看到太多的嵌套间隔，虽然在理论上不应该难以从一个转换到另一个。代替执行预订遍历以标记节点，执行广度优先递归。诀窍是找出一种标记节点的n个子节点的最有效的方法。由于a / b和c / d之间的节点是（a + c）/（b + d），病态条件插入（例如，从左到右插入子节点）运行产生相同指数生长的风险在索引值中，例如，使用完整的实现路径。要抵消这种影响是不难的 - 一次创建一个新索引，将每个索引插入到产生最小分母的位置。

While I've seen examples for nested sets, I haven't seen much for nested intervals, although in theory it shouldn't be difficult to convert from one to the other. Instead of doing pre-order traversal to label the nodes, do a breadth-first recursion. The trick is to work out the most efficient way of labelling n children of a node. Since the node between a/b and c/d is (a+c)/(b+d), an ill-conditioned insert (for instance, inserting the children left to right), runs the risk of creating the same exponential growth in the index values as, for instance, using a full materialized path. It is not difficult to counteract this effect - create the new indexes one at a time, inserting each at the location that produces the lowest resulting denominator.

就性能降级而言很大程度上取决于你打算做的操作。还有一些操作将需要整个树的完全重新标记 - 嵌套集合或嵌套间隔方法对于很少改变的结构最有效。如果您对层次结构进行了大量的结构更改，那么标准父子表结构可能更容易使用。记住，对于嵌套集合的整数标注，间隔方法的某些操作（例如子孙数）要容易得多。

As far as performance degradation goes, much depends on the operations you intend to do. There are still some operations that will require a complete relabeling of the entire tree - the nested set or nested interval methods both work best for structures that seldom change. If you are doing a lot of structure changes to the hierarchy, the 'standard' parent-child table structure may be easier to work with. remember too that some operations (such as number of descendants) are far easier with the integer labeling of nested sets than the interval methods.

这篇关于嵌套间隔是嵌套集（修改的预订遍历）RDBMS性能降级的可行解决方案吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！