我一直关注基数树的空间使用情况，但我没有发现任何有用的讨论。
现在假设我们有一个与linux基数树.c相同的基数树实现，它取一个整数，并使用每6位来索引树中的下一个位置。我很容易想到基数树的空间使用量远远超过二进制搜索树的情况。如果我错了，请纠正我：
使用案例：（0,1,1,1,1），（1,1,1,1,11），（2,1,11,1,1）。。。（63,1,1,1,1）。
这里只是为了方便起见，我使用（a，b，c，d，e）来表示一个30位的整数键，每个元素代表一个6位的值。a是MSB，e是LSB。
根树：
对于这个用例，基数树的高度为5，每个键将具有4个独立的节点，因为它们位于根的不同子树上。因此将存在（（5-1）*64+1）=257个节点。
每个节点包含2^6=64个指针，因此它将使用257*64*4Byte=65KB
二进制搜索树
我们只在乎有多少把钥匙。在这种情况下，它有64个键。
假设每个BST节点每个节点使用3个指针，它将使用64*3*4Byte=768字节。
比较
看起来基数树的空间效率很低。在相同节点数的情况下，它使用的空间是二进制搜索树的约100倍！我不明白为什么它甚至在linux内核中使用。
我是不是错过了什么？谢谢
您询问了空间复杂性，让我们来解决它。
如果我们认为叶上的非空指针是感兴趣的值，那么不难矛盾地证明最坏的情况是每个叶节点有一个值的完全填充树。
如果分支是N向（在用例64中），高度是H（在用例5中），则该树中有N^（H-1）个叶节点，存储相同数量的值。节点总数为
1 + N + N^2 + ... N^(H-1) = (N^H - 1) / (N-1)
因此，以指针为单位测量的存储需求是这个数量的N倍。
(N^H - 1) [N / (N-1)]
这产生的存储效率
(N^H - 1) [N / (N-1)]
--------------------
N^(H-1)
这是指针总数除以有效数据指针的计数。
当N变大时，它接近N。在您的示例用例中，它实际上是65.01（对于N=64）。因此，我们可以说存储复杂性是O（NV），其中V是要存储的数据值的数量。
尽管我们在这里进行了第一性原理分析，但它完全有意义。整棵树的叶级存储量占其余存储量的比例接近N。该存储量的大小为NV。
当然，像这样具有巨大分支因子的树（例如数据库中的B树）的优点是，需要更少的节点遍历才能找到正确的叶子。
此外，当每次遍历都是像基数树中那样的单个数组查找时，速度不会快得多。
在您的用例中，一个完全平衡的二进制搜索树将需要多达30个比较，伴随的分支将刷新管道。与5个数组索引操作相比，这可能要慢得多。数组索引往往比比较更快，因为它是非分支代码。但是，即使它们是相同的，二进制树也只需要2^5=32个元素，就可以产生与包含2^30个元素的基数树相同的索引工作量。
为了推广这一点，如果键比较和数组索引操作具有相同的成本，则2^H元素的二叉树将需要与能够容纳N^（H-1）元素的索引树相同的查找工作。
正如其他人所说，如果树的顶层的索引位倾向于几个常见前缀（即，它们是同一VM空间的地址的顶层），则不会发生基数树的最坏情况存储行为。
Radix树被大量使用，其中包含带有公共/共享前缀的长字符串。在这种情况下，基数树将更加经济。
对于您指定的数据类型，情况就不一样了。
编辑
带前缀的长字符串的一个很好的例子是在计算机上存储所有带完整路径的文件名。有了这样的数据，它将比其他选择更经济，并且可以非常快速地查找文件名是否存在。在某些情况下甚至可能比哈希表更快。
看看这两个文件：
- "c:\Program Files（x86）\Microsoft Visual Studio 12.0\VC\include\streambuf"
- "c:\Program Files（x86）\Microsoft Visual Studio 12.0\VC\include\string"
它们的共享前缀是："c:\Program Files（x86）\Microsoft Visual Studio 12.0\VC\include\str"，只存储一次。
Linux中的基数树最初是作为支持页面缓存的数据结构出现的，在页面缓存中，这样的密钥分布（文件偏移量）并不常见。
（FWIW，最初的变体使用了一棵八字树，但Linus拒绝了：）
基数树又宽又浅，因此在其中进行查找可以访问相对较少的不同缓存行，这显然对性能非常有利。
它还具有页面缓存访问的局部性意味着基数树中的局部性的特性节点访问，不同于哈希表之类的替代设计。