Understanding B+ Trees and Log-Structured Merge Trees (LSM Trees) in HBase

We start by posing a question about data structures and introduce the Log-Structured Merge Tree (LSM Tree) as a creative solution used in HBase.

First, the article reviews B+ trees, explaining why relational databases rely on them to reduce seek time on HDDs, describing their multi‑way balanced search tree nature and showing a typical diagram.

B+ trees have lower disk I/O cost because internal nodes store only keys, allowing more keys per block.

Query paths are uniform, giving stable lookup performance.

All data resides in leaf nodes, making range scans efficient.

A reference link to a detailed B+ tree tutorial is provided: https://blog.csdn.net/b_x_p/article/details/86434387.

The article then discusses the main drawback of B+ trees: they generate many random I/O operations during inserts and range queries due to leaf node splits.

To overcome this, HBase adopts the LSM Tree concept. The LSM Tree originated from a 1996 paper addressing fast writes under limited memory and slow random disk I/O.

LSM Trees are widely used in databases such as HBase, TiDB, Cassandra, LevelDB, and RocksDB. An illustration of the LSM architecture is shown below.

The Ck tree structure is described: data flows from an in‑memory C0 tree and is merged into larger on‑disk Ck trees, turning random writes into sequential writes and greatly improving write throughput, at the cost of some read performance.

In HBase, writes first go to MemStore (the C0 implementation). When a threshold is reached, MemStore flushes sequentially to disk as a new StoreFile (HFile), and multiple StoreFiles are later compacted.

MemStore internally uses a ConcurrentSkipListMap, which provides ordered storage with expected logarithmic time similar to balanced trees but with simpler and faster operations.

To boost random read performance under the LSM architecture, HBase incorporates Bloom filters (Bloom index block in HFile). The Bloom filter structure is illustrated below.

Through Bloom filters, HBase can quickly determine the existence of a key with minimal space overhead, further enhancing read efficiency. A detailed article on Google and Redis Bloom filters is linked for further reading.