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.
It might _work_, I just don't see the point. Given an attribute of a heap relation that has N distinct values and T tuples, you need to store
- N bitmaps, each of T bits (before compression) - T ctids - a way to map from a bit in one of the bitmaps to a heap tuple - a way to decide which bitmap(s) to use for a given index scan
I don't see why it's a win to organize this data in a tree. Why not store the ctids in a simple array? You then know that bit K of any bitmap refers to entry K of the ctid array. You'd also need some meta data to figure out which bitmap to use for a given scankey, but it should be pretty easy to do that efficiently.
-Neil
---------------------------(end of broadcast)--------------------------- TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]
