IBM 000-8697 User Manual
System Architecture
2-141
Structure of an Index Page
Branch Node Pages
The first index branch node is created after the root node and at least two leaf
nodes exist. Regardless of which page fills first, either the root node or one of
the leaf nodes, the result is the creation of a branch node.
nodes exist. Regardless of which page fills first, either the root node or one of
the leaf nodes, the result is the creation of a branch node.
If the root node becomes full, it splits and creates two branch nodes, each
with half of the root node entries. The root node retains only three entries: one
pointer to each of the branch nodes and one to the infinity slot.
with half of the root node entries. The root node retains only three entries: one
pointer to each of the branch nodes and one to the infinity slot.
If one of the leaf nodes becomes full, it splits into two leaf nodes and one
branch node.
branch node.
Splitting logic is one of the most complicated aspects of index maintenance.
It is not described in detail here.
It is not described in detail here.
node, two branch nodes, and several leaf nodes.