Re: Implementing Bitmap Indexes

On Sun, 30 Jan 2005 11:07:59 +1100, Neil Conway <neilc(at)samurai(dot)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(at)gmail(dot)com
GPLS -- PINES Development
Database Developer
http://open-ils.org