LSM tree(日志结构合并树)_笔记

谁践踏了优雅 2024-03-26 17:27 69阅读 0赞

WAL：Write Ahead Log 写前日志，顺序日志文件

## 1 LSM tree的定义 ##

LSM tree：  
Log-Structured-Merge-Tree，日志结构合并树。

Log-Structured Merge-tree (LSM-tree) is a disk-based data structure designed to provide low-cost indexing for a file experiencing a high rate of record inserts (and deletes) over an extended period.

可以认为，LSM tree是**内存的树**和**磁盘文件的树**的集合。  
如LSM的内存中的memtable可以使用B+Tree实现、磁盘上面的每层sst文件也可以使用B+Tree实现。

## 2 LSM tree的组成 ##

LSM tree包括三个部分：

1.  MemTable，
2.  Immutable MemTable，
3.  SSTable(Sorted String Table)  
    ![在这里插入图片描述][816f7a383f8e46849fd780a97d061398.png]

### 2.1 MemTable ###

MemTable 是内存中的数据结构，用于保存最近更新的数据，会按照 Key 有序地组织这些数据。  
可以是红黑树、跳表等。

### 2.2 Immutable MemTable ###

内存数据持久化到磁盘时增加的缓存。

### 2.3 SSTable ###

有序键值对集合。文件结构基本思路就是先划分为数据块，然后再为数据块建立索引，索引项放在文件末尾。

当某层的SSTable数量大小达到阈值，会通过 Compact 策略将其转化到下一层。  
有两种基本策略：

1.  size-tiered 策略
2.  leveled 策略

## 3 LSM tree的操作 ##

利用顺序写来提高写性能，代价就是会稍微降低读性能（读放大），写入量增大（写放大）和占用空间增大（空间放大）。

### 3.1 LSM tree的插入、修改、删除 ###

LSM 树的插入、修改、删除都是在 L0 层的树里操作，并记录记录项的时间戳。

### 3.2 LSM tree的查找 ###

查找只需从 L0 层往下查，直到查到某个 key 的记录就可以了。

## 4 LSM tree的与B+tree对比 ##

1.  LSM tree吞吐量高写入性能高；  
    LSM 树不需要磁盘 IO，直接操作内存，单次插入耗时短，所以其写入的最大吞吐量是高于 B+ 树的。
2.  LSM tree查找效率低；  
    查找时， LSM tree需要遍历所有层次的树，查找效率上要低于 B+ 树。
3.  并发控制和故障恢复方面：  
    ![在这里插入图片描述][c0fc3ab1d5e44827ad2340648b9191f6.png]

## 5 LSM tree的应用 ##

LSM 树主要被用于 NoSql 数据库中，如 HBase、RocksDB、LevelDB 等。  
TiDB 的底层存储也是用的 LSM 树。

## 6 小结 ##

LSM tree特点：顺序写入、Compact 操作、读、写和空间放大。  
LSM tree适用场景：对于写操作吞吐量要求很高、读操作吞吐量要就较高的场景，目前主要在 NoSql 数据库中用的比较多。

[816f7a383f8e46849fd780a97d061398.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c2ffba5f31234d049cb7956968d73904.png
[c0fc3ab1d5e44827ad2340648b9191f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c1eed21267f24e5db645436d0357d333.png