PostgreSQL哈希与B+树索引组合查询的复杂度及存储疑问

我的表user_tran包含user_id、transaction_id、time_stamp三个字段。我为user_id和transaction_id创建了哈希索引（用于精确匹配），为time_stamp创建了B+树索引。执行的查询语句如下：

select user_id from user_tran where transaction_id = 1 and time_stamp > now() - 3 days;
select transaction_id from user_tran where user_id = 1 and time_stamp > now() - 3 days;

我了解单独使用哈希索引查询复杂度为O(1)，B+树索引为O(lgn)，但两者组合后的查询复杂度是多少？是否为O(lgn + 1)？另外，数据库底层会同时维护这3个索引（2个哈希、1个B+树）吗？

咱们一步步拆解你的问题：

一、多条件组合查询的复杂度分析 #

首先要明确：数据库执行这类混合条件查询时，不会直接把两个索引的复杂度简单相加成O(logn + 1)，实际的执行成本取决于优化器选择的执行计划，常见的两种路径如下：

1. 哈希索引定位 + 时间条件过滤 #

以第一个查询为例，优化器可能优先选择transaction_id的哈希索引（O(1)复杂度），快速定位到所有transaction_id = 1的记录，然后在这些命中的记录里逐一校验time_stamp是否满足范围条件。

这时候的实际复杂度是 O(1) + O(k)，其中k是哈希索引命中的记录数：

• 如果k很小（比如只有几条匹配记录），实际开销接近O(1)；
• 如果k很大（比如上千条），开销主要集中在后续的时间条件过滤步骤。

2. B+树范围查询 + 等值条件过滤 #

优化器也可能反过来，先通过time_stamp的B+树索引（O(logn)复杂度）找到所有近3天的记录，再逐一检查这些记录的transaction_id或user_id是否符合等值条件。

此时的复杂度是 O(logn) + O(m)，其中m是时间范围命中的记录数，同样m的大小会直接影响实际执行效率。

优化建议 #

因为哈希索引不支持范围查询，这类混合条件查询没法通过两个独立索引直接定位到目标记录。如果想优化这类查询的效率，建议创建联合B+树索引（比如(transaction_id, time_stamp)或(user_id, time_stamp)），这样可以通过一次索引遍历（O(logn)复杂度）直接定位到同时满足两个条件的记录，避免后续的过滤开销。

二、数据库是否会同时维护这三个独立索引 #

答案是肯定的。只要你显式创建了这三个独立索引（两个哈希、一个B+树），数据库会在每次数据变更（INSERT/UPDATE/DELETE）时同步维护所有索引：

• 插入记录时：会把user_id、transaction_id分别插入对应的哈希索引结构，同时将time_stamp插入B+树索引的对应位置；
• 更新/删除记录时：会在三个索引中分别找到对应条目，执行同步的更新或删除操作。

不过要注意：维护多个索引会带来写入性能的额外开销——每一次数据变更都要操作三次索引，所以索引的创建要结合实际查询需求做权衡，不是越多越好。

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