B-tree fan-out

On Fri, Jun 22, 2007 at 09:32:30PM +0200, cluster wrote:

What is the fan-out (number of child nodes) on each B-tree node in
postgresql? Is it dependent of the size of the keys being indexed? If
so: How?

In postgres, everything is done in pages, so how ever many keys fit in
a page. Bigs keys mean less. For integers you can fit an awful lot of
keys.

In B-trees all non-leaf nodes have a bunch of pointers to its child
nodes. What is the size of such a pointer?

I imagine it's a page number, probably just a 32-bit integer.

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

In postgres, everything is done in pages, so how ever many keys fit in
a page. Bigs keys mean less. For integers you can fit an awful lot of
keys.

OK, interesting. Does that mean, that when a node containing only small
values (e.g. integers) is split, then it gets an awful lot of child nodes?

In B-trees all non-leaf nodes have a bunch of pointers to its child
nodes. What is the size of such a pointer?

I imagine it's a page number, probably just a 32-bit integer.

OK, thanks a lot. Do you know if other database systems implement
b-trees this way too? I.e. one page per node.

Thanks!

On Sat, Jun 23, 2007 at 04:11:52PM +0200, cluster wrote:

In postgres, everything is done in pages, so how ever many keys fit in
a page. Bigs keys mean less. For integers you can fit an awful lot of
keys.

OK, interesting. Does that mean, that when a node containing only small
values (e.g. integers) is split, then it gets an awful lot of child nodes?

No, when you split a page it gets split in two, with each page getting
half the keys of the old one. This is independant of the size of the
keys. (This is also why a key is limited to 1/3 page size, so you can
always split a page into two smaller ones.)

In any case, I think the answer to your original question is that the
fan-out can be up to several hundred per level, but it's not fixed.

In B-trees all non-leaf nodes have a bunch of pointers to its child
nodes. What is the size of such a pointer?

I imagine it's a page number, probably just a 32-bit integer.

OK, thanks a lot. Do you know if other database systems implement
b-trees this way too? I.e. one page per node.

No idea whatsoever.

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

In any case, I think the answer to your original question is that the
fan-out can be up to several hundred per level, but it's not fixed.

OK, its beginning to make sense. So the fan-out is given by the key size
and each child node is stored in its own page. Is that correct?

Thanks in advance!

Martijn van Oosterhout <kleptog@svana.org> writes:

On Fri, Jun 22, 2007 at 09:32:30PM +0200, cluster wrote:

In B-trees all non-leaf nodes have a bunch of pointers to its child
nodes. What is the size of such a pointer?

I imagine it's a page number, probably just a 32-bit integer.

src/include/access/itup.h
Also see "Notes about data representation" in
src/backend/access/nbtree/README

We use the same tuple format for all entries in a btree. The line
number part of the t_tid field is useless for downlinks, but in view of
alignment considerations this is unlikely to be worth worrying about.

regards, tom lane

On Sat, Jun 23, 2007 at 05:58:51PM +0200, cluster wrote:

In any case, I think the answer to your original question is that the
fan-out can be up to several hundred per level, but it's not fixed.

OK, its beginning to make sense. So the fan-out is given by the key size
and each child node is stored in its own page. Is that correct?

I beleive so, yes. Each branch is a page that points to many either
branches or leaves. A leaf is also a page which can contain many keys,
which reference tuples in the actual table.

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/