Database Reference
In-Depth Information
records without a primary key or index would require a linear search across multiple
nodes. Let's discuss format index data structure.
Indexes are stored in sorted order into B-tree (balanced tree) structure, where in-
dexes are leaf nodes under branch nodes.
Figure 3-1
depicts data storage where multi-
level leaf nodes (0,1) are indexed in sorted order and data is in unsorted order. Here
each leaf node is a b-tree node containing multiple keys. Based on inserts/updates/de-
letes, the number of keys per b-tree node keeps changing but in sorted order.
Figure 3-1
.
b-tree Index and data structure with multi-level leaf nodes
Let's simplify further. In
Figure 3-2
,
the table containing age and row keys are leaf
nodes and the other one is a physical table.
Figure 3-2
.
A physical table and an index table as leaf node
