The B* tree structure is changed by INSERT, UPDATE, and DELETE statements only when there is not enough space for the new information in the target page, or when the fill level of a page falls below the predefined fill level.
The address table is defined using the city primary key column. In the table, insert an entry with the value Albas for the city primary key field. The new table entry is too large for the corresponding leaf page in the B* tree.
· 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 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.
See also: Non-Uniform Distribution of Data Pages