LSM-tree and B-tree

The data structure used in the previous video consists of a memory buffer (M-M table) that stores incoming writes.

Periodically, the M-M table is flushed to disk as a sorted key-value file known as an SS table.

SS tables are merged over time through a process called compaction.

This structure is known as an LSM-tree, commonly abbreviated as LSM3.

LSM3 principles are widely used in storage engines.

Examples include Google Cloud's Bigtable, Apache HBase, Apache Cassandra, LevelDB, and InfluxDB.

In contrast, databases like MySQL, PostgreSQL, and Apache CouchDB rely heavily on B-trees.

So, is there a clear winner between LSM3 and B-tree databases?

LSM3s offer faster write performance.

Each write is buffered in memory and flushed to disk sequentially.

In B-trees, a single logical write may trigger multiple disk writes.

When a B-tree node becomes full, it must split, resulting in multiple disk writes.

This phenomenon is known as write amplification.

LSM3s exhibit less write amplification than B-trees.

This leads to higher write throughput and longer SSD disk lifespans.

SSDs have a limited total write count.

B-trees offer faster read performance.

The number of disk reads per query in a B-tree is at most equal to the tree depth.

In LSM3s, queries may require scanning multiple SSD files to locate a key.

This results in higher read amplification.

B-trees have less read amplification than LSM3s.

This leads to higher read throughput in B-tree databases.

It might seem simple: choose LSM3 for write-heavy systems, B-tree for read-heavy systems.

But this is not a binary choice.

LSM3 databases include optimizations to improve read performance.

These include bloom filters and internal memory caching.

If queries target recently inserted data, that data may remain in memory.

Such data is stored in memtables and can be read instantly.

Other mechanisms enhance both write and read throughput.

Sharding increases write throughput and applies to both LSM3 and B-tree databases.

A distributed cache placed in front of an LSM3 or B-tree database improves read throughput and reduces latency.

Thus, performance goals can be achieved through system-level design, not just storage engine choice.

The underlying storage engine—whether LSM3 or B-tree—becomes less critical.

Many factors must be considered when selecting a database.

This topic will be discussed in detail later in the course.

Meanwhile, let's continue examining the LSM3 vs B-tree comparison.

B-trees generally provide more predictable performance for both reads and writes.

LSM3 architecture includes two background processes: flash and compaction.

The flash process writes memtables to disk.

The compaction process merges SS tables into fewer, larger files.

This compaction process may interfere with active reads and writes.

It introduces minor latency spikes for a small percentage of requests.

However, compaction improves data consistency and reduces file fragmentation.

This background activity is essential for long-term performance and stability.

The compaction process helps maintain efficient storage and reduces the number of files over time.

LSM trees are designed to minimize disk fragmentation. Fragmentation occurs when storage space is used inefficiently.

In traditional storage systems, unused space is scattered across data pages, leading to wasted capacity.

This inefficiency arises from two common operations:

• When a B-tree page splits, it often leaves large, unutilized gaps in adjacent pages.
• When a record is deleted, it leaves a contiguous block of unused space within a page.

These gaps result in fragmented storage, where data is not stored contiguously.

Fragmentation reduces storage efficiency because the system must spend time and resources to manage scattered free space.

The presence of unused space in pages increases the likelihood of inefficient data placement.

In LSM trees, operations are structured to avoid creating such gaps.

By batching writes and merging data in levels, LSM trees reduce the number of page splits and deletions.

This design directly combats the formation of fragmented storage regions.

Less fragmentation means storage space is used more efficiently.

Efficient space utilization ensures that data is stored in compact, contiguous blocks.

This allows for faster data access and reduced disk I/O overhead.

The core mechanism of LSM trees prioritizes continuous storage allocation over isolated, scattered blocks.

This structural choice is fundamental to their performance in high-write workloads.