System Design AI

B-trees in System Design Interviews: When to Use It and What to Say

A B-tree is a balanced tree data structure that stores keys in sorted order and keeps all leaf nodes at the same depth. It is designed for storage systems where reading a block of data (a disk page) is much more expensive than reading a few bytes in memory. By packing many keys into each node, a B-tree reduces the number of I/O operations needed to locate a record.

The Problem B-trees Solve

Imagine a distributed key-value store that holds petabytes of user profiles. Each profile is identified by a user ID and must be retrievable in logarithmic time. Storing the index in a plain binary search tree would require a disk read for every level, and with a depth of dozens of levels the latency would explode. A B-tree solves this by increasing the branching factor – a node can hold dozens or hundreds of keys, matching the size of a storage block (e.g., 4 KB). The result is that a lookup typically touches only a handful of blocks, keeping latency on the order of a few milliseconds even at massive scale.

How a B-tree Works – Step by Step

  1. Node Layout – Each node occupies a fixed-size page (often 4 KB). Inside the page we store up to m keys and m + 1 child pointers. The value of m is called the order of the tree. For a 4 KB page with 8-byte keys and 8-byte child pointers, m is roughly 250.
  2. Search – Start at the root. Perform a binary search among the keys in the node to find the child pointer that leads to the target range, then follow that pointer to the next node. Repeat until you reach a leaf.
  3. Insertion – Insert the new key into the leaf node in sorted order. If the leaf has room, you are done. If it overflows (exceeds m keys), split the node into two halves and push the middle key up to the parent. This may propagate upward, potentially creating a new root.
  4. Deletion – Remove the key from its leaf. If the leaf now has fewer than ⌈m/2⌉ keys, you try to borrow a key from a sibling. If borrowing is not possible, you merge the leaf with a sibling and pull a key down from the parent.
  5. Balancing – Because every node (except the root) maintains at least half full, the tree height stays bounded by roughly the logarithm of N to the base ⌈m/2⌉, where N is the number of keys and m is the order. With a high order, the height is typically 3-4 for billions of entries.

Small Worked Example

Suppose we use an order-4 B-tree (max 4 keys per node) and insert the keys 10, 20, 5, 6, 12, 30, 7, 17.

StepActionTree Structure
1Insert 10Root: [10]
2Insert 20Root: [10, 20]
3Insert 5Root: [5, 10, 20]
4Insert 6Root: [5, 6, 10, 20]
5Insert 12 → overflow, splitRoot: [10] with two children: left [5, 6], right [12, 20]
6Insert 30Right child becomes [12, 20, 30]
7Insert 7 → goes to left child, fits: [5, 6, 7]
8Insert 17 → goes to right child, fits: [12, 17, 20, 30]

After the split, the tree height is 2, and any lookup needs at most two page reads.

Where B-trees Appear in Classic Design Questions

Design QuestionWhere the B-tree Shows Up
Distributed Key-Value Store (e.g., Dynamo-style)In the storage engine as the on-disk index for sorted keys. The B-tree is one choice for that engine; many stores use a log-structured merge tree there instead, so say which you picked and why.
File System Metadata (e.g., NTFS, ext4)As the directory index: NTFS keeps directory entries in a B-tree, and ext4 uses a hashed tree for large directories. Each directory entry is a key, so the OS can locate a file with few disk seeks.
Time-Series Storage (e.g., metrics database)As the index for timestamps. Queries like "all points between T1 and T2" are served by walking a small number of leaf pages.

In each case, the interviewer may ask you to justify the choice of B-tree over a hash table or a plain binary tree, and to discuss how it interacts with replication, sharding, or compaction.

Trade-offs and the Alternative Interviewer May Probe

AspectB-treeAlternative (Hash Table)
Read latency for point lookupsFew I/O reads (2-3) because of high fan-out.Constant time in memory, but requires a separate index for range queries.
Range queriesNaturally ordered; can scan consecutive leaves.Not supported; need to maintain a secondary ordered structure.
Write amplificationSplits cause extra writes; may double the number of pages written on a heavy insert workload.Writes are single-page; lower amplification but no ordering.
Space overheadNodes are kept at least half full, so overhead is modest (≈ 50%).Hash tables often waste space due to load factor (e.g., 75%).
ComplexityRequires split/merge logic, concurrency control.Simpler put/get logic; easier to implement in a distributed setting.

Interviewers often follow up with questions about write amplification and compaction. Be ready to say that the usual alternative is a log-structured merge tree (LSM), which batches writes into sorted files and merges them later, trading some read latency for lower write cost.

A 30-Second Pitch

"A B-tree is a balanced multi-way search tree that stores many keys per disk page, so lookups need only a handful of I/O operations. It’s the go-to structure for ordered data that lives on SSD or HDD – think file system metadata, a sorted key-value store, or a time-series index. Insertions may cause node splits, which keep the tree shallow, while deletions may merge nodes to stay at least half full. The trade-off is higher write amplification compared with a hash table, but you get efficient range scans and predictable latency."

Common Mistakes Candidates Make

  1. Confusing B-tree order with tree height – Candidates often state that a B-tree of order m has height log₂ N. The correct base is roughly m/2 because each node holds at least half the maximum keys.
  2. Omitting node split propagation – It’s easy to say “split the leaf and stop.” In reality, a split can cascade up to the root, possibly creating a new root and increasing height.
  3. Treating B-trees as in-memory structures – Many interview answers describe pointer-heavy binary trees. Remember that B-trees are designed for block-oriented storage; each node corresponds to a disk page.
  4. Overstating delete complexity – Deleting a key may be simple if the leaf stays above the minimum occupancy; otherwise you need to borrow or merge, which can affect multiple levels.
  5. Neglecting concurrency – Real systems use latch coupling or lock-free algorithms. Mentioning that you would protect a node during split/merge shows depth.

How to Practice This

  1. Study the worked design in the System Design AI library that walks through a B-tree-backed storage engine. Observe how the diagram builds the request path node by node.
  2. Draw your own B-tree on the canvas for a sample set of keys (e.g., 15, 3, 27, 8, 19). Write the split steps and annotate each node with its page size and fan-out.
  3. Explain the design aloud using the 30-second pitch. Record yourself, then compare to the rubric in the practice brief to see where you missed details like write amplification or concurrency.

Questions people ask

When is a B-tree a better choice than a hash table?

When you need ordered range queries, predictable read latency on disk, or when the data set exceeds memory. Hash tables excel at point lookups but cannot serve scans without a secondary index.

How does the order of a B-tree affect its performance?

Higher order means more keys per node, fewer I/O hops, and shallower trees, but larger nodes can increase cache miss cost. The order is usually chosen to match the underlying storage block size.

What is write amplification in a B-tree and how can it be mitigated?

Splits cause extra pages to be written, sometimes duplicating data. Mitigation strategies include batching inserts, leaving free space in pages so that splits are rarer, or choosing an LSM tree instead when the workload is write-heavy.

Can B-trees be used in a distributed system?

Yes. Each shard can maintain its own B-tree index, and the routing layer uses a consistent hash to locate the shard. Global ordering is achieved by merging results from multiple shards during range scans.