Further Block B-tree thoughts

Just to let everyone know, I'm continuing work on the Block B-tree idea 
discussed earlier.

The current plan is to have a (compressed) bitmap of offsets attached to 
index tuples, to allow vacuuming. For example, if we have a heap like this:
 2 4 6 8
-
10
12
14
16
5
-
18
20

where dashes represent page boundaries, the corresponding index would 
look like:

low key -> heap blk no (offsets)      2 -> 1 (1,2)      5 -> 2 (5)      6 -> 1 (3,4)     10 -> 2 (1,2,3,4)     18 -> 3
(1,2)


So each index tuple points to a group of tuples that are located on the 
same page. The grouped tuples have keys in the range "this index key" - 
"next index key", and there's no other tuples with a key in that range. 
On index page boundaries, the high key of the page can be used instead 
of the next index key to simplify insertion and scanning.

When scanning, index quals need to be rechecked after fetching the heap 
tuples, unless the index tuple pointed to just one heap tuple, or we're 
doing a range scan and both the min and max key of the group are within 
the range. And to do a regular ordered index scan, tuples within a group 
need to be sorted.

The current B-tree is a special case of this design, where each index 
tuple points to a single heap tuple.

At first I thought this would be a new index access method, but it now 
seems that it makes more sense to integrate this with the normal B-tree, 
assuming that the behavior and performance is the same when all index 
tuples point to single heap tuples.

--   Heikki Linnakangas  EnterpriseDB   http://www.enterprisedb.com