We know balanced trees perform insertion, deletion, and search in O(log n)-time, examples include
- Red-Black
- AVL
- Splay
- B-tree (and its variants).
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.
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.
Why Van Emde Boas tree is not widely used as say Red-Black or B-tree since
- it's not a novelty (it was invented in 1975)
- easy to implement
- way faster than other trees
and what are the considerations about it?