database - 数据库中 B 树索引的空间复杂度

Question

传统的 B 树实现具有 O(n) 空间复杂度 [ 1 ]。

所以假设在一个数据库中（不管实现，只考虑一般情况），我有一个 10GB 数据的表，目前索引大小是 1GB，那么我可以假设如果数据库增长到 100GB，我的索引大小将是 10GB？

Answer 1

你不能说任何“不管实施”。

如果索引是纯B树，那么理论上应该在被索引的键的数量和大小上与填充率的一些软糖因素成线性关系。但是，它不太可能是纯 B 树。首先，它可能是 B+树或其他一些变体。B+tree 会在大小计算中添加一个非常小的对数项。这种增长不太可能是实质性的。更重要的是，大多数实现都没有实现理论上的 B-tree 操作来维持填充率。例如，删除可能只通过留下一个开放的插槽供以后的插入使用来实现。在大量的操作和运气不好的情况下，索引表示的效率可能会降低，因此索引可能会变得更大。如果您在 10GB 上的索引是紧凑的，而您的 100GB 是经过一年的操作，它可能会比您预期的要大。

直接回答您的问题-不，我认为您的假设不安全。更多是因为索引可能会随着时间的推移而改变大小，而不是由于底层数据结构中的非线性。