Index Depth and Search Complexity

In this lesson, you will learn how the logarithmic structure of a B-Tree index keeps search times remarkably fast even as your data grows to millions of rows.

The Power of Logarithmic Scaling

When you perform a search in a B-Tree index, the database doesn't scan the entire table. Instead, it traverses the tree from the root node down to the leaf node where your data resides. The number of levels in this tree is called the index depth.

Because B-Trees are "balanced," every path from the root to a leaf has the same length. The search complexity is logarithmic, often expressed as $O(\log_b n)$, where $n$ is the number of total rows and $b$ is the branching factor (the number of pointers a single node can hold).

Visualizing the Hierarchy

Imagine a database page (node) can hold 100 pointers. If you have 1,000,000 rows:

• Depth 1: 100 entries.
• Depth 2: 10,000 entries ($100^2$).
• Depth 3: 1,000,000 entries ($100^3$).

To find any specific row in a million-item table, the database engine only needs to perform 3 disk I/O operations. Even if your table grew to 100 million rows, the tree would only need to grow to a depth of 4.

Query Latency Implications

Latency in database lookups is dominated by disk I/O. Each level of the index depth requires an I/O request to fetch a page from storage into the buffer pool.

-- Searching for a specific ID
SELECT * FROM Users WHERE user_id = 54321;

When you run this query, the engine:

1. Loads the root node (1 I/O).
2. Follows the pointer to the branch node (1 I/O).
3. Follows the pointer to the leaf node (1 I/O).
4. Fetches the actual data row (1 I/O).

By keeping the index depth shallow, the database ensures that your search complexity stays low. If the branching factor $b$ is large, the tree remains "flat" and wide, preventing the depth from increasing and keeping your query latency predictable and fast, regardless of the table's total size.

Key Takeaway: The logarithmic nature of B-Trees means that doubling your data rarely increases the number of disk reads required, keeping search times efficient even at a massive scale.