In this lesson, you will learn how the database engine navigates a B-Tree index to locate specific data rows with minimal disk I/O.
Understanding the Hierarchy
Think of a B-Tree as a specialized navigational map for your data. Because searching every single page in a heap table would be prohibitively slow (as we discussed in our lesson on Sequential vs Random Access), the database organizes index entries into a balanced hierarchy. This structure is composed of three distinct types of nodes:
- The Root Node: The starting point of every search. It contains a small set of keys that act as "signposts" pointing toward the relevant branch nodes below.
- Internal (Branch) Nodes: These serve as intermediaries. They store ranges of values, helping the engine narrow down which sub-section of the tree contains the data.
- Leaf Nodes: The destination. These are the bottom-most pages that contain the actual pointers to your data rows (or the data itself in a clustered index).
Tracing a Lookup
When you execute a query like SELECT * FROM Users WHERE UserID = 450, the storage engine begins at the Root Node. It compares your target value (450) against the pointers stored in that page.
If the Root Node indicates that values from 1 to 500 are found in the left child, the engine follows that pointer, loading that specific page into the Buffer Pool. It then repeats this logic within the Internal Node, comparing 450 against its keys to determine which Leaf Node holds the entry for 450.
The process looks like this conceptual flow:
Root Node: [ 100 | 200 | 300 | 400 | 500 ]
| | | | \--> Pointer to [501-600]
| | | \--------> Pointer to [401-500] <-- Target
| | \--------------> Pointer to [301-400]
By only loading the specific pages required to reach the leaf, the engine avoids scanning the entire table. The height of this tree is remarkably short, meaning even with millions of rows, the database usually reaches the leaf node in just 3 or 4 disk I/O operations.
Key Takeaway: The B-Tree hierarchy functions like a digital map, allowing the database to prune the search space at each level until it lands precisely on the required data leaf.