Re: Why hash indexes suck

>>>>> "Tom" == Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

Tom> This means that if you have only one or a few items per
Tom> bucket, the information density is awful, and you lose big on
Tom> I/O requirements compared to a btree index. On the other
Tom> hand, if you have enough items per bucket to make the storage
Tom> density competitive, you will be doing linear searches
Tom> through dozens if not hundreds of items that are all in the
Tom> same bucket, and you lose on CPU time (compared to btree
Tom> which can do binary search to find an item within a page).

This is probably a crazy idea, but is it possible to organize the data
in a page of a hash bucket as a binary tree ? Then you wouldn't lose
wrt CPU time at least.

--
Pip-pip
Sailesh
http://www.cs.berkeley.edu/~sailesh