多列b树索引的复杂性

Question

根据 Sebastian Brestin 的一篇文章，多列 B 树索引将如下所示。 似乎更多的列并不能创建更深的 B 树。因此，如果单列（

n

条目）b树索引具有搜索/插入/更新复杂度：

O(log(n))

和空间复杂度：

O(n)

，则

m

列（

n

条目）b -树索引也有搜索/插入/更新复杂度：

O(log(m*n))

和空间复杂度：

O(m*n)

？

PS：如果数据库供应商很重要，我想了解 PostgreSQL。

Answer 1

是的，如果您有一个 composite 键，其中每个成员具有相同的数据类型（使用相同的空间量），那么您会认为一个（复合）键使用的空间是 O(𝑚)，在最坏的情况下，关键比较的时间复杂度为 O(𝑚)。

如果 𝑚 是一个常数，那么通常的时间复杂度为 O(log𝑛) ，空间复杂度为 O(𝑛)。对于动态确定的 𝑚（当然，对于给定的 B 树，固定），您可以在这些表达式中将 𝑛 替换为 𝑛𝑚：O(log𝑚𝑛) 和 O(𝑚𝑛)。