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: | 451D4843.5050704@enterprisedb.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
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
keys.)
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
EnterpriseDB http://www.enterprisedb.com
From | Date | Subject | |
---|---|---|---|
Next Message | Walter Cruz | 2006-09-29 16:25:40 | a little doubr about domains and pl/python |
Previous Message | Tom Lane | 2006-09-29 16:14:11 | Array assignment behavior (was Re: Stored procedure array limits) |