Log-Structured Merge Trees (LSM-Trees) are the foundational data structure behind most modern write-optimized databases and storage engines. Originally described by Patrick O’Neil in 1996, LSM-Trees power systems like Apache Cassandra, HBase, LevelDB, RocksDB, and — critically for AI engineering — many vector databases that store embeddings at scale.
The core insight of an LSM-Tree is deceptively simple: instead of updating data in-place on disk (which requires expensive random I/O), buffer all writes in memory and periodically flush them to disk as immutable, sorted files called Sorted String Tables (SSTables). This transforms random writes into sequential writes, which are orders of magnitude faster on both HDDs and SSDs.
For AI engineers, understanding LSM-Trees matters because they underpin the storage layers of vector databases like Weaviate and Milvus. When you ingest millions of embeddings, the storage engine must handle sustained high write throughput while maintaining efficient read access — exactly the trade-off LSM-Trees are designed to optimize.
When a write operation arrives (a PUT(key, value)), it is first inserted into an in-memory data structure called the memtable. The memtable is typically implemented as a balanced binary search tree (like a red-black tree) or a skip list, which maintains keys in sorted order as they are inserted.
The memtable serves two purposes: it absorbs write bursts at memory speed, and it keeps data sorted so that flushing to disk produces an already-sorted file. A typical memtable is configured to hold between 4 MB and 256 MB of data before triggering a flush.
An in-memory sorted data structure (usually a skip list or red-black tree) that buffers incoming writes. When the memtable exceeds a configured size threshold, it becomes immutable and is flushed to disk as an SSTable. A new, empty memtable is created to accept further writes.
When a memtable reaches its size threshold, it is frozen (made immutable) and written to disk as a Sorted String Table (SSTable). An SSTable is a file containing key-value pairs sorted by key, along with an index block that maps key ranges to byte offsets for efficient lookups.
The internal structure of an SSTable typically includes:
An immutable file on disk containing key-value pairs in sorted key order. Once written, an SSTable is never modified — updates create new SSTables, and deletions are recorded as special “tombstone” markers. This immutability simplifies concurrency and crash recovery.
The complete write path in an LSM-Tree follows this sequence:
// Simplified LSM write path pseudocode
function put(key, value):
wal.append(key, value) // Step 1: durability
memtable.insert(key, value) // Step 2: in-memory sorted insert
if memtable.size() > THRESHOLD:
immutable = memtable // Freeze current memtable
memtable = new Memtable() // Create fresh memtable
flush_to_sstable(immutable) // Background flush to disk
return SUCCESS // Step 3: fast acknowledgmentReading from an LSM-Tree requires checking multiple locations in order from newest to oldest:
Bloom filters are critical for read performance. Before performing a binary search within an SSTable, the bloom filter is consulted. If it returns “no,” the key is guaranteed absent from that file, and the search skips it entirely. This can eliminate 99%+ of unnecessary disk reads.
As more SSTables accumulate on disk, read performance degrades because more files must be checked. Compaction is the background process that merges multiple SSTables into fewer, larger files while discarding obsolete entries.
Two primary compaction strategies exist:
The ratio of total bytes written to disk vs. bytes written by the application. In leveled compaction, a single application write may result in 10-30x actual disk writes as data is repeatedly merged through levels. This is the fundamental trade-off of LSM-Trees: fast application-level writes at the cost of background I/O.
In a leveled compaction scheme, SSTables are organized into levels:
When L0 reaches its file limit, its SSTables are merged with overlapping SSTables in L1. When L1 exceeds its size limit, selected SSTables are merged into L2, and so on down the tree.
Vector databases like Weaviate use LSM-Tree-based storage for their object and inverted index stores. When you ingest embeddings at scale (millions of vectors), the LSM-Tree handles the write throughput while maintaining sorted access patterns needed for metadata filtering and hybrid search.
During bulk embedding ingestion — say, processing 10 million document chunks through an embedding model — the storage layer must sustain write rates of 50,000-100,000 operations per second. LSM-Trees excel here because each write only touches memory and a sequential WAL append, with the expensive sorting and merging happening asynchronously in the background.
AI observability systems that log every inference request, token count, and latency metric use LSM-Tree-based stores (like InfluxDB’s TSI engine) because the data arrives in roughly time-ordered fashion and is rarely updated — a perfect match for the append-oriented LSM-Tree design.
Systems like RocksDB serve as embedded storage engines for caching computed embeddings, KV cache states, or preprocessed feature vectors. The LSM-Tree’s sorted structure enables efficient range scans (e.g., “retrieve all embeddings for document IDs 1000-2000”) alongside point lookups.