LSM-Tree是什么数据结构？

本文共计2518个文字，预计阅读时间需要11分钟。

LSM-Tree，即Log Structured Merge Tree，是一种分层有序的磁盘数据结构。它利用磁盘的顺序写特性，通过顺序写入日志文件（Log）来提高写性能，同时通过合并有序的数据文件来优化读性能。核心思想是利用磁盘的顺序写特性，将数据先写入到内存中的结构（如跳表），当内存满时，再将内存中的数据有序地写入到磁盘上的有序文件中。这种结构既提高了写性能，又保证了数据的有序性。它不是一种严格的树结构。

简述LSM-Tree LSM-Tree 1. 什么是LSM-Tree

LSM-Tree 即 Log Structrued Merge Tree，这是一种分层有序，硬盘友好的数据结构。核心思想是利用磁盘顺序写性能远高于随机写。

LSM-Tree 并不是一种严格的树结构，而是一种内存+磁盘的多层存储结构。HBase、LevelDB、RocksDB这些 NoSQL 存储都使用了 LSM-Tree。

2. LSM的组成部分 2.1 MemTable

MemTable 是 LSM-Tree 在内存中的数据结构，只用于保存最新的数据，按照 Key 有序地组织这些数据。

LSM-Tree 没有规定用怎样的数据结构实现 MemTable，例如 HBase 使用跳表来保证内存中 Key 的有序性。

存在内存中的数据会因为断电丢失，所以我们通常使用 WAL，即预写日志的方式来保证数据的可靠。

WAL：预写日志，即事务的所有修改在提交之前要先写入 log 文件中

2.2 Immutable MemTable

MemTable 达到一定大小后，会转化为 Immutable MemTable。