lacakus wrote:

>
>> In Firebird, an index is made up of pages - the same size as all
> pages
>> in the database. It starts as a single page. Index entries (called
>> nodes) are added to the page in order by key. When the page fills,
>> two other index pages are added.
>>
> I guess, that Fb uses B-trees, true ?

There are lots of varieties of B-Trees, but yes, it's a B-Tree
variant.

> Are these trees 2-3 B-trees, or each parent can have more than 3
> childs ?

Each parent is a page and contains as many nodes as fit on a page.
Nodes in the upper (parent) levels contain the key, a record
number of a record that contains that key value and the page number
of the lower level page that starts with that key and record number.
So, the number of "children" a "parent" page can have depends on
the page size and the size of the compressed keys.

> Contains intermediate nodes, also pointers to data rows (or only
> pointers to deeper level index nodes?, or only leaf nodes contains
> pointers to data rows ?

Upper level pages contain only pointers to lower level pages and
actual record pointers are only on the lowest level pages.

> As I understand, if only leaf nodes contains pointers to data rows,
> then this tree will be keept good balanced, without requirements
> of "rebalancing" ?

That's part of it, though garbage collection is also a factor.


Regards,


Ann