Rebalancing 
Use
In the following cases, the database system changes the structure of a B* tree:
● If there is not enough space available on the leaf page when a data record is changed or inserted.
The database system adds a new leaf page and redistributes the data records.
Thus the size of a table is limited only by the total amount of available storage space in the data area.
● A leaf page is no longer sufficiently full after the deletion of data records.
The database system deletes the leaf page and moves the data records to other leaf pages.
● Due to the changing or insertion of a data record, the separators on the next higher level are no longer unique.
The database system redistributes the separators.
This can cause some branches of the B* tree to have many more pages than other branches. Such an irregular distribution of the pages compromises the performance of the database system, because more accesses are required to search for data in branches with many pages than in branches with only a few pages.
The database system recognizes this irregular distribution and automatically balances the load (no-reorganization principle).
The following graphic shows how the database system changes the B* tree structure when an INSERT statement is executed.
Example of Distribution of a Page on the Leaf Level
In the ADDRESS table, the CITY column is defined as the primary key. A user uses an INSERT statement to insert a new data record with the value Albas for the CITY column. The data record is too large for the corresponding leaf page in the B* tree, however. As a result, the database system performs the following actions:
...
1. The database system creates a new leaf page and inserts the new data record in the new leaf page. The entries on the new leaf page are sorted beginning with the new data record.
2. If necessary, it copies all data records that belong to the sort area of the new leaf page from the old leaf page to the new leaf page, and then deletes them from the old leaf page. This procedure is called page split. Then the database system updates the position lists and the respective pointers to the following pages within the leaf level.
3. The database system inserts the addresses and separator information for the new leaf page in the corresponding root or B* tree index page at the next higher level.
○ If the B* tree index page is too small, then the database system inserts a new B* tree index page at this index level.
○ If the root page at the top level is too small, then the database system creates a new B* tree index level.
See also: