对于等式查找，Hash Index 怎么可能不比 Btree 快？

Question

对于每个支持哈希索引的 Postgres 版本，都有一个警告或说明哈希索引与btree索引“相似或更慢”或“不更好” ，至少到版本 8.3。从文档：

7.2 版：

注意：由于哈希索引的实用性有限，B 树索引通常比哈希索引更受欢迎。我们没有足够的证据表明即使对于 = 比较，哈希索引实际上也比 B 树更快。此外，哈希索引需要更粗的锁；见第 9.7 节。

7.3 版（最高 8.2 版）：

注意：测试表明 PostgreSQL 的哈希索引与B 树索引相似或更慢，并且哈希索引的索引大小和构建时间要差得多。哈希索引在高并发下也表现不佳。由于这些原因，不鼓励使用哈希索引。

8.3 版：

注意：测试表明 PostgreSQL 的哈希索引的性能并不比 B 树索引好，哈希索引的索引大小和构建时间要差得多。此外，哈希索引操作目前没有 WAL 日志记录，因此在数据库崩溃后可能需要使用 REINDEX 重建哈希索引。由于这些原因，目前不鼓励使用哈希索引。

在这个 8.0 版本的线程中，他们声称从未发现哈希索引实际上比 btree 更快的情况。

根据这篇博文（2016 年 3 月 14 日）：André Barbosa撰写的
Postgres 上的哈希索引，即使在 9.2 版本中，除了编写实际索引之外，任何其他方面的性能提升几乎都没有。

我的问题是这怎么可能？

根据定义，哈希索引是一种O(1)操作，而 btree 是一种O(log n)操作。那么O(1)查找怎么可能比（甚至类似于）找到正确的分支然后找到正确的记录慢呢？

我想知道索引理论可以使这种可能性成为可能！

Answer 1

基于磁盘的 Btree 索引确实是 O(log N)，但这对于适合这个太阳系的磁盘阵列来说几乎无关紧要。由于缓存，它们大多是 O(1) 和一个非常大的常数加上 O((log N)-1) 和一个小常数。形式上，这与 O(log N) 相同，因为常量在大 O 符号中无关紧要。但它们在现实中确实很重要。

散列索引查找速度减慢的主要原因是需要防止与查找同时调整散列表大小引起的损坏或死锁。直到最近的版本（你提到的每个版本都过时了），这需要导致更高的常量和相当差的并发性。与哈希并发相比，BTree 并发优化的工时要多得多。

Answer 2

哈希查找理论上是O(1)键哈希直接映射到目标记录的物理位置时的操作。如果我理解正确的话，它在 Postgres 中的工作方式有点复杂：键哈希映射到包含您要查找的 OID的存储桶。一个存储桶可能包含多个页面，您需要依次扫描这些页面，直到找到您的特定键（哈希）。这就是为什么它看起来比您预期的要慢。

源代码存储库中的哈希索引访问方法README 文件包含所有详细信息。

Answer 3

该为什么呢？其他答案已经解决了问题，但我质疑前提是否仍然正确。

自 9.6 以来，事情在 Postgres 中发生了变化。哈希索引现在是一等公民（因为它们是 WAL 记录的，因此可以安全使用）。我在 Postgres 11 上的一个简单测试（唯一整数）中测得比 btree 的性能提高了 40%。

像所有基准测试一样，这应该非常谨慎地对待。但是哈希索引永远不会比 btree 快的情况不再是这样。

该基准从一个大型合成表中的 1e8 行中检索 1e7 行，并由以下 SQL 语句组成：

create table hash_test as 
select * from generate_series(1e10, 1e10+1e8) as id;

create index idx_btree on hash_test using btree (id); -- 2.5 minutes
create index idx_hash on hash_test using hash (id); -- 4 minutes
analyze hash_test;

-- enable one index (e.g. idx_hash) and disable the other:
update pg_index set indisvalid = (indexrelid = 'idx_hash'::regclass)
where indexrelid in ('idx_btree'::regclass, 'idx_hash'::regclass);

-- fetch and sum 1e7 randomly selected rows:
with ids_to_fetch as (
    select 1e10 + (random() * 1e8)::int as id 
    from generate_series(1, 1e7) as num_rows_to_fetch
)
select sum(id) from hash_test
natural inner join ids_to_fetch

-- only idx_btree enabled: 72, 72, 72 seconds (3 runs)
-- only idx_hash enabled: 42, 43, 43 seconds (3 runs)