数据库管理-第127期 LSM Tree（202301225）
说起分布式数据库，绕不开的一个话题就是LSM Tree，全称为log-structured merge-tree，回到吕海波老师授权过的那句话“没搞过Oracle的，但又是数据库圈里的人，特别做数据库开发的，对Oracle的印象就是：集中式、落后、旧时代的产物，超过Oracle很简单，基于Poxos/Raft，随便上个分布式就可以了。如果再实现个LSM Tree，那就超过Oracle太多了。”可见LSM Tree对于分布式数据库是很重要的一个东西，无论是国外的HBase、Cassandra、LevelDB、RocksDB等，还是国内较为出名的OceanBase、TiDB等，都是使用LSM Tree来组织数据。
1 基本
LSM Tree和B+ Tree是数据库创建block(块)的时候提到的两种基础数据结构。B+ Tree一般用于较少查询和插入时间的场景，而LSM Tree则用于写压力非常大而读要求不是那么高的场景。
LSM Tree并非是一个所谓的新技术，从维基百科来看这是一个诞生于1996年的技术，较早发表用于具体技术则是2006年Google发表的论文《Bigtable: A Distributed Storage System for Structured Data》，这篇论文也被誉为分布式数据库开山鼻祖之作，后面很多分布数据库也都是基于这一篇论文的理论建立起来的。
2 机制
LSM Tree的出现是为了大数据量的OLAP场景，其最大的机制也可以说是优势是可以充分利用磁盘顺序写的优势而带来非常强大的数据写入性能，当然在查询这块牺牲了一定性能一般来说是慢于B Tree，当然这个性能也是可以接受的。而随着内存与SSD价格的持续走低以及容量的极大提升，基于LSM Tree的数据库读性能也有了显著提升。
一个简单版本的LSM Tree包含两层类似于树状的数据架构：
新纪录被插入到Memtable中(T0组件)。如果插入导致T0组件超过一定的大小阈值，则从T0中删除一个连续的条目段，并将其合并到磁盘上的SSTable(T1组件)中。
3 组件
LSM Tree主要使用3个组件来优化读写操作：
Sorted String Table (SSTables)：
数据按排序顺序排序的，因此无论何时读取数据，在最坏的情况下，其时间复杂度将为O(Log(N))，其中N是数据库表中的条目数。
