Re: Implementing Bitmap Indexes

On Sun, 30 Jan 2005 11:07:59 +1100, Neil Conway <neilc@samurai.com> wrote:
> Mike Rylander wrote:
> > For on-disk bitmap indexes, yes.  I don't see any reason this couldn't
> > be done with GiST
> 
> It might be possible to do it with GiST, but GiST is designed for
> implementing tree-structured indexes; I don't think it's the right tool
> for the job.

For the initial example where the index is implemented as a set of
unique keys from the table and a bitmap for each key this would look a
unique index, but with an extra datum at at each index node to hold
the bitmap for that key.  If implemented that way an augmented B-Tree
structure would work fine.  At least that's how I would imagine an
on-disk bitmap index would work.  I suppose that would make the index
much more efficient for high-cardinality values, no?

-- 
Mike Rylander
mrylander@gmail.com
GPLS -- PINES Development
Database Developer
http://open-ils.org