图解日志结构合并树LSM Tree

数据库中两种常用索引结构分别为B+树与LSM树。B+树在插入和搜索性能上表现优异，但其在磁盘中的逻辑与物理存储存在差异，导致大量磁盘随机读写，性能受限。为了提升IO性能，LSM树（Log-Strucured-Merge-Tree）应运而生。LSM树并非特定树型结构，而是一种处理写操作密集负载的机制，如OLTP场景。其核心原理是通过日志实现从随机写到顺序写的转变，进而优化数据存储效率。

LSM树内部包含几个关键组件：Memtable、SSTable和WAL（Write-Ahead Log）。Memtable作为内存中的数据结构，内部采用有序数据结构如红黑树或跳表，以保证数据有序性。SSTable则是一种存储键值对的格式，按键值顺序排列，用于将数据持久化至磁盘。WAL在数据写入前记录写请求，确保数据安全。

在数据写入过程中，首先将写请求写入Memtable和WAL，随后当Memtable满载时，其数据将刷新至磁盘上的SSTable。SSTable通过Compaction操作合并重复数据，优化存储效率。Compaction过程持续进行，清理多余Segment文件，以避免磁盘空间浪费。当查询数据时，通过顺序扫描SSTable进行查找，借助稀疏索引加速定位，布隆过滤器则用于高效处理不存在数据的查询请求。

随着时间推移，系统积累更多Segment文件，Compaction线程负责将其合并为新的Segment，以优化存储结构。删除操作通过为键添加墓碑标记来标记已删除数据，最终在Compaction过程中被清理，释放磁盘空间。通过这种方式，LSM树实现高效数据存储与管理，特别适用于写操作密集型场景。

您可能感兴趣问答

Collapsible

热门标签

热点问答