Storage Engines: B-Trees, LSM Trees, Column Stores, and Object Storage

Storage Layout Is a Payment Schedule

Storage engines usually enter design conversations too late. A team models the data, adds indexes, ships the feature, and only then discovers that deletes do not reclaim space quickly, write latency has a second peak during compaction, a migration needs a table rewrite, or a cheap analytical scan becomes expensive after the files fragment into thousands of tiny objects.

Those surprises are rarely random. They are consequences of storage layout.

A storage engine decides where the system pays for the work of accepting a write, making it durable, finding it again, preserving order, serving scans, maintaining indexes, deleting old versions, and recovering after failure. Some engines pay more before the write returns. Some defer work to reads. Some turn updates and deletes into new records and rely on later cleanup. Some make large scans cheap by storing columns together. Some make elasticity and durability cheap by treating object storage as the substrate, then pay in metadata, commit coordination, and file management.

The useful question is not “Which storage engine is fastest?” It is: for this workload, where will the engine move the cost, and can the team observe and operate that cost before users feel it?

The Storage-Engine Contract

A storage engine has a small contract with a large blast radius. It must accept writes, make committed work durable, find records or ranges, expose enough ordering or concurrency behavior for the database above it, and eventually reclaim obsolete space. It must do this while hardware lies, processes crash, disks fill, traffic bursts, and operators run maintenance at imperfect times.

Durability usually starts with an append-friendly record: a write-ahead log, commit log, journal, or immutable file. Searchability requires structure: pages, sorted runs, indexes, manifests, partition directories, bloom filters, zone maps, metadata catalogs, or statistics. Space reclamation requires another mechanism: page reuse, vacuum, compaction, file rewrite, tombstone cleanup, or retention expiry. The product may hide the names, but it cannot make the work disappear.

A useful storage review therefore follows one operation all the way through the machinery. For a write, count the pages, logs, files, indexes, replicas, and derived copies that must change. Ask what must flush, replicate, checkpoint, or commit before the caller receives success. For a read, count the structures the engine may consult before it can return a record or prove that no record exists. Then trace deletion, background maintenance, and recovery with the same care. Is old data removed, marked dead, hidden by a tombstone, retained in a snapshot, or rewritten later? After a crash, how much log replay, file listing, manifest repair, reindexing, or cache rebuilding stands between the team and service?

The product may present one API, but these paths can have different costs and different clocks. That is what turns storage from folklore into an inspectable design surface.

One Order System, Four Storage Behaviors

Continue with the order domain from Chapter 5. Checkout updates the order, payment attempt, and shipment state under strict invariants. Support searches recent orders by customer, SKU, note text, and status. Finance scans months of payment and refund facts. Product analytics retains clickstream events for broad scans.

Those four paths should not be forced through one physical layout. The operational source of truth might use a B-tree-oriented row store because checkout needs constrained updates, uniqueness, and ordered lookups by customer or order. Support search can use an inverted index derived from that truth. Finance can use columnar files because it reads a few fields across many rows. Clickstream analytics can land append-only files in object storage and compact them into query-friendly partitions.

Now add one requirement: customers can request deletion or redaction under the company’s retention policy. The requirement is singular, but the physical work is not. The row store may mark or delete rows and rely on vacuum-like cleanup. The search document must be removed or reindexed. The columnar table may need delete metadata or rewritten files. The object-backed event lake may need a partition rewrite, compaction, or a retention exception path. A cache must evict stale copies.

Saying “we delete user data” conceals all of that work. A defensible design names the source of truth, every derived copy, the physical delete mechanism, the maximum cleanup lag, the signal that proves cleanup is progressing, and the owner for each layout. Keep this order system in view while comparing the engines below: the useful difference between them is where each path makes the system pay.

B-Tree Families

B-tree and B+tree families organize data into fixed-size pages ordered by key. Internal pages route the search. Leaf pages contain entries, row references, or the rows themselves, and many designs keep leaves linked in key order. That simple shape explains much of their production behavior: find the key by walking the tree, then scan neighboring leaves when the query follows the same order.

This is why B-tree-style layouts are natural for point lookups, uniqueness checks, and ordered range scans. A primary key lookup does not need to inspect every row. A query for one tenant’s recent records can be efficient when the key order places that tenant and time range together. An index can enforce uniqueness because the ordered structure gives the engine a place to check whether the key already exists.

The cost appears when writes disturb ordered pages. Inserts into a full leaf can split a page. Updates may move a row, leave an old version behind, or touch several secondary indexes. Deletes may mark space reusable before it is physically compacted. Hot ranges can concentrate writes into the same pages or locks. If rows grow, shrink, or churn heavily, the layout can accumulate fragmentation, dead versions, or free space that is not useful for the next write shape.

Most production systems manage those costs with page reuse, fill factors, background cleaners, vacuum-like processes, clustering, statistics refreshes, or rebuild operations. Those tasks are not optional housekeeping. They are part of the payment schedule. In the order system, update churn and secondary indexes on customer, status, and time can make that schedule visible long before the base table appears large.

B-tree behavior matters most when a workload has update churn and many secondary indexes. Each insert, update, and delete may touch several ordered structures. A query that becomes fast because of five indexes can make every write more expensive and can increase backup size, restore time, migration duration, and cache pressure. Storage mechanics explain why every maintained access path has a write tax.

LSM Trees

Log-structured merge trees move much of the write path away from random page mutation. A write lands in memory, is recorded durably in a log, and later flushes to immutable sorted files. Reads check memory and one or more sorted runs, often helped by bloom filters, sparse indexes, and file-level metadata. Background compaction merges files, discards overwritten values, and removes tombstones when it is safe.

This design can absorb high write rates because the foreground write is append-friendly. The trade-off is read amplification, write amplification during compaction, and compaction debt. A read may consult multiple files before it proves the answer. A logical update may be written once to the log, once to a flushed file, and several more times as compaction rewrites it into lower levels or merged runs. A delete may become a tombstone that must remain visible long enough to suppress older values.

A dangerous LSM failure mode is delayed honesty. The system can accept writes quickly while it accumulates files that must be merged later. If compaction falls behind, disk usage grows, reads touch more files, and tail latency can jump when background work competes with foreground traffic. If tombstones accumulate, a customer’s logical deletion may neither reduce storage nor remove the cost of encountering older versions until the cleanup path catches up.

LSM-backed systems are not simply “fast for writes.” They are strong for write-heavy workloads when compaction has headroom, keys are distributed sensibly, read paths are helped by appropriate filters and ordering, and operators monitor debt instead of only request latency.

Column Stores

Columnar storage arranges values by column rather than by row. Analytical queries often read a few columns across many rows: revenue by day, events by device type, error count by service, inventory movement by warehouse. Columnar layout lets the engine skip unused columns, compress similar values together, and process batches efficiently. Zone maps, min/max statistics, dictionaries, and other metadata can let the engine skip whole chunks when predicates align with the layout.

The cost is that the layout is not naturally shaped like a small transactional row update. Updating one logical row may touch several column files, create a delta record, or wait for a later merge. Tiny writes can produce inefficient fragments unless the system buffers, batches, or compacts them. A point lookup can be awkward if the engine must reconstruct one row from multiple column segments built for scans.

Column stores shine when the workload is scan-heavy, projection-friendly, and batch-oriented. That is why the finance path can read payment amount, currency, refund status, and date without pulling every operational order field through the scan. The same layout becomes brittle when a team asks it to behave like a high-churn transactional system without accounting for update, delete, and merge behavior.

Object Storage as a Data Substrate

Object storage changes the ground under the engine. Instead of assuming mutable local pages, many analytical and lakehouse-style designs treat data as immutable files plus metadata. The database shape moves into partition layout, file sizing, manifests, table metadata, commit protocols, statistics, and compaction jobs.

That trade can be excellent. Immutable files are durable, cheap to retain, easy to copy, and friendly to large scans. Compute can scale separately from storage in many architectures. Reprocessing and backfills can operate over file sets rather than one monolithic database volume.

The payment schedule changes, though. A query may spend time listing files, reading manifests, pruning partitions, consulting metadata, and opening many objects. Small files can dominate performance even when total bytes are modest. Bad partitioning can force broad scans. Concurrent writers need commit rules so readers do not see half-published data. Deletes, updates, and privacy corrections may require new files, delete vectors, metadata changes, or compaction rather than immediate in-place removal.

Object storage is not “just cheap disk.” Once it backs a table, file count, partition design, metadata scale, and commit behavior become database design concerns. For the clickstream path, the consequential unit may be a file or partition rather than an event: millions of small event writes can be cheap to accept yet expensive to organize into files that later queries can use.

Memory-First Systems

Memory-first systems choose another payment schedule. They keep hot data in RAM for caches, session stores, leaderboards, queues, rate limiters, feature flags, counters, derived views, or low-latency serving paths. The first design question is whether memory is the source of truth, a rebuildable copy, or a speed layer with acceptable loss.

Eviction is not a minor implementation detail. It is a correctness and latency behavior. If the cache hides an expensive query until a popular key expires, traffic can stampede the source of truth. If the system evicts a session or token that the application treats as authoritative, user-visible behavior changes. If cached authorization data outlives a permission change, the storage choice becomes a security risk.

Persistence changes the review. A memory-first system that claims durability needs snapshotting, append-only logs, fsync policy, failover behavior, and restore procedures. A memory-first system that does not claim durability needs rebuild rules, cold-start expectations, stampede protection, and correctness when the data disappears.

Memory-first designs belong in the same storage review as disk-backed engines because they still choose durability, deletion, recovery, and ownership behavior.

Design Consequences

Storage mechanics should change design conversations early.

Hot keys are not only traffic problems. They can concentrate writes into a page, partition, shard, log segment, lock, compaction range, cache entry, or object prefix. Large rows are not only schema smells. They can reduce page density, increase network cost, hurt cache hit rates, slow repair, and make partial updates expensive. Range scans are cheap only when layout and predicates cooperate; they are costly when they cross scattered keys, many files, too many partitions, or unhelpful clustering.

Deletes deserve special skepticism. A logical DELETE may mean physical removal, a dead version, a tombstone, a retained snapshot, a delete vector, a file rewrite, or a retention marker. If storage cost, privacy, compliance, or customer trust depends on deletion, verify the physical path and the maximum lag.

Backfills and bulk imports deserve the same attention as foreground traffic. A bulk load can be friendly when it arrives as sorted files, bounded batches, or compacted partitions. It can be hostile when it fights ordinary writes, invalidates cache assumptions, creates tiny files, floods compaction, or changes planner statistics before the team is watching.

Storage-Mechanics Risk Sheet

Use this sheet before selecting a storage engine, approving a workload change, or adding a derived store:

The sheet is complete only when it names budgets and owners. “The database handles compaction” is not a production answer if nobody knows what happens when compaction falls behind.

Benchmark the Debt, Not the Demo

A clean-path benchmark can show what an engine does before its deferred work arrives. It cannot show whether production will remain healthy. Run long enough to trigger compaction, vacuum, index growth, cache churn, checkpoints, file merging, statistics changes, and the steady creation of tombstones or dead versions. Measure foreground latency while those tasks compete for I/O, CPU, memory, locks, and network. In an isolated test environment, exhaust the storage budget, restart a node, rebuild a cache, and restore from the artifacts the system will actually retain.

The symptoms often reveal which unpaid work to investigate. A second p99 peak under write load points toward compaction, checkpointing, page splitting, or index maintenance. Disk growth after deletion points toward tombstones, dead tuples, retained snapshots, or files awaiting rewrite. An object-backed table that scans modest bytes slowly may be paying for file count, weak partition pruning, manifests, or metadata. A cache that improves ordinary latency but magnifies incidents may be hiding a cold-start, stampede, failover, or stale-authorization problem.

Do not respond to those symptoms by changing products first. Reconstruct the write, read, delete, maintenance, and recovery paths. Compare their observed cost with the budgets on the risk sheet. A different engine may move the cost to a better place, but it cannot abolish the cost.

Practice: Predict the First Pain

Pick one production table, collection, cache, topic, or object-backed dataset. Write its storage-mechanics risk sheet. Then predict which operation becomes painful first if traffic grows by 10x: inserts, updates, deletes, range scans, analytical scans, object listing, cache rebuild, restore, or maintenance.

Now change one assumption. Make the workload delete-heavy, update-heavy, scan-heavy, bulk-import-heavy, or multi-tenant with one hot tenant. Explain which storage layout becomes less attractive, which maintenance task becomes critical, and which monitor would reveal the problem before users do.

The exercise is complete when the design names where the cost moves, how the team will see it, and who owns the work when the payment comes due. The next chapter narrows this machinery to one particularly consequential structure: the index, which buys a read path by adding work to writes, maintenance, and recovery.