advanced9 min readUpdated 2026-06-08

B-Trees

B-Trees are self-balancing tree data structures that maintain sorted data in pages optimized for disk I/O, forming the backbone of indexes in PostgreSQL,.

Quick answer: B-Trees

B-Trees is covered here as a practical system design concept. B-Trees are self-balancing tree data structures that maintain sorted data in pages optimized for disk I/O, forming the backbone of indexes in PostgreSQL,. Use it to understand the Databases idea, where it appears in production systems, and how to discuss it clearly in interviews.

Focus on the problem being solved, the main design choice, the failure mode, and the tradeoff you would defend in front of a senior engineer. This page is part of the DosiBridge system design knowledge graph, so it links related concepts, interview problems, tradeoffs, and references instead of leaving the topic isolated.

Aspect	Details
What it is	A balanced tree structure with high fan-out nodes sized to disk pages, enabling any key lookup in O(log N) disk reads with N potentially in the billions
When to use	Read-heavy workloads, range queries, ordered access patterns, and general-purpose indexing — the default choice for relational database indexes
When NOT to use	Extremely write-heavy workloads where sequential I/O matters more — LSM Trees provide higher write throughput by avoiding random page updates
Real-world example	PostgreSQL uses B-Trees as its default index type, and every primary key and unique constraint automatically creates a B-Tree index
Interview tip	Explain why B-Trees are disk-optimized — the branching factor is chosen so each node fits in one disk page, minimizing I/O per lookup
Common mistake	Confusing B-Trees with binary trees — a binary tree has 2 children per node and is very deep; a B-Tree has hundreds of children and is very shallow
Key tradeoff	B-Trees provide excellent read performance and range scan efficiency but require in-place page updates on writes, which is slower than LSM's sequential I/O

Why This Matters

B-Trees are arguably the most important data structure in databases. Every relational database uses them for primary key lookups, secondary index scans, and range queries. Understanding B-Trees means understanding why databases can find any row among billions in just 3-4 disk reads, how page splits and merges keep the tree balanced during writes, and why index key ordering matters for query performance. In system design interviews, B-Tree knowledge demonstrates that you understand storage engines beyond the API level — you know what happens when the database executes your query.

System architecture diagram for B-Trees showing how services, databases, and caches connect — System architecture for B-Trees

The Building Blocks

Nodes as Pages: Each B-Tree node is stored as a fixed-size disk page (4-16KB), containing sorted keys and pointers to child pages. This alignment eliminates partial reads and maximizes I/O efficiency.
High Fan-Out: With hundreds of keys per node, a B-Tree is extremely shallow — a 100-million-row table with 500-way branching needs only 3 levels, so any lookup takes 3 disk reads.
Page Splits & Merges: When a node overflows, it splits into two nodes and promotes a key to the parent. When underfull, nodes merge. These operations keep the tree balanced at O(log N) height.
Range Scans: Leaf nodes are linked together as a doubly-linked list, enabling efficient range scans — once you find the start key, you follow leaf pointers sequentially without traversing the tree again.
Buffer Pool: Frequently accessed B-Tree pages are cached in the database's buffer pool (shared memory), so hot indexes serve most lookups from RAM without any disk I/O.

Under the Hood

A B-Tree consists of internal nodes (containing keys and child pointers) and leaf nodes (containing keys and row pointers or inline data). In a B+ Tree variant (used by virtually all databases), all data resides in leaf nodes, and internal nodes contain only keys and child pointers for navigation. The leaf nodes are chained together in a linked list for efficient sequential access.

Step-by-step diagram showing how B-Trees processes a request from start to finish — How B-Trees works step by step

When a lookup occurs, the database starts at the root page (almost always cached in the buffer pool) and performs binary search within the node to find the correct child pointer. It follows this pointer to the next level and repeats. With a branching factor of 500, three levels cover 500^3 = 125 million keys. The top 1-2 levels are virtually always in the buffer pool, so a typical lookup requires just 1-2 physical disk reads.

Writes are more complex. To insert a key, the database traverses to the correct leaf page and inserts in sorted order. If the page is full, it splits: half the keys stay, half move to a new page, and a separator key is promoted to the parent. This split may cascade up if the parent is also full, but cascading splits are rare. Deletions mark keys as removed and pages are merged when they drop below a fill threshold. To prevent partial updates during crashes, all page modifications go through the write-ahead log (WAL), ensuring the tree is always in a consistent state on recovery.

How Companies Actually Do This

PostgreSQL Uses B+ Trees as the default index type for all primary keys, unique constraints, and CREATE INDEX statements, storing keys and row TIDs (tuple identifiers) in 8KB pages with a typical branching factor of several hundred.

Comparison table for B-Trees contrasting approaches, tradeoffs, and when to use each — Comparing key aspects of B-Trees

MySQL InnoDB Organizes all table data in a clustered B+ Tree index ordered by primary key, meaning the table itself is a B-Tree. Secondary indexes contain the primary key value as a row pointer, requiring a double lookup.

SQLite Uses B-Trees for both table storage (rows stored in B-Tree leaves) and indexes, making B-Tree performance critical for the billions of SQLite databases embedded in mobile devices worldwide.

Common Pitfalls

Creating too many indexes — each B-Tree index must be updated on every INSERT/UPDATE/DELETE, and page splits on write-heavy tables add significant overhead and fragmentation
Not understanding clustered vs non-clustered indexes — in InnoDB, the table IS a B-Tree ordered by primary key; choosing a random UUID as PK causes constant page splits and fragmentation
Ignoring index bloat — over time, page splits and deletions leave B-Tree pages partially empty; periodic REINDEX (PostgreSQL) or OPTIMIZE TABLE (MySQL) reclaims space and improves cache efficiency

Data flow diagram for B-Trees showing how requests and responses move through the system — Data flow through B-Trees

Interview Questions Worth Practicing

Why are B-Trees preferred over binary search trees or hash indexes for general-purpose database indexing?
Explain what happens internally when you insert a key into a B-Tree that causes a page split.
Compare B-Trees and LSM Trees for a workload that's 80% writes and 20% reads. Which would you choose and why?

The Tradeoffs

Read Latency vs Write Throughput: B-Trees provide fast single-key reads (1-3 disk I/O) but writes require in-place page updates and potential splits, which are slower than LSM's sequential appends
Space Efficiency vs Write Performance: B-Trees store each key in one location (minimal space amplification) but page splits create partially-empty pages that waste space until compacted
Simplicity vs Flexibility: B-Trees handle reads, writes, and range scans well in one structure, but specialized structures (LSM for writes, hash indexes for equality) outperform them in narrow use cases

Component diagram for B-Trees showing each building block and its responsibility — Key components of B-Trees

How to Explain This in an Interview

Here is how I would explain B-Trees in a system design interview:

Explain B-Trees by starting with the disk I/O problem: databases store far more data than fits in RAM, so minimizing disk reads per query is critical. A binary search tree with 1 billion keys would be 30 levels deep — 30 disk reads per lookup. A B-Tree solves this by packing hundreds of keys into each node sized to a disk page (4-16KB). With a branching factor of 500, 1 billion keys fit in just 4 levels — 4 disk reads maximum, and the top levels are cached in RAM, so it's usually 1-2 reads. Leaf nodes are linked together for efficient range scans. On writes, keys are inserted in sorted order within leaf pages; if a page is full, it splits and promotes a key upward. Mention that the B+ Tree variant (used by all major databases) stores data only in leaves, keeping internal nodes small and fan-out high. The key tradeoff vs LSM Trees: B-Trees excel at reads and range scans but LSM Trees win on write throughput.

Interview preparation checklist for B-Trees with key points to mention and mistakes to avoid — Interview tips for B-Trees

Original DosiBridge notes for B-Trees

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study B-Trees is to connect the concept to a production service where growth exposes the first weak assumption in the original design. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

Query Shape: For B-Trees, decide the query shape before choosing tools; otherwise the design looks clean but fails when b changes.
Write Amplification: For B-Trees, decide the write amplification before choosing tools; otherwise the design looks clean but fails when trees changes.
Replication Lag: For B-Trees, decide the replication lag before choosing tools; otherwise the design looks clean but fails when b changes.
Migration Safety: For B-Trees, decide the migration safety before choosing tools; otherwise the design looks clean but fails when trees changes.
Data Ownership: For B-Trees, decide the data ownership before choosing tools; otherwise the design looks clean but fails when b changes.

Production review question

If a team adopts B-Trees, what observable signal proves it helped instead of only making the architecture diagram more fashionable?

Practical metric to track

Track b-trees health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For B-Trees, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.