什么阻止Van Emde Boas树在现实世界的应用中更受欢迎？ [英] What prevents Van Emde Boas trees from being more popular in real-world applications?

问题描述

我们知道平衡树在 O（log n） -time中执行插入，删除和搜索，示例包括

We know balanced trees perform insertion, deletion, and search in O(log n)-time, examples include

• 红黑


• AVL


• Splay


• B树（及其变体）

• Red-Black
• AVL
• Splay
• B-tree (and its variants).

但是，当键在一定范围内是整数时，可以使用Van Emde Boas树将这些操作放下到（o）（log（log n）） -time，即比AVL或RB树指数更好。
嗯，这实际上是许多现实世界的应用程序的情况。

However, when keys are integers in some limited range, it is possible to use a Van Emde Boas tree to drop these operations down to O(log(log n))-time, i.e., exponentially better than AVL or RB trees. Well, this is actually the case of many real world applications.

我看到很多应用程序。
我想引用的一个是数据库，创建索引基本上涉及在Hash或B * -tree之间进行选择。
如果实施了Van Emde Boas树，它将提供这两个选项之间的一半，理论上改进了许多查询优化问题。

I see lots of applications for this. One I'd like to cite is on databases, for which creating indexes basically involves choosing between a Hash or a B*-tree. If a Van Emde Boas tree was implemented, it would provide a halfway between these two options, theoretically improving many query optimization problems.

为什么选择Van Emde Boas树由于

Why Van Emde Boas tree is not widely used as say Red-Black or B-tree since

• 这不是一个新奇事物（这是1975年发明的），所以不像红黑或B树一样广泛使用


• 容易实现


• 方式比其他树更快

有什么注意事项？

推荐答案

渐近的复杂性有时是误导性的。在 Van Emde Boas树的情况下，常量相当大请参阅我引用：

The asymptotic complexity is sometimes misleading. In the case for Van Emde Boas tree the constant is quite large see here. I quote:

However, for small trees the overhead associated with vEB trees
is enormous: on the order of 2^(m/2)

还有其他情况下，存在更好复杂性的算法，但只有更好的输入如此之大，实际上几乎从未使用过线性时间静态RMQ。

There are also other cases where an algorithm with better complexity exists but it only gets better for an input so big that in practice it is almost never used e.g. linear time static RMQ.

这篇关于什么阻止Van Emde Boas树在现实世界的应用中更受欢迎？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！