c - 基数树的空间复杂度是多少？

Question

我一直关心基数树的空间使用情况，但我没有找到任何有用的讨论。

现在假设我们有一个与 linux radix-tree.c 相同的基数树实现，它采用一个整数并使用每 6 位来索引树中的下一个位置。我很容易想到基数树的空间使用量远远超过二叉搜索树的情况。如果我错了，请纠正我：

用例：(0,1,1,1,1), (1,1,1,1,1), (2,1,1,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内核中也使用它。

我错过了什么吗？谢谢。

score 8 · Accepted Answer

您要求空间复杂性，所以让我们解决它。

如果我们认为叶子上的非空指针是一个感兴趣的值，那么不难证明最坏的情况是一个完全填充的树，每个叶子节点都有一个值。

如果分支是 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 空间地址的最高位），则不会发生基数树的最坏情况存储行为.

score 1 · Accepted Answer

Linux 中的基数树最初是作为支持页面缓存的数据结构出现的，其中键（文件偏移）的这种分布并不常见。

（FWIW，最初的变体使用了 splay 树，但 Linus 拒绝了 :)

基数树又宽又浅，因此在其中的查找会访问相对较少的不同缓存行，这显然对性能非常有益。

它还具有页面缓存访问中的局部性意味着基数树节点访问中的局部性的属性，这与哈希表等替代设计不同。

score 0 · Accepted Answer

基数树用于保存具有公共/共享前缀的长字符串。在这种情况下，基数树将更加经济。

对于您指定的那种数据，情况就不同了。

编辑

带有前缀的长字符串的一个很好的例子是在您的计算机上存储所有带有完整路径的文件名。有了这样的数据，它将比其他方法更经济，并且可以非常快速地查找文件名是否存在。在某些情况下甚至可能比哈希表更快。

看看这两个文件：

它们的共享前缀是：“c:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\str”，只存储一次。

3 回答 3