A B-tree index is a balanced, sorted tree of fixed-size pages that maps key values to the rows containing them, so the database can locate a row, a range of rows or an ordered sequence by reading only a few pages instead of scanning the whole table. In indexing for relational databases, it is the default index type in PostgreSQL, MySQL InnoDB, SQL Server, Oracle and SQLite, and the structure most people mean when they simply say “an index”.
Its value comes from two properties: the tree stays balanced on every insert and delete, and each node holds hundreds of keys, so even a table with hundreds of millions of rows needs only three or four levels. That makes lookups, range scans and sorted reads predictably fast, at the price of extra storage and slower writes.
How a B-tree index finds a row
A B-tree index finds a row by descending from a single root page through internal pages to a leaf page, choosing at each level the child whose key range contains the search value. Each page is one unit of disk I/O, typically 8 KB in PostgreSQL, SQL Server and Oracle and 16 KB in InnoDB, which is why the structure is built around pages rather than individual keys.
Internal pages store separator keys and child pointers. Leaf pages store the indexed key together with a row locator: a physical tuple identifier in PostgreSQL, a row ID in Oracle, or the primary key value in InnoDB secondary indexes. Almost every production engine actually implements the B+ tree variant, in which all entries live in the leaves and leaves are linked to their neighbors, so a range scan walks sideways along the leaf level without climbing back up the tree.
The number of children per internal page, the fan-out, determines the height. With 8-byte integer keys and page overhead, fan-outs of 300 to 500 are typical. The table below shows how quickly capacity grows with each level, assuming a fan-out of 500 and about 400 entries per leaf page.
| Levels including leaf | Leaf pages reachable | Keys addressable | Page reads per lookup |
|---|---|---|---|
| 2 | 500 | 200,000 | 2 |
| 3 | 250,000 | 100 million | 3 |
| 4 | 125 million | 50 billion | 4 |
In practice the root and most internal pages stay in the buffer cache, so a point lookup on a large table usually costs one or two physical reads at most. A balanced binary tree over 100 million keys would need about 27 levels, which is why databases never use binary trees on disk.
Operations and their cost
Every core B-tree operation runs in logarithmic time relative to the number of keys, and the logarithm base is the fan-out, not two. Range scans add a cost proportional to the number of matching entries, because the leaves are already in key order.
| Operation | Cost | What happens |
|---|---|---|
| Equality lookup | O(log n) | Descend from root to one leaf |
| Range scan | O(log n + k) | Descend once, then follow leaf links |
| Ordered read | O(log n + k) | Leaves deliver rows already sorted |
| Insert | O(log n) | Add to leaf; split the page if full |
| Delete | O(log n) | Remove or mark entry; merge or reclaim later |
When an insert reaches a full leaf, the engine performs a page split: it allocates a new page, moves roughly half the entries to it and adds a separator to the parent, which can cascade upward and, rarely, add a new root. This is how the tree grows from the top and stays perfectly balanced. With random insert order, leaves settle at about 69 percent full on average, so random keys such as version 4 UUIDs produce larger, less cache-friendly indexes than sequential keys.
Which queries a B-tree index can serve
A B-tree index serves any predicate that maps to a contiguous range of sorted keys: equality, comparison operators, BETWEEN, IN lists, IS NULL in most engines and prefix matches such as LIKE 'abc%'. It also lets the query planner skip an explicit sort for ORDER BY and GROUP BY, and return MIN or MAX by reading a single edge of the tree.
In a composite index, the order of columns matters. An index on (country, city, created_at) serves filters on country, on country plus city, and on all three, but it cannot efficiently serve a filter on city alone. This leftmost-prefix rule follows directly from how the keys are sorted.
| Predicate | Index usable | Reason |
|---|---|---|
last_name = 'Novak' | Yes | Leading column equality |
last_name LIKE 'Nov%' | Yes | Fixed prefix is a key range |
last_name LIKE '%vak' | No | Leading wildcard has no range |
first_name = 'Eva' only | Rarely | Skips the leading column |
lower(last_name) = 'novak' | No | Function hides the key; needs an expression index |
When all columns a query needs are present in the index, the engine can answer from the leaves alone. This index-only access is the idea behind a covering index, which removes the most expensive step of many lookups: fetching each row from the table.
B-tree index compared with other index types
The B-tree index is the general-purpose choice, while specialized structures win only for narrower access patterns. The comparison below shows where each alternative fits.
| Index type | Best for | Range and order support | Main limitation |
|---|---|---|---|
| B-tree | Equality, ranges, sorting | Yes | Write overhead, random-key bloat |
| Hash index | Equality only | No | Useless for ranges and sorting |
| LSM tree | Write-heavy workloads | Yes | Read and compaction amplification |
| Bitmap index | Low-cardinality analytics | Limited | Poor under concurrent updates |
| GIN or inverted index | Arrays, JSON, full text | No | Slow, costly updates |
| BRIN | Huge, naturally ordered tables | Coarse ranges | Effective only with physical correlation |
A hash index can be marginally faster for pure equality on very long keys, but the B-tree index handles equality nearly as well and adds ranges and ordering, which is why most designers choose it even for equality-only columns.
Costs, maintenance and common mistakes
Every B-tree index slows every write to its table, because each insert, each delete and each update of an indexed column must also modify the index. A table with eight indexes performs at least nine page modifications per inserted row, plus write-ahead log records for each.
- Over-indexing: indexes created for every column consume memory and slow writes while the planner uses only a few of them.
- Wrong column order in composite indexes leaves the most selective filters unable to use the index.
- Low-selectivity indexes on columns such as a boolean flag are often ignored, because a full scan is cheaper than millions of random row fetches.
- Index bloat builds up after heavy updates and deletes; PostgreSQL relies on vacuum and occasional
REINDEX, other engines on online rebuilds. - Functions on indexed columns in the
WHEREclause disable the index unless a matching expression index exists.
A practical rule is to index for real query patterns, confirm usage with the execution plan, and drop indexes that monitoring shows are never scanned.
The simple explanation
A B-tree index works like the index at the back of a thick book, organized in layers. The top page says which section of the alphabet is where, the next page narrows it down further, and the last page points to the exact page number. Nobody needs to read the whole book to find one word.
Because each layer narrows the search hundreds of times, the database can find one row among millions in three or four steps. The trade-off is that every time a new row is added, the index must be updated too, so more indexes mean slower writing.
How it is used in practice
An online store keeps 120 million order rows in PostgreSQL. The customer account page runs a query that filters by customer_id and sorts by created_at descending to show the latest 20 orders. Without a suitable index, the planner reads the whole table, and the page takes about 9 seconds under load.
The team creates a composite B-tree index on (customer_id, created_at). The planner now descends the tree once to the customer’s newest entry and reads 20 entries backward along the leaf level, with no separate sort step. Response time drops to under 2 milliseconds, and the index adds roughly 4 GB of storage. The team also drops two older single-column indexes that the new one makes redundant, which keeps the write overhead unchanged.