B-Tree Index Internals

In this lesson, you will learn how the structural design of B-Tree indexes dictates the efficiency of your equality and range-based database queries.

The Anatomy of the B-Tree

At its core, a B-Tree index is a balanced, multi-level tree structure. Think of it as an optimized "search map" that sits alongside your table. The tree consists of three primary components:

1. Root Node: The starting point of every search.
2. Internal (Branch) Nodes: These store pointers to child nodes, effectively partitioning the search space.
3. Leaf Nodes: These contain the actual indexed values and pointers to the physical rows (or the primary key) in your data pages.

Because the tree is "balanced," the distance from the root to any leaf is identical. This guarantees consistent query performance regardless of whether your data resides at the "beginning" or the "end" of the index.

Equality vs. Range Queries

The way the engine traverses this structure changes based on the query type:

• Equality Queries (WHERE id = 500): The engine starts at the root and performs a binary search within each node. It follows the pointers down to the specific leaf node containing 500. It performs a single "descent," making it extremely fast—usually $O(\log N)$ complexity.
• Range Queries (WHERE id BETWEEN 100 AND 500): The engine performs the same initial descent to find the starting point (100). However, because leaf nodes are linked in a doubly-linked list, the engine does not need to climb back up to the root. It simply follows the horizontal pointers from one leaf node to the next until it hits 500.

This linked structure at the leaf level is what makes B-Trees superior for ranges compared to structures like Hash indexes, which require a full scan for range conditions. If your index depth is 3, any record can be found in exactly 3 disk reads (plus the actual data fetch), making the traversal cost highly predictable and incredibly low.

Key Takeaway: B-Tree indexes provide logarithmic search times for equality queries and efficient linear scanning for range queries by combining hierarchical tree navigation with horizontal leaf-level links.