title: What's the space complexity of a radix tree?
body: <p>I've been always concerned with the space usage of a radix tree, but I didn't find any helpful discussions on this. </p>
  
  <p>Now let's say we have a radix tree implementation same as linux radix-tree.c, which takes a integer and use every 6 bits to index the next position in tree. I can easily think of cases where radix tree's space usage is far more than binary search trees. Please correct me if I'm wrong:</p>
  
  <p>Use cases: (0,1,1,1,1), (1,1,1,1,1), (2,1,1,1,1), ... (63,1,1,1,1). </p>
  
  <p>Here just for convenience, I use (a,b,c,d,e) to represent a 30-bit integer key, with each element standing for a 6-bit value. a is MSB and e is LSB. </p>
  
  <p><strong>Radix Tree:</strong></p>
  
  <p>For this use case, radix tree will have a height of 5, and each key will take 4 separate nodes, because they are on different subtrees of root. So there will be ((5-1) * 64 + 1) = 257 nodes.</p>
  
  <p>Each node contains 2^6 = 64 pointers, so it is going to use 257 * 64 * 4Byte = 65KB</p>
  
  <p><strong>Binary Search Tree</strong></p>
  
  <p>We only care how many keys are there. In this case it has 64 keys.</p>
  
  <p>Assume each BST node uses 3 Pointers per Node, it is going to use 64 * 3 * 4Byte = 768 Bytes.</p>
  
  <p><strong>Comparison</strong></p>
  
  <p>Looks radix tree is very space inefficient. It uses ~100 times space than binary search tree given same number of nodes! I don't understand why it is used even in linux kernel.</p>
  
  <p>Am I missing something? Thanks.</p>