How it works
Each node holds many sorted keys rather than just one. Internal nodes contain separator keys and child pointers; a lookup follows the appropriate pointer until it finds the target leaf. The high branching factor keeps the tree shallow, and all leaves remain at the same depth.
In a classic B-tree, records or record references can appear in internal nodes as well as leaves. In a B+ tree, data entries live in the leaves, while internal nodes guide searches. Database documentation often uses “B-tree index” as the broader name, so clarify the layout rather than relying on the label.
B+ tree leaves are linked in key order. To read photos from a particular month, the database seeks to the first matching key and scans leaf entries until the range ends. This avoids a separate root-to-leaf lookup for every result, though retrieving rows outside the index may require additional reads.
Composite keys are sorted lexicographically. An index on (user_id, created_at, photo_id) groups each user's photos together and orders them by time, with photo_id breaking ties. It supports a user's time-range queries well, but generally cannot efficiently seek a global time range without constraining user_id.
Inserts locate a leaf and add an entry; a full page may split and update its parent, potentially propagating toward the root. Deletes can leave free space, with merging or cleanup depending on the implementation. Write-ahead logging and concurrency control make these changes recoverable and safe under concurrent access.
Lookup cost grows logarithmically with the number of entries, but page reads matter more than comparisons for disk-backed indexes. Frequently used upper pages often stay cached. A range scan adds work proportional to the leaf pages visited and any table rows fetched.
A worked example
Indexing a photo library for ordered pagination
Suppose a photo service stores 100 million metadata rows and frequently returns a user's next 50 photos. Use a B+ tree index on (user_id, created_at, photo_id). With an illustrative capacity of 200 entries per leaf and 200 children per internal page, the index needs about 500,000 leaf pages and four tree levels. A request seeks to the user's cursor, then scans roughly enough leaf entries to return 50 photos, rather than skipping thousands of earlier results. Upper levels may already be cached. If captions and object keys are not covered by the index, returning those fields requires table-row fetches. Every photo insertion also adds an index entry and may trigger a page split.
Trade-offs to say out loud
- Fast ordered reads versus write overhead
- Each affected index must be maintained on inserts, deletes, and indexed-column updates, adding page writes, logging, and occasional splits.
- Covering queries versus larger indexes
- Including needed columns can avoid table-row fetches, but wider entries consume more storage and cache space and can increase tree height.
- Sequential insertion versus a hot leaf
- Increasing keys tend to concentrate writes near one edge of the tree, improving locality but potentially creating contention under heavy concurrent insertion.
- Random insertion versus cache efficiency
- Random keys spread writes across more pages, which can increase cache misses, page splitting, and unused space.
- B+ trees versus LSM trees
- B+ trees provide direct ordered page access, while LSM trees buffer and merge writes, trading different write costs for compaction and potentially more read work.
- Logical ordering versus physical row placement
- A secondary index preserves key order but may lead to scattered table reads, while a clustered layout keeps rows organized by the clustering key.
When to reach for it
- The main queries combine equality filters with a range, such as one user's photos within a date interval.
- The API needs ordered results or keyset pagination without scanning and discarding a growing offset.
- You need selective point lookups and range scans from the same persistent index.
- The design requires ordered threshold matching, such as finding price alerts crossed by a price change.
- An interviewer asks you to justify a storage engine or explain why a proposed composite index fits the query.
How to bring it up in the interview
- Start with the query and propose a concrete index: “For a user's photo history, I would index (user_id, created_at, photo_id).” Explain the equality prefix, range column, and unique tie-breaker.
- Walk through the actual read path: seek to a leaf, scan matching entries, and fetch table rows if the index does not cover the query. Interviewers often probe how many entries are scanned versus returned.
- Name the write cost before adding another index. Expect follow-ups about ingestion rate, index size, cache residency, and whether a wide covering index is justified.
- Explain keyset pagination using the last returned composite key, then distinguish deterministic ordering from snapshot consistency when rows change between requests.
- Keep local indexing separate from distribution: a B+ tree indexes data within a storage engine; sharding and replication still determine routing, availability, and cross-shard query costs.
Common mistakes
- Calling a B-tree a binary tree; each internal node normally has many children.
- Saying a lookup always needs one disk read, or that every tree level necessarily causes a disk read; cache residency changes the physical I/O.
- Assuming an index on (user_id, created_at) is equally effective for queries on created_at alone.
- Treating O(log N) lookup time as the entire query cost while ignoring range size, filtering, table fetches, and sorting.
- Claiming an index supplies transaction isolation or makes pagination snapshot-stable; those require separate concurrency and consistency decisions.
Where it comes up
Interview questions where b-trees is part of a strong answer, and why.
- Design a price alert systemAn ordered index on instrument and threshold can locate alerts crossed by a price movement without checking every registered alert.
- Design Google PhotosComposite indexes support bounded per-user library queries, date filtering, and ordered pagination over photo metadata.
- Design Google CalendarComposite indexes bound candidate event scans by calendar and time, while overlap filtering and recurring-event expansion require additional logic.
- Design a distributed key-value storeChoosing a B+ tree versus an LSM tree is a central storage-engine decision affecting durable writes, read paths, and ordered range access.
Questions people ask
What is the difference between a B-tree and a B+ tree?
A classic B-tree can store records or record references in both internal nodes and leaves. A B+ tree keeps data entries in linked leaves and uses internal nodes for navigation, making ordered scans straightforward. Many databases call their B+ tree-style structures “B-tree indexes.”
Why do databases use B+ trees instead of binary search trees?
B+ trees fit many keys and child pointers into each page, reducing the number of page accesses needed to search a large index. They also remain balanced and support efficient ordered scans through their leaves. Binary search trees typically require many more pointer-following steps and offer poorer page locality.
When should I choose a B-tree index instead of a hash index?
Choose a B-tree-style index when you need ranges, ordered traversal, prefix-based composite lookups, or both equality and range queries. Hash indexes are designed primarily for equality lookups and do not preserve useful key ordering. The actual choice also depends on the database's index implementations and workload.