User Guide

SAP AG November 2002

Changes in the B* Tree Structure

The address table is defined via the city primary key [Page

101] column. In the address table,

insert an entry with the value Albas for the city primary key field. The new table row is too

large for the corresponding leaf page [Page 103] in the B* tree [Page 128].

• A new leaf page is created. The new row of the table is incorporated in this leaf page. In

other words, the beginning of the sort area of the new leaf page is specified by this row of

the table. The sort sequence of the individual leaf pages must be restored. To do so, it

may be necessary to copy the table rows that belong in the new sort area from the leaf

page with the next smallest sort area to the new leaf page, and then delete them from the

previous leaf page. This procedure is called page split.

• Pointers to consecutive pages are updated whenever required.

• Address and separator information on the new page is also inserted in the corresponding

root or index page [Page

10 ]3 one level higher. If the index page is too small to

accommodate this information, a new index page is inserted at this index level as well. If

the root page at the uppermost level is too small to accommodate a new entry, a new

index level is created.

A chain of page splits can result in the B* tree being rebalanced.