data-structures - 是什么阻止了 Van Emde Boas 树在实际应用中更受欢迎？

Question

我们知道平衡树在 O(log n) 时间内执行插入、删除和搜索，示例包括

红黑

AVL

展开

B 树(及其变体)。

但是，当键是某个有限范围内的整数时，可以使用 Van Emde Boas 树将这些操作降低到 O(log(log n)) 时间，即比 AVL 或 RB 树呈指数级好。
嗯，这实际上是许多现实世界应用程序的情况。

我看到很多这方面的应用。
我想引用的一个是数据库，为此创建索引基本上涉及在哈希或 B* 树之间进行选择。
如果实现了 Van Emde Boas 树，它将介于这两个选项之间，理论上可以改善许多查询优化问题。

为什么 Van Emde Boas 树没有像红黑树或 B 树那样被广泛使用，因为

这不是什么新鲜事(它发明于 1975 年)

易于实现

比其他树快得多

对此有何考虑？

Answer 1

渐近复杂性有时会产生误导。在 Van Emde Boas tree 的情况下常数相当大see here .我引用:

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

还有其他一些情况，其中存在具有更好复杂性的算法，但它只会在输入如此之大以至于实际上几乎从未使用过的情况下变得更好，例如线性时间静态 RMQ。