Re: [GENERAL] "Hash index" vs. "b-tree index" (PostgreSQL

Tom Lane wrote:
> On the other hand, once you reach the target index page, a hash index
> has no better method than linear scan through all the page's index
> entries to find the actually wanted key(s)

I wonder if it would be possible to store the keys in a hash bucket in
sorted order, provided that the necessary ordering is defined for the
index keys -- considering the ubiquity of b+-trees in Postgres, the
chances of an ordering being defined are pretty good. Handling overflow
pages would be tricky: perhaps we could store the entries in a given
page in sorted order, but not try to maintain that order for the hash
bucket as a whole. This would mean we'd need to do a binary search for
each page of the bucket, but that would still be a win.

-Neil