PostgreSQL中多列B-tree索引的复杂度疑问

核心结论 #

• 查询/插入/更新复杂度：O(log(n))，并非O(log(m*n))
• 空间复杂度：O(m*n)（量级层面，实际有优化空间）

时间复杂度解析 #

多列B-tree索引的条目总数依然对应表中的n行数据，树的深度由条目总数n决定，和单条索引包含的列数m无关。虽然查询/插入/更新时需要基于多列组合键进行节点内的比较，但单组比较操作属于常数时间（O(1)），不会改变B-tree的深度层级。在PostgreSQL的B-tree实现中，增加列数只会改变单条索引条目存储的内容，不会增加树的深度，因此时间复杂度仍保持为O(log(n))。

空间复杂度解析 #

每个多列B-tree的索引条目需要存储m列的键值数据，再加上B-tree节点的元信息，从渐近复杂度的角度看，空间占用量级为O(mn)。不过PostgreSQL会对多列索引做针对性优化，比如对重复的键前缀进行压缩，实际占用空间会比理论值略小，但整体量级仍符合O(mn)。

内容的提问来源于stack exchange，提问作者Ken T