title: What prevents Van Emde Boas trees from being more popular in real-world applications?
body: <p>We know balanced trees perform insertion, deletion, and search in <em>O(log n)</em>-time, examples include</p>
  
  <ul>
  <li>Red-Black</li>
  <li>AVL</li>
  <li>Splay</li>
  <li>B-tree (and its variants).</li>
  </ul>
  
  <p>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 <em>O(log(log n))</em>-time, i.e., exponentially better than AVL or RB trees.
  Well, this is actually the case of many real world applications.</p>
  
  <p>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.</p>
  
  <p>Why Van Emde Boas tree is not widely used as say Red-Black or B-tree since</p>
  
  <ul>
  <li>it's not a novelty (it was invented in 1975)</li>
  <li>easy to implement</li>
  <li>way faster than other trees</li>
  </ul>
  
  <p>and what are the considerations about it?</p>