Re: Block B-Tree concept

On Fri, Sep 29, 2006 at 10:51:32AM +0100, Heikki Linnakangas wrote:
> 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.

I think something like this has been discussed before. Where an index
tuple currently has the key values followed by a ctid, simply change
that so that it can be a list of ctid's, in order.

This works on having the same key, but doesn't care if the tuples are
on the same page. It used to be not possible because of how to handle
forward and backward scanning within an index entry during updates. I
think with the new "page at a time" index scanning, this got a lot
easier.

One issue is that a single index page could hold more than 1000 index
entries, which might cause problems for callers.

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

This way doesn't change the current index format much.

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.