相对于传统的page based数据库存储方式，OceanBase使用了现在非常流行的LSM Tree作为存储引擎保存数据的基本数据结构，这在分布式的通用关系型数据库当中是很少见的。今天我们就来为大家详细解读下LSM Tree的技术原理。

首先需要说明的是，LSM Tree技术出现的一个最主要的原因就是磁盘的随机写速度要远远低于顺序写的速度，而数据库要面临很多写密集型的场景，所以很多数据库产品就把LSM Tree的思想引入到了数据库领域。LSM Tree ，顾名思义，就是The Log-Structured Merge-Tree 的缩写。从这个名称里面可以看到几个关键的信息：

第一： log-structred，通过日志的方式来组织的
第二：merge，可以合并的
第三：tree，一种树形结构

实际上它并不是一棵树，也不是一种具体的数据结构，它实际上是一种数据保存和更新的思想。简单的说，就是将数据按照key来进行排序（在数据库中就是表的主键），之后形成一棵一棵小的树形结构，或者不是树形结构，是一张小表也可以，这些数据通常被称为基线数据；之后把每次数据的改变（也就是log）都记录下来，也按照主键进行排序，之后定期的把log中对数据的改变合并（merge）到基线数据当中。下面的图形描述了LSM Tree的基本结构。

图中的C0代表了缓存在内存中的数据，当内存中的数据达到了一定的阈值后，就会把数据内存中的数据排序后保存到磁盘当中，这就形成了磁盘中C1级别的增量数据（这些数据也是按照主键排序的），这个过程通常被称为转储。当C1级别的数据也达到一定阈值的时候，就会触发另外的一次合并（合并的过程可以认为是一种归并排序的过程），形成C2级别的数据，以此类推，如果这个逐级合并的结构定义了k层的话，那么最后的第k层数据就是最后的基线数据，这个过程通常被称为合并。

用一句话来简单描述的话，LSM Tree就是一个基于归并排序的数据存储思想。从上面的结构中不难看出，LSM Tree对写密集型的应用是非常友好的，因为绝大部分的写操作都是顺序的。但是对很多读操作是要损失一些性能的，因为数据在磁盘上可能存在多个版本，所以通常情况下，使用了LSM Tree的存储引擎都会选择把很多个版本的数据存在内存中，根据查询的需要，构建出满足要求的数据版本。在数据库领域，很多产品都使用了LSM Tree结构来作为数据库的存储引擎，例如：OceanBase，LevelDB，HBase等。