For every version of Postgres that supported hash indexing, there is a warning or note that hash indexes are "similar or slower" or "not better" than btree indexes, at least up to version 8.3. From the docs:
Note: Because of the limited utility of hash indexes, a B-tree index should generally be preferred over a hash index. We do not have sufficient evidence that hash indexes are actually faster than B-trees even for = comparisons. Moreover, hash indexes require coarser locks; see Section 9.7.
Note: Testing has shown PostgreSQL's hash indexes to be similar or slower than B-tree indexes, and the index size and build time for hash indexes is much worse. Hash indexes also suffer poor performance under high concurrency. For these reasons, hash index use is discouraged.
Note: Testing has shown PostgreSQL's hash indexes to perform no better than B-tree indexes, and the index size and build time for hash indexes is much worse. Furthermore, hash index operations are not presently WAL-logged, so hash indexes might need to be rebuilt with REINDEX after a database crash. For these reasons, hash index use is presently discouraged.
In this version 8.0 thread, they claim that had never found a case where hash indexes were actually faster than btree.
Even in version 9.2, the performance gain for anything other than writing the actual index was almost nothing according to this blog post (14 March 2016):
Hash Indexes on Postgres by André Barbosa.
My question is how is that possible?
By definition, Hash indexes are a
O(1) operation, where a btree is an
O(log n) operation. So how is it possible for a
O(1) lookup to be slower than (or even similar to) finding the correct branch, and then finding the correct record?
I want to know what about indexing theory could EVER make that a possibility!