I’ve been working with databases for over a decade, but I only really understood B-trees a few years ago. Like most developers, I knew they existed and that indexes used them somehow. I could write queries that performed well without thinking about the underlying data structures. But understanding how B-trees actually work changed how I think about database performance entirely.

B-trees are everywhere. Your relational database uses them for indexes. Your file system uses them for directory structures. Most key-value stores build on B-tree variants. They’re the invisible foundation that makes modern data storage practical, yet they’re rarely discussed outside of computer science courses.

The insight that makes B-trees work is elegant. Traditional binary search trees break down when data lives on disk instead of memory. Each node access requires a disk read, and disk reads are thousands of times slower than memory access. B-trees solve this by packing way more data into each node, dramatically reducing the number of disk reads needed for any operation.

Why Binary Trees Don’t Scale

A binary search tree with a million items might be 20 levels deep. That’s potentially 20 disk reads just to find one record. Each disk read takes several milliseconds, so a single lookup could take 100ms or more. Scale that up to the billions of records that large applications manage, and binary trees become unusable for disk-based storage.

The problem isn’t just search performance. Insertions and deletions also require traversing the tree, and unbalanced binary trees can degrade into essentially linked lists. Real-world data often has patterns that create unbalanced trees, making worst-case performance common rather than exceptional.

The B-Tree Solution

B-trees flip the design around. Instead of one key per node, you might have hundreds. Instead of two children per node, you might have hundreds. This reduces tree height dramatically. The same million items might only require 3 or 4 disk reads to find any record.

The trade-off is that each disk read brings back more data, but that’s exactly what you want. Modern storage systems are optimized for reading larger chunks rather than tiny pieces. A 4KB page can hold many keys and child pointers, making each disk read more valuable.

Each B-tree node contains multiple keys in sorted order, along with pointers to child nodes. The keys act as separators. If a node contains keys [10, 20, 30], then the first child contains all keys less than 10, the second child contains keys between 10 and 20, and so on. This organization maintains the sorted property while allowing efficient navigation.

Staying Balanced

The crucial property of B-trees is that all leaf nodes are at the same level. This balanced structure guarantees that every search, insertion, or deletion takes the same number of steps. There are no degraded cases where operations suddenly become much slower.

When you insert a key into a full node, the node splits in half. The middle key gets promoted to the parent node, and the two halves become separate children. If the parent is also full, it splits too, potentially cascading all the way to the root. This is how B-trees grow: upward from the root, not downward like binary trees.

The beauty is that this splitting process automatically maintains balance. New levels are only added when absolutely necessary, and they’re added uniformly across the entire tree. This prevents the unbalanced scenarios that plague binary trees.

Why Databases Love Them

B-trees map perfectly to how storage systems work. Each node corresponds to one disk page, typically 4KB to 16KB. This aligns with the block sizes that storage systems prefer to read and write. You get efficient storage utilization and predictable I/O patterns.

The predictable performance matters enormously. Query planners need to estimate costs for different execution strategies. Having guaranteed logarithmic performance for index operations makes this possible. There are no surprise scenarios where a query becomes 100x slower because data happened to be inserted in an unfortunate order.

Range queries work naturally with B-trees. Since keys are sorted within nodes and the tree structure maintains global ordering, you can find the start of a range and scan forward through adjacent keys. This is why database queries with range conditions (BETWEEN, greater than, less than) can be so efficient when they use indexes.

Beyond Simple Lookups

Most databases actually use B+ trees, a variant where only leaf nodes store data records, and internal nodes just store keys for navigation. All leaf nodes are linked together, making range scans even faster. You can traverse a range without repeatedly accessing higher levels of the tree.

Some implementations pack more intelligence into the structure. They might compress keys within nodes to fit more entries per page. Others optimize for append-heavy workloads where new keys are always larger than existing ones. The fundamental principles remain the same though.

B-trees also handle concurrent access well. Multiple readers can traverse the tree simultaneously without interfering with each other. Writers can lock individual nodes rather than the entire tree, allowing good concurrency for mixed read-write workloads.

What This Means for Your Code

Understanding B-trees helps you write better queries. Primary key lookups are single B-tree searches, so they’re consistently fast. Queries that can use index ranges scan through B-tree leaves efficiently. Full table scans bypass the B-tree entirely and just read raw pages.

When you add an index to speed up a query, you’re essentially giving the database a B-tree structure that matches your access pattern. The database can navigate directly to relevant data instead of scanning through everything. The cost is additional storage for the index and slower writes, since the B-tree needs to be maintained as data changes.

Composite indexes work because B-trees handle multi-part keys naturally. An index on (last_name, first_name) creates a B-tree sorted first by last name, then by first name within each last name group. This supports queries on last name alone or on both fields, but not efficiently on first name alone.

The Bigger Picture

B-trees represent a fundamental insight about working with persistent storage. The gap between memory and disk speeds is enormous, and algorithms that work well in memory often fail on disk. B-trees bridge that gap by batching operations and minimizing expensive I/O.

This principle extends beyond traditional databases. Modern distributed systems face similar trade-offs between local and network operations. Many of the same concepts that make B-trees effective for disk-based storage apply to designing efficient network protocols and data structures.

Every time you write a query that uses an index, you’re leveraging decades of research into making B-trees fast. The next time you wonder why certain operations are slow while others are blazing fast, think about the B-tree structures that make it all work.