On Fri, Jul 28, 2006 at 03:14:33PM -0400, Alvaro Herrera wrote: > Jim C. Nasby wrote: > > > What I'm getting at is that I've never seen any explanation for the > > theoretical use cases where a hash index would outperform a btree. If we > > knew what kind of problems hash indexes were supposed to solve, we could > > try and interest people who are solving those kinds of problems in > > fixing hash indexes. > > The btree index needs to descend potentially many pages before getting > to the leaf page, where the actual index is stored. The hash index can > get at the "leaf" node in --supposedly-- one fetch. Btree is O(logN) to > get a single key, while hash is O(1). Our problem lies in the > constants; for btree they are smaller than for hash, so in practice > that O(logN) is always smaller than O(1). > > I've heard other database systems manage to have hash indexes that are > actually faster than btree, so either (1) our btree absolutely rocks, or > (2) their hash implementations are better (probably both).
In that case, perhaps this is something Greenplum might be interested in, since it might fit nicely between bitmap and btree indexes. -- Jim C. Nasby, Sr. Engineering Consultant [EMAIL PROTECTED] Pervasive Software http://pervasive.com work: 512-231-6117 vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461 ---------------------------(end of broadcast)--------------------------- TIP 5: don't forget to increase your free space map settings
