Database Indexing Internals: B-Trees, Keyset Pagination, and Why Your SQL Queries Scan Instead of Seek (2026 Guide)

In the early days of building an application, relational databases feel like magic. You define tables, insert a few thousand rows, write a few SELECT * FROM Orders WHERE CustomerId = 42 queries, and responses return in under 2 milliseconds. But as your business scales and tables cross 5 million, 20 million, or 100 million rows, queries that used to take milliseconds suddenly take 12 seconds, CPU usage spikes to 100%, and application connection pools exhaustively time out.

When inexperienced developers encounter slow queries, the common reaction is to panic, blame the database, and randomly add indexes on every column mentioned in the WHERE clause. But adding unoptimized indexes often makes performance worse: it slows down write operations, causes massive disk fragmentation, and fails to stop the query optimizer from executing devastating table scans.

To master database performance, you must understand what happens underneath the SQL abstraction layer. In this guide, we will explore the physical storage engine of relational databases (Microsoft SQL Server and PostgreSQL), demystify B-Tree node mechanics, analyze Index Seek vs Index Scan vs Key Lookup operators in execution plans, construct Covering Indexes with INCLUDE, and reveal why traditional OFFSET / FETCH pagination is an $O(N)$ disaster that should be replaced with Keyset Cursor Pagination.

The Physical Storage Engine: 8KB Pages & B-Trees

Relational databases do not read individual rows from disk. In SQL Server, the fundamental unit of data storage is an 8KB Page. In PostgreSQL, it is an 8KB block. Eight physically contiguous pages form an Extent (64KB). When your query requests a single row, the database engine must load the entire 8KB page containing that row into memory (the Buffer Pool).

Anatomy of a Clustered B-Tree Index

A table with a Clustered Index is physically sorted and stored on disk in the order of the clustered index key. The index is organized as a self-balancing search tree known as a B-Tree (Balanced Tree):

1. Root Node: A single 8KB page at the top of the tree containing key ranges and pointers to intermediate pages.
2. Intermediate Level: One or more levels of branching pages directing searches down the tree.
3. Leaf Level: In a clustered index, the leaf level IS THE DATA TABLE ITSELF. The leaf pages contain all columns of every row, linked together as a bidirectional linked list (PrevPage ⮂ NextPage).

Because B-Trees have massive branching factors (a single 8KB intermediate page can store hundreds of key pointers), a B-Tree index on a table with 50,000,000 rows typically has a depth of only 3 or 4 levels. Searching for a row by clustered key requires only 3 or 4 page reads: Root ──▶ Intermediate ──▶ Intermediate ──▶ Leaf Page. This binary traversal runs in $O(\log N)$ time, completing in less than 0.5 milliseconds.

Clustered vs. Nonclustered Indexes & The Bookmark Penalty

A table can have only one clustered index because physical data rows can only be sorted on disk in one order (typically the primary key Id). Every additional index you create is a Nonclustered Index.

What Lives in a Nonclustered Index Leaf?

A nonclustered index is an entirely separate, secondary B-Tree structure. Unlike the clustered index, the leaf pages of a nonclustered index do NOT contain the complete data row. Instead, each nonclustered leaf entry contains only two things:

1. The indexed key columns (e.g., CustomerId).
2. A row locator (or Bookmark): the Clustered Index Key (e.g., Id) pointing to the actual row in the clustered table.

The Key Lookup Disaster

Consider the following query executed against an Orders table with 10,000,000 rows:

SELECT OrderId, CustomerId, TotalAmount, CreatedAt
FROM Orders
WHERE CustomerId = 9812;

Suppose you have a nonclustered index defined as: CREATE INDEX IX_Orders_Cust ON Orders(CustomerId);.

When the query engine executes this query:

1. It traverses the IX_Orders_Cust B-Tree (Index Seek) to locate all rows where CustomerId = 9812.
2. For each matching row, it finds the CustomerId and the clustered key OrderId.
3. THE PROBLEM: The query also requested TotalAmount and CreatedAt, but those columns are not in the nonclustered index!
4. To fetch the missing columns, the engine must execute a Key Lookup (Bookmark Lookup): it jumps over to the clustered index and navigates down the clustered B-Tree to retrieve the full row!

If Customer 9812 has placed 2 orders, 2 Key Lookups take 1 millisecond. But if Customer 9812 has placed 10,000 orders, the database engine must execute 10,000 separate random I/O disk seeks! Random disk I/O is hundreds of times slower than sequential reads.

The Tipping Point: When the query optimizer calculates that executing thousands of Key Lookups is more expensive than reading the entire table, it abandons your nonclustered index completely and defaults to a Clustered Index Scan (Full Table Scan)!

The Solution: Covering Indexes with INCLUDE

To eliminate Key Lookups entirely, you must create a Covering Index. A covering index contains 100% of the columns requested by a specific query, allowing the engine to satisfy the request directly from the nonclustered index leaf pages without ever touching the clustered data table.

In SQL Server, you achieve this using the INCLUDE clause:

-- OPTIMAL COVERING INDEX
CREATE NONCLUSTERED INDEX IX_Orders_CustomerId_Covering
ON Orders (CustomerId)
INCLUDE (TotalAmount, CreatedAt);

Why Put Columns in INCLUDE Instead of the Key?

Why not simply create INDEX IX_Orders(CustomerId, TotalAmount, CreatedAt)?

• Key Columns: Stored and sorted across all levels of the B-Tree (Root, Intermediate, Leaf). Adding large columns to the key bloats intermediate pages, decreases fanout, and increases B-Tree depth.
• INCLUDE Columns: Stored only at the leaf level. They are not sorted and do not participate in intermediate index navigation. This keeps intermediate pages compact while satisfying queries with Zero Key Lookups!

Execution Plan Operators: Seek vs. Scan

When analyzing query performance in SQL Server Management Studio (SSMS) or Azure Data Studio, you must inspect the Graphical Execution Plan. Look for these four critical operators:

-- DANGEROUS AT SCALE (Page 5,000)
SELECT Id, Title, CreatedAt
FROM Articles
ORDER BY CreatedAt DESC
OFFSET 100000 ROWS FETCH NEXT 20 ROWS ONLY;

-- KEYSET / CURSOR PAGINATION (CONSTANT O(1) LATENCY)
SELECT TOP (20) Id, Title, CreatedAt
FROM Articles
WHERE (CreatedAt < @LastCreatedAt) 
   OR (CreatedAt = @LastCreatedAt AND Id < @LastId)
ORDER BY CreatedAt DESC, Id DESC;