Creation of Root and Leaf Nodes

When you create an index for an empty table, the database server allocates a single index page. This page represents the root node and remains empty until you insert data in the table.

At first, the root node functions in the same way as a leaf node. For each row that you insert into the table, the database server creates and inserts an index item in the root node. Figure 1 illustrates how a root node appears before it fills.

Figure 1. Root Node

begin figure description - The figure shows a table inside of root node one; the contains two columns; the first column is a list of names, the second column contains rowid information for each name in the corresponding row. end figure description

When the root node becomes full of index items, the database server splits the root node by performing the following steps:

Creates two leaf nodes
Moves approximately half of the root-node entries to each of the newly created leaf nodes
Puts pointers to leaf nodes in the root node

As you add new rows to a table, the database server adds index items to the leaf nodes. When a leaf node fills, the database server creates a new leaf node, moves part of the contents of the full index node to the new node, and adds a node pointer to the new leaf node in the root node.

For example, suppose that leaf node 3 in Figure 2 becomes full. When this situation occurs, the database server adds yet another leaf node. The database server moves part of the records from leaf node 3 to the new leaf node, as Figure 2 shows.

Figure 2. Leaf Node 4 Created After Leaf Node 3 Fills

begin figure description - The paragraph that precedes this figure describes the content of the figure. - end figure description