Database Storage Engine Internals in 2026: B-Trees vs. LSM-Trees, Write Amplification, MemTables, and Leveled Compaction

At the very foundation of every persistent software system—from distributed transactional ledgers and relational enterprise databases to time-series telemetry aggregators and real-time vector indexes—lies a single fundamental component: the Database Storage Engine. While high-level database layers are responsible for parsing SQL dialects, compiling abstract syntax trees, and planning distributed query executions, it is the storage engine that dictates how data is organized, cached in RAM, committed to non-volatile storage, and retrieved under extreme concurrency.

For more than forty years, the B-Tree (and its ubiquitous B+ Tree variant) has reigned as the undisputed standard for database storage engines, powering relational giants like PostgreSQL, MySQL (InnoDB), SQLite, Microsoft SQL Server, and Oracle. However, the exponential explosion of write-heavy workloads—spurred by distributed IoT telemetry, real-time financial auditing, high-frequency event streaming, and distributed message logs—has exposed a structural vulnerability in B-Trees: severe Write Amplification caused by random, in-place page overwrites.

To overcome the write limitations of B-Trees, modern distributed databases—including Google Bigtable, Apache Cassandra, RocksDB, ScyllaDB, and CockroachDB—have turned to Log-Structured Merge-Trees (LSM-Trees). By converting random disk writes into high-speed sequential appends in RAM, LSM-trees deliver unprecedented write throughput. Yet, this write efficiency introduces a different set of architectural compromises: read amplification, background compaction stalls, and space overhead. In this engineering masterclass, we dissect the internal mechanics of B-Trees and LSM-Trees, evaluate the physics of modern NVMe SSDs, analyze the RUM Conjecture, and implement a high-concurrency storage engine pipeline in modern C#.

1. The Mechanical Reality: Random I/O vs. Sequential I/O

To understand why storage engine architecture is violently contested among database designers, one must understand the underlying physics of hardware storage media.

In traditional spinning hard drives (HDDs), sequential I/O achieved speeds 100x faster than random I/O because a physical actuator arm had to mechanically seek across magnetic platters. While modern PCIe 5.0 NVMe SSDs have eliminated mechanical seek delays, solid-state flash memory suffers from an equally severe hardware constraint: Erase Blocks vs. Write Pages.

• Flash Page Size: Data is read and written in granular pages (typically 4KB to 16KB).
• Flash Erase Block Size: Solid-state memory cannot overwrite an existing page in-place. Before a flash page can be re-written, the entire containing Erase Block (typically 2MB to 8MB) must be erased in a high-voltage electrical operation.
• The Flash Translation Layer (FTL): An embedded microcontroller on the SSD continuously remaps logical block addresses (LBAs), collects garbage, and moves valid pages to new blocks. When a database performs frequent random 4KB updates to disk, the FTL must rewrite entire multi-megabyte blocks, burning through the SSD's finite Program/Erase (P/E) cycles and degrading drive lifespan by up to 80%.

The Core Architectural Principle: Regardless of whether a system runs on HDDs, SATA SSDs, or enterprise NVMe arrays, sequential append-only writes are vastly cheaper, faster, and more hardware-friendly than random in-place updates.

2. B+ Tree Internals: The Read-Optimized Classic

A B+ Tree is a self-balancing, multi-way search tree organized into fixed-size pages (typically 4KB in SQLite, 8KB in PostgreSQL, and 16KB in MySQL InnoDB). Unlike binary trees, a B+ Tree node has a high branching factor (fan-out), typically between 100 and 500 pointers per node, ensuring that even a table with billions of rows has a tree depth of only 3 or 4 levels.

The Cost of In-Place Updates: Write Amplification & Page Splits

While B+ Trees provide exceptional point-read and range-scan performance (requiring at most 3 or 4 page lookups to locate any arbitrary record), their write mechanics are notoriously punishing:

1. Page Flushes: If an application modifies a single 32-byte column in a 16KB row, the database must eventually flush the entire 16,384-byte page to disk. This creates an immediate Write Amplification Factor (WAF) of 512x (writing 16KB of physical I/O for 32 bytes of logical data).
2. Page Splits: When an insertion occurs on a leaf page that is 100% full, the storage engine must allocate a new page, copy 50% of the existing keys over, update the sibling linked-list pointers, and insert a new guide key into the parent node. If the parent node is also full, the split cascades upward toward the root, freezing concurrent queries across the branch.
3. Doublewrite Buffers: To prevent partial page writes if a server loses power mid-flush (torn pages), engines like InnoDB must write every page twice—first to a contiguous doublewrite buffer, and then to the actual table file.

3. LSM-Tree Internals: The Write-Optimized Powerhouse

The Log-Structured Merge-Tree (LSM-Tree), formalized by Patrick O'Neil, Edward O'Neil, and Gerhard Weikum in 1996, discards the concept of in-place page modification entirely. Instead, an LSM-Tree treats all updates (inserts, modifications, and deletions) as immutable, sequential appends.

An LSM-Tree storage engine is divided into two primary tiers: the In-Memory Volatile Tier and the Persistent On-Disk Tier.

The Write Path: From MemTable to Immutable SSTable

1. Write-Ahead Log (WAL): When a write arrives (e.g., PUT user:419 { name: 'Alice' }), it is immediately appended to a sequential disk log file. Because the write is strictly appended to the tail of the file, the disk head or NVMe controller never seeks. An fsync() guarantees zero data loss in the event of an abrupt power outage.
2. Active MemTable: Simultaneously, the record is inserted into an in-memory data structure called the MemTable. The MemTable is typically implemented as a SkipList or a concurrent Red-Black Tree, ensuring that keys are continuously sorted in memory with $O(\log N)$ insertion and lookup complexity.
3. MemTable Freezing: Once the active MemTable reaches a configurable size threshold (typically 32MB to 64MB), it is marked as immutable. A new active MemTable and WAL are spawned instantly to handle incoming traffic with zero pause.
4. Flushing to SSTable: A background worker thread drains the immutable MemTable, writing its contents sequentially to disk as a Sorted String Table (SSTable) at Level 0 (L0). Once flushed, the corresponding old WAL file is safely unlinked.

The Anatomy of an SSTable

An SSTable is an immutable disk file divided into precise sections:

• Data Blocks: Fixed-size blocks (typically 4KB) containing sorted key-value pairs compressed with zstd or Snappy.
• Sparse Index Block: Contains the first key of every data block along with its physical file offset. The entire index block is cached in RAM, allowing the engine to locate any key with a single binary search.
• Bloom Filter Block: A space-efficient probabilistic data structure that can definitively state whether a key does not exist in the SSTable, bypassing disk I/O entirely for non-existent keys.
• Footer: A small, fixed-size trailer at the end of the file containing magic bytes and file pointers to the index and meta blocks.

4. Leveled Compaction vs. Size-Tiered Compaction

Because new SSTables are flushed continuously, an LSM-Tree would quickly accumulate thousands of disparate files, causing read operations to degrade catastrophically as the engine searched file after file. To prevent this, the storage engine runs continuous background Compaction.

The Mechanics of Leveled Compaction

In Leveled Compaction (the standard in RocksDB):

• Level 0 (L0): Flushed directly from RAM. Because each SSTable represents a discrete flush, key ranges overlap across L0 files. A key could exist in any L0 SSTable.
• Level 1 (L1) and Beyond: The background compaction process selects overlapping L0 files and merges them into Level 1 using a multi-way merge sort. Within Level 1, key ranges are strictly partitioned and non-overlapping (e.g., SSTable 1 covers [A-G], SSTable 2 covers [H-M], SSTable 3 covers [N-Z]).
• Level Multipliers: Level 1 has a capacity of ~256MB. Level 2 is 10x larger (2.5GB). Level 3 is 25GB. When Level 1 exceeds 256MB, an L1 SSTable is merged with overlapping L2 SSTables. Over 90% of all data naturally rests in the deepest, cold level.
• Tombstone Purging: Deletions in an LSM-tree are recorded as special tombstone markers. When an SSTable in the deepest level is compacted, tombstones and overwritten historical versions are discarded, reclaiming storage space.

5. The Read Path & Bloom Filter Optimization

When an application executes a point lookup (e.g., GET user:419) on an LSM-Tree, how does the engine locate the key without reading hundreds of files?

1. Check Active MemTable: If the key was recently written, it is found in RAM instantly.
2. Check Immutable MemTables: If a flush is pending, the frozen MemTables in RAM are searched.
3. Search Level 0 SSTables: Because L0 key ranges overlap, the engine must inspect L0 SSTables from newest to oldest.
4. Search Level 1+ SSTables: Because key ranges are non-overlapping in L1 and below, the engine performs a single binary search on the level's manifest to identify the exactly one SSTable that could possibly contain the key.

The Critical Role of Bloom Filters

Without optimization, searching Level 0, Level 1, and Level 2 would require multiple random disk reads. To eliminate this penalty, every SSTable includes an in-memory Bloom Filter:

Bloom Filter Operation:
Key "user:419" → Hash_1() = 12, Hash_2() = 47, Hash_3() = 89
Check Bit Array: [ Bit 12 == 1, Bit 47 == 0, Bit 89 == 1 ]
Bit 47 is ZERO → Key DEFINITIVELY DOES NOT EXIST in this SSTable!
Result: Skip reading SSTable from disk entirely (0ms cost).

Allocating just 10 bits per key in RAM delivers a 99% filter accuracy rate (a 1% false positive rate). For 99 out of 100 SSTables that do not contain the target key, the storage engine skips the file completely without touching the NVMe drive.

6. The RUM Conjecture: The Impossibility of Perfection

In distributed database theory, the CAP Theorem proves that a distributed system cannot simultaneously guarantee Consistency, Availability, and Partition Tolerance. In storage engine design, a parallel law exists: The RUM Conjecture (formalized by Manos Athanassoulis and Stratos Idreos at Harvard University).

The RUM Conjecture states that an engine can optimize for at most two of the following three core dimensions, inevitably sacrificing the third:

• Read Overhead (R): How many I/O operations or bytes must be read to satisfy a query?
• Update Overhead (U): How many extra bytes must be written to disk for every byte written by the user (Write Amplification)?
• Memory / Space Overhead (M): How much memory and auxiliary disk space (fragmentation, index metadata, duplicated versions) is consumed?

7. C# / .NET 9 Implementation: High-Throughput Concurrent MemTable

Let us construct a production-grade, thread-safe Concurrent MemTable in C# / .NET 9 utilizing ConcurrentSkipList concepts, atomic memory tracking, and an asynchronous flush controller.

using System.Collections.Concurrent;
using System.Text;
using Microsoft.Extensions.Logging;

public sealed class MemTableEngine : IDisposable
{
    private readonly long _maxSizeBytes;
    private readonly ILogger<MemTableEngine> _logger;
    private readonly ConcurrentDictionary<string, StorageEntry> _activeMemTable;
    private ConcurrentDictionary<string, StorageEntry>? _frozenMemTable;
    private long _currentMemoryBytes;
    private readonly FileStream _walStream;
    private readonly object _flushLock = new();

    public MemTableEngine(string walPath, long maxSizeBytes, ILogger<MemTableEngine> logger)
    {
        _maxSizeBytes = maxSizeBytes;
        _logger = logger;
        _activeMemTable = new ConcurrentDictionary<string, StorageEntry>(StringComparer.Ordinal);
        _walStream = new FileStream(walPath, FileMode.Append, FileAccess.Write, FileShare.Read, 4096, FileOptions.WriteThrough);
    }

    public async Task PutAsync(string key, byte[] value, CancellationToken ct = default)
    {
        var entrySize = Encoding.UTF8.GetByteCount(key) + value.Length + 16;

        // 1. Write to Write-Ahead Log (WAL) with strict durability
        await WriteToWalAsync(key, value, isDelete: false, ct);

        // 2. Insert into in-memory Active MemTable
        var entry = new StorageEntry(value, DateTime.UtcNow.Ticks, IsTombstone: false);
        _activeMemTable.AddOrUpdate(key, entry, (_, _) => entry);

        // 3. Track atomic memory footprint
        var totalBytes = Interlocked.Add(ref _currentMemoryBytes, entrySize);

        // 4. Trigger asynchronous flush if threshold exceeded
        if (totalBytes >= _maxSizeBytes)
        {
            TriggerBackgroundFlush();
        }
    }

    public bool TryGet(string key, out byte[]? value)
    {
        // 1. Search Active MemTable (RAM)
        if (_activeMemTable.TryGetValue(key, out var activeEntry))
        {
            if (activeEntry.IsTombstone)
            {
                value = null;
                return false; // Key was deleted
            }
            value = activeEntry.Payload;
            return true;
        }

        // 2. Search Frozen MemTable (RAM - Flush in flight)
        if (_frozenMemTable is not null && _frozenMemTable.TryGetValue(key, out var frozenEntry))
        {
            if (frozenEntry.IsTombstone)
            {
                value = null;
                return false;
            }
            value = frozenEntry.Payload;
            return true;
        }

        // 3. Key not in RAM; caller proceeds to Disk SSTable search
        value = null;
        return false;
    }

    private void TriggerBackgroundFlush()
    {
        lock (_flushLock)
        {
            if (_frozenMemTable is not null) return; // Flush already in progress

            _logger.LogInformation("MemTable reached capacity ({Bytes} bytes). Freezing and flushing to SSTable L0...", 
                _currentMemoryBytes);

            // Snapshot active table to frozen slot
            _frozenMemTable = new ConcurrentDictionary<string, StorageEntry>(_activeMemTable, StringComparer.Ordinal);
            _activeMemTable.Clear();
            Interlocked.Exchange(ref _currentMemoryBytes, 0);

            // Dispatch background I/O flush
            Task.Run(async () =>
            {
                try
                {
                    await FlushToSSTableAsync(_frozenMemTable);
                }
                finally
                {
                    _frozenMemTable = null;
                    _logger.LogInformation("SSTable L0 flush complete. Memory reclaimed.");
                }
            });
        }
    }

    private async Task FlushToSSTableAsync(ConcurrentDictionary<string, StorageEntry> data)
    {
        // Sort keys and write sequentially to immutable SSTable file on disk
        var sortedKeys = data.Keys.OrderBy(k => k, StringComparer.Ordinal).ToList();
        var sstableFileName = $"sstable_l0_{DateTime.UtcNow.Ticks}.sst";
        
        await using var sstStream = new FileStream(sstableFileName, FileMode.CreateNew, FileAccess.Write, FileShare.None, 65536);
        foreach (var key in sortedKeys)
        {
            var entry = data[key];
            var keyBytes = Encoding.UTF8.GetBytes(key);
            
            // Format: [KeyLen (2B)][KeyBytes][ValLen (4B)][ValBytes][IsTombstone (1B)]
            await sstStream.WriteAsync(BitConverter.GetBytes((short)keyBytes.Length));
            await sstStream.WriteAsync(keyBytes);
            await sstStream.WriteAsync(BitConverter.GetBytes(entry.Payload.Length));
            await sstStream.WriteAsync(entry.Payload);
            sstStream.WriteByte(entry.IsTombstone ? (byte)1 : (byte)0);
        }
        await sstStream.FlushAsync();
    }

    private async Task WriteToWalAsync(string key, byte[] value, bool isDelete, CancellationToken ct)
    {
        var keyBytes = Encoding.UTF8.GetBytes(key);
        var buffer = new byte[7 + keyBytes.Length + value.Length];
        
        buffer[0] = isDelete ? (byte)1 : (byte)0;
        BitConverter.TryWriteBytes(buffer.AsSpan(1, 2), (short)keyBytes.Length);
        keyBytes.CopyTo(buffer.AsSpan(3));
        BitConverter.TryWriteBytes(buffer.AsSpan(3 + keyBytes.Length, 4), value.Length);
        value.CopyTo(buffer.AsSpan(7 + keyBytes.Length));

        await _walStream.WriteAsync(buffer, ct);
        await _walStream.FlushAsync(ct);
    }

    public void Dispose()
    {
        _walStream.Dispose();
    }
}

public sealed record StorageEntry(byte[] Payload, long Timestamp, bool IsTombstone);

8. Architectural Decision Framework: When to Choose Which

When architecting a new microservice or selecting an operational database, platform leads should apply the following decision tree:

Frequently Asked Questions (FAQ)