Re: Block B-Tree concept

Heikki Linnakangas wrote:
> If we want to keep the property that VACUUM doesn't re-evaluate index 
> entries, any proposal that doesn't keep track of every heap tuple 
> isn't going to work. I'll try to modify the design I had in mind so 
> that it does keep track of every heap tuple in some form.
After some thought:

Imagine a normal B-tree just like what we have now. But when there is 
more than one tuple on the same heap page with consecutive index keys, 
we represent all of them in a single index tuple that contains the key 
of the first one of them, and a (run-length encoded) bitmap of the 
OffsetNumbers. We should get most of the space and I/O savings as with 
the original proposal, but we can vacuum it without re-evaluating index 
expressions.

It does change the format of an index tuple, unlike the original 
proposal. That adds some complexity. but it's doable.

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