10 Data Structures for Databases: B-trees, Bε-trees, LSM-trees
This chapter explains how real-world databases accelerate queries with indexes and why understanding their underlying data structures matters when you choose or tune a system. An index is a separate structure that maps keys to row locations, transforming costly table scans into targeted lookups. The chapter contrasts clustered and unclustered indexes and highlights the fundamental tradeoff: indexes speed reads but impose maintenance work on writes. Because many inserts embed lookups (for deduplication or constraints), the true performance picture is a balance between read and write costs in an external-memory setting where I/Os dominate.
B-trees are presented as the foundational external-memory search structure: large, disk-sized nodes with high fanout keep the tree shallow and provide optimal lookup costs in terms of I/Os. The chapter details how lookups, inserts, and deletes work—splitting on overflow, borrowing/merging on underflow—and how all leaves stay at the same depth to ensure predictable performance. It also introduces B+-trees, which store all records in linked leaves (with internal nodes as routing keys), enabling efficient range scans and better space utilization in upper levels. These designs underpin mainstream systems like PostgreSQL and MySQL, and their search costs meet the external-memory lower bound.
To improve write throughput while keeping fast reads, the chapter advances two write-optimized designs. Bε-trees add per-node buffers that batch updates as messages flowing toward leaves; flushing in groups amortizes I/Os, yielding inserts/deletes that are asymptotically cheaper than in B-trees while keeping lookups within a small constant factor. Lookups reconcile buffered messages along the root-to-leaf path, and this approach powers engines like TokuDB and file systems like BetrFS. LSM-trees push write optimization further by staging sorted components across exponentially growing levels and compacting them via sequential merges. The chapter contrasts leveling (fewer components, higher write amplification) with tiering (more components, lower write amplification), and shows how Bloom filters curb point-query costs. LSM-trees excel in heavy-ingest workloads (e.g., RocksDB, LevelDB, Cassandra), trading some read complexity and range-query overhead for exceptional write performance.
: Building two indices on top of two different columns in a table.
: A structure of a node in a B-tree. Each node has space to accommodate 2d keys and 2d+1 pointers, no matter how full it is. The pivots direct the search, that is, when searching for the element x, we compare it with the pivots, and the next node (i.e., pointer to it) is chosen based on the value of the key. The node on the left is minimally filled, and the node on the right is maximally filled.
: Insertion into B-tree when the designated leaf is not full.
: Insertion into a full node that results in B-tree growing in depth by 1.
: Handling deletions from an internal node vs. a leaf.
: Deletion of an element can cause an underflow. If neighbors are not at their minimum capacity, the node borrows keys from one of the neighbors.
: Deletion of an element from a leaf might cause a node concatenation, if neighbors are at their minimum capacity. The concatenations can propagate up the tree and ultimately reduce the tree height by 1.
: A -tree organization. Internal nodes are simple and contain keys that route queries to the leaves, where more detailed information on each key is contained.
: The lower bound calculation assumes good blocks.
: A node in a -tree has keys and buffers. Currently, the buffer is full and can not accommodate any more updates.
: When a buffer becomes too full, we flush the fullest sub-buffer to the appropriate node
: Insert and delete messages on the root-to-leaf path to item 7.
: The spectrum of -tree data structures, from most read optimized to most write optimized.
: Our simple write-optimized data structure that is not the LMS-tree.
: Merging smaller component into a larger one in leveling merge policy of an LSM-tree. The example shows a B+-tree-like unit components at each level, but modern LSM-tree implementations use various data structures or even simple tables and files instead of B+-trees.
: Tiering merge policy in an LSM-tree with . When components at tier get filled up, they merge into one component at tier .
: LSM-trees use Bloom filters to eliminate unnecessary disk seeks to tables that do not contain queried items.
Summary
- Database index is a data structure built on top of a database table meant to speed up query performance for large tables. Indexes are built using data structures that can perform efficient searches in the external-memory setting.
- B-trees form the backbone of the most widespread storage engines such as MySQL. B-tree is an optimal data structure to perform lookups on disk. B-tree nodes are large and are usually related to the block size. All operations in a B-tree are logarithmic with the base of
. When nodes in B-trees become too full/too empty, nodes can be split/merged, and the tree grows upwards. - B-trees are read-optimized, and there are other data structures that are better suited to write-heavy workloads. Inserts and deletes are operations that, unlike searches, can be delayed, or processed in batches together. Write-optimized data structures use this idea to delay and buffer insert/delete operations to achieve much faster inserts than B-trees.
-tree is a write-optimized data structure whose inserts/deletes are asymptotically faster than B-trees, and lookups only by a constant slower than B-trees. -trees employ buffer at their nodes to temporarily store insert/delete messages so that they can be at a convenient moment processed in a batch. The value of a parameter 
determines the extent to which the data structure prefers writes over reads.- LSM-tree is a write-optimized data structure that consists of sorted runs that occasionally get merged in a fast sequential fashion. LSM-trees can achieve extremely fast updates at the cost of lookups that are slower both than those of a B-tree and -tree.
FAQ
What is a database index and why is it important?
An index is a separate, ordered data structure (typically a tree or a set of sorted runs) that maps keys to row locations, allowing queries to skip linear scans. With billions of rows, a full scan is infeasible; indexes route lookups to the right block in a handful of I/Os.What’s the difference between clustered and unclustered indexes?
- Clustered index: physically orders the table by the index key; only one per table; great for range scans on that key.- Unclustered index: separate structure that points to rows; you can have many; each table update must also update all affected unclustered indexes.
How do B-trees work and what are their asymptotic costs?
B-trees store many keys per node (fan-out >> 2), matching disk block sizes to keep depth small. A lookup reads one node per level, so worst-case cost is O(log_B N) I/Os (logarithm base is the fan-out). Inserts and deletes do a lookup plus occasional node splits/merges, keeping the same asymptotic cost O(log_B N).How do B+-trees differ from classic B-trees?
In B+-trees, all records live in the leaves; internal nodes hold only routing keys. Leaves are linked, enabling fast in-order scans and range queries. Internal nodes fit more pivots (higher fan-out), often reducing depth. Lookups always go to a leaf, so they consistently cost O(log_B N) I/Os.What happens during B-tree inserts and deletes?
- Insert: find the target leaf; if full, split it and promote the median to the parent; splits may cascade, possibly growing the tree height by one.- Delete: remove from leaf; if a leaf underflows, first borrow from a sibling (and adjust the separator), otherwise merge and pull down the separator; merges can cascade up and may reduce the height.
What is a Bε-tree and why can it write faster than a B-tree?
A Bε-tree augments each internal node with a large buffer. Inserts/deletes are appended as “messages” to buffers and flushed in batches toward the correct child, amortizing many updates into a single I/O. With a tunable parameter ε (0 < ε ≤ 1), lookups remain O(log_B N), while updates are faster by about a factor of B^ε (e.g., ε=1/2 yields ~√B speedup in amortized I/Os per update).How do Bε-tree buffers and lookups actually work?
- Buffers: Each internal node aggregates update messages, conceptually partitioned by child. When a buffer fills, the fullest sub-buffer is flushed to the child in one I/O, moving many messages at once; timestamps preserve order.- Lookup: Walk from root to leaf as in a B-tree, but along the path collect relevant messages (by key) and apply them in timestamp order to get the correct answer. Lookups don’t trigger buffer flushes.
What is an LSM-tree and how do its compaction policies differ?
LSM-trees keep a small in-memory component plus exponentially larger on-disk components (levels/tiers), each internally sorted. Writes are appended and later merged (compacted) sequentially.- Leveling: at most one component per level; smaller components repeatedly merge into the next level (higher write amplification, fewer components to read).
- Tiering: multiple equal-size components per tier; once a tier fills, its components merge once into the next tier (lower write amplification, more components to check on reads).
How do Bloom filters help LSM-tree reads?
Each on-disk component (e.g., an SSTable) keeps a Bloom filter in RAM. On a point lookup, filters quickly rule out most components, so only the few likely components are probed on disk. This reduces typical lookup cost to roughly the number of levels (often logarithmic in data size). Range queries benefit less because many keys may match.When should I choose B-trees, Bε-trees, or LSM-trees?
- B-/B+-trees (e.g., PostgreSQL, MySQL/InnoDB): read-heavy or balanced workloads, frequent range scans, strong point-query latency, moderate write rates.- Bε-trees (e.g., TokuDB, BetrFS): mixed workloads with high insert/delete throughput needs while keeping near–B-tree lookup asymptotics.
- LSM-trees (e.g., LevelDB, RocksDB, Cassandra): write-heavy ingestion, batched/streaming writes, tolerate higher read amplification (mitigated by Bloom filters); excellent sequential write performance.
Algorithms and Data Structures for Massive Datasets ebook for free
