Skip site navigation (1) Skip section navigation (2)

Re: Block B-Tree concept

From: Heikki Linnakangas <heikki(at)enterprisedb(dot)com>
To: Heikki Linnakangas <heikki(at)enterprisedb(dot)com>
Cc: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, Bruce Momjian <bruce(at)momjian(dot)us>, "Jim C(dot) Nasby" <jim(at)nasby(dot)net>, PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Block B-Tree concept
Date: 2006-09-29 09:51:32
Message-ID: (view raw, whole thread or download thread mbox)
Lists: pgsql-hackers
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 

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

Heikki Linnakangas

In response to


pgsql-hackers by date

Next:From: Martijn van OosterhoutDate: 2006-09-29 09:52:59
Subject: Re: Another idea for dealing with cmin/cmax
Previous:From: Markus SchaberDate: 2006-09-29 09:21:21
Subject: Re: Faster StrNCpy

Privacy Policy | About PostgreSQL
Copyright © 1996-2017 The PostgreSQL Global Development Group