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

Re: Block B-Tree concept

From: Heikki Linnakangas <heikki(at)enterprisedb(dot)com>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: 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 16:22:27
Message-ID: (view raw, whole thread or download thread mbox)
Lists: pgsql-hackers
Tom Lane wrote:
> Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
>> I don't mean consecutive as in "1, 2, 3, 4, ... without gaps" but as in 
>> "A and B are consecutive in the index, if there's no value X in the 
>> index so that A < X < B". Maybe there's a better word for that.
> Um, but how are you going to make that work without storing the keys for
> both A and B?  You won't be able to tell whether an incoming key C
> that's just a bit bigger than A should go before or after B.

Let me describe the insertion algorithm:

1. To insert a tuple with key X, we find the position in the index where 
the new tuple would go, just like with a normal B-tree. Let's call the 
index tuple right before the position A and the next tuple B. So 
according to normal B-tree rules, X should go between A and B.

2. If A points to the same heap page as X, we set the bit representing 
the offset of the new tuple in the index tuple A (this might require 
enlarging the index tuple and event splitting the page), and we're done. 
If it points to a different page, we need split the range A-B to A-X-B, 
proceed to step 3.

3. To split the range A-B, scan the heap page to see which of the tuples 
pointed to by A are >= X and which are < X . If there's no tuples >= X, 
insert a new index tuple for X, and we're done. Otherwise, let Y be the 
smallest tuple >= X. Insert a new index tuple for Y, containing all the 
offsets with keys >= X, and remove those offsets from A. We have now 
split A-B to A-Y-B so that A < X < Y < B.

4. Insert the new index tuple for X.

(I'm not sure I got the above description correct for cases with equal 

Note that we don't keep track of the ordering of tuples that are clumped 
into a single index tuple. That's not important, I/O wise, because if 
you're going to fetch a heap page into memory, you might as well scan 
all the tuples on it and sort them if necessary. That's where the space 
and I/O savings comes from.

  Heikki Linnakangas

In response to

pgsql-hackers by date

Next:From: Walter CruzDate: 2006-09-29 16:25:40
Subject: a little doubr about domains and pl/python
Previous:From: Tom LaneDate: 2006-09-29 16:14:11
Subject: Array assignment behavior (was Re: Stored procedure array limits)

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