B+ Trees Explained Without the Textbook: Why Database Indexes Are So Fast

A friendly tour of the little hierarchy that stops your database from reading 50 million rows just to find a customer’s orders.

Imagine an orders table with 50 million rows.

Now find the three orders for customer_id = 91827.

Without an index, the database may need to read up to 50 million rows to return those three.

An index stores a sorted key, say, a customer ID, and a way to find matching rows without reading everything.

But an index with 50 million keys must stay sorted without becoming hard to update. A linked list makes inserts easy once you reach the right spot, but finding that spot means walking link by link. An array is quick to search, but adding a key in the middle means shifting later entries aside.

A B+ tree gives the database fast directions and small, local changes.

Following the signposts

A B+ tree is a hierarchy of small, sorted pages.

Each large box in the diagram is a page: a fixed-size block of storage the database reads as one unit — usually 8 KB in PostgreSQL or 16 KB by default in InnoDB. A page holds many small key → pointer entries, not just one order. One page read can therefore give the database many possible directions for its next step. PostgreSQL: page layout · InnoDB

The upper pages are signposts: guide values paired with pointers to the next page. To find 91827, the database compares it with the guides, takes the highlighted middle pointer, then repeats until it reaches the leaf with that customer’s entries.

That many-way choice is called fan-out. A binary tree gives the database two paths from each page; a B+ tree gives it many. High fan-out keeps the tree shallow, which matters because reading a page costs far more than comparing keys already inside it.

In a rough model, a page holds about 200 useful references. Three levels can reach about 200³—8 million—entries; four can reach about 1.6 billion. A 50-million-row table can therefore be only four page reads away from a cold cache, and the top levels are often already in memory.

The “plus” is the clever part

In a classic B-tree, an internal page can hold a key and either the record itself or a pointer to it, so a search may finish before reaching a leaf.

A B+ tree draws a cleaner line: upper pages are only a directory of guide keys and child pointers. Every actual index entry — key plus row location or data — lives in the leaf pages, and those pages link to their neighbours.

That gives the upper pages more room for directions while keeping every real entry in one sorted, sideways-walkable layer.

That sounds like an implementation detail until you run this:

SELECT *
FROM orders
WHERE created_at >= '2026-08-01'
  AND created_at <  '2026-09-01'
ORDER BY created_at;

Given an index on created_at, the tree first finds the first August order. Then it simply walks across the linked leaf pages until September begins.

Get Basel Issmail’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

That is the B+ tree’s small magic trick:

• Equality lookup: take the signs to one place.
• Range lookup: take the signs once, then stroll along the shelves.
• Sorted results: you are already standing in order.

Why not a hash index? Hash indexes are for exact matches. They do not keep keys in sorted order, so they cannot handle ranges or hand back rows already sorted. A B+ tree handles exact lookups too, which makes it the versatile default.

PostgreSQL’s B-tree indexes support both comparisons and ordered retrieval. PostgreSQL: B-tree implementation · PostgreSQL: index types

The order matters

An index on (customer_id, created_at) is sorted by customer first, then by date. It can quickly find WHERE customer_id = 91827 and narrow that customer’s orders to an August range. But a date range alone leaves every customer group in play, so the index is much less useful.

Put the column your queries start with first. That is the practical consequence of sorted shelves. PostgreSQL: multicolumn indexes

What happens when the shelf is full?

The tree does not panic. It splits.

When a leaf page fills up, the database redistributes its entries into a new sibling page and adds a new signpost to the parent. If the parent is full, the split can ripple upward, but only along that one short route.

If it reaches the root, the database creates a new root above it. The tree grows one level taller, not sideways.

This keeps every leaf at the same depth, so every lookup gets the same short, predictable route through the tree. PostgreSQL performs this same kind of leaf-to-parent split cascade. PostgreSQL: B-tree implementation

The trade-off is the index tax: inserts and indexed updates can trigger splits, while deletes may leave pages that need cleanup. Fast reads cost extra write work and storage, so not every column deserves an index.

One important wrinkle: an index is not always separate from the data

“An index points to the row” is a useful mental model, not a universal rule. A leaf entry may point to a table row, or the leaf may contain the row data itself.

InnoDB’s primary-key index is clustered, so its leaf pages contain the rows. A secondary index stores the primary-key value instead; if the query needs other columns, InnoDB may take a second trip through the primary-key tree to fetch them. SQLite takes another route: each table and index has its own B-tree inside the same database file. MySQL: clustered and secondary indexes · SQLite architecture

Best case: if an index already contains every value a query needs, the database may answer from the index alone — an index-only or covering-index scan. PostgreSQL: index-only scans

Different layouts, same idea: a wide, balanced set of directions that makes both “find this” and “find everything from here to there” feel instant.

The next time an index makes a query fast

Indexes do not make queries fast by magic. A B+ tree needs a place to start in sorted order: LIKE 'foo%' starts at foo; LIKE '%foo' does not. PostgreSQL: index types

Next time a query is slow, run EXPLAIN or EXPLAIN ANALYZE. For a selective lookup, this is the kind of plan you hope to see:

Index Scan using orders_customer_id_idx on orders
  Index Cond: (customer_id = 91827)

A Seq Scan is not automatically a failure it may be the right plan when most rows match. But a sequential scan over a huge table for a query returning only a few rows is a good prompt to investigate: does the query need an exact lookup, a range, or ordered results? PostgreSQL: using EXPLAIN

Picture a librarian who opens one cabinet, follows three or four immaculate signs, lands on the correct shelf, and for a range, glides sideways from book to book.

That librarian is a B+ tree.