CNDBA社区
1 B+ Tree
B+树是关系型数据库常用的索引存储模型，能够支持高效的范围扫描，叶节点相关链接并且按主键有序，扫描时避免了耗时的遍历树操作。
B+树的局限在于不适合大量随机写场景，会出现“写放大”和“存储碎片”。
- 写放大: 为了维护B+树结构产生的额外IO操作，比如逻辑上仅需要一条写入记录，实际需要多个页表中的多条索引记录。
- 存储不连续：新增叶节点会加入到原有叶节点构成的有序链表中，整体在逻辑上是连续的；但磁盘存储上，新增页表申请的存储空间与原有页表很可能是不相邻的。这样，在后续包含新增叶节点的查询中，将会出现多段连续读取，磁盘寻址的时间将会增加。进一步来说，在B+Tree上进行大量随机写会造成存储的碎片化。
在实际应用B+Tree的数据库产品（如MySQL）中，通常提供了填充因子（Factor Fill）进行针对性的优化。填充因子设置过小会造成页表数量膨胀，增大对磁盘的扫描范围，降低查询性能；设置过大则会在数据插入时出现写扩大，产生大量的分页，降低插入性能，同时由于数据存储不连续，也降低了查询性能。
2 LSM-Tree
LSM-Tree（Log Structured-Merge Tree）由Patrick O’Neil首先提出。而后Google在Bigtable中引入了该模型。
LSM-Tree的主要思想是借助内存将随机写转换为顺序写，提升了写入性能；同时由于大幅度降低了写操作对磁盘的占用，使读操作获得更多的磁盘控制权，读操作性能也并未受到过多的影响。
写操作简化过程如下：
- 当写入请求到达时，首先写入内存中Memtable，处理增量数据变化，同时记录WAL预写日志；
- 内存增量数据达到一定阈值后，当前Memtable会被冻结，并创建一个新的Memtable，已冻结的Memtable中的数据会被顺序写入磁盘，形成有序文件SSTable（Sorted String Table），这个操作被称为Minor Compaction（在HBase中该操作称为Flush操作，而Minor Compaction有其他含义）；
- 这些SSTable满足一定的规则后进行合并，即Major Compaction。每个Column Family下的所有SSTable被合并为一个大的SSTable。
该模型规避了随机写的IO效率问题，有效缓解了B树索引的写放大问题，极大的提升了写入效率。
NoSQL广泛使用了LSM-Tree模型，包括HBase、Cassandra、LevelDB、RocksDB等K/V存储。
当然LSM-Tree也存在自身的缺陷：
首先，其Major Compaction的操作非常重，影响联机读写，同时也会产生写放大。因为这个原因，HBase的使用中通常会禁止系统自动执行Major Compaction。
Major Compaction操作的意义是降低读操作的时间复杂度。设系统包含多个SSTable文件，共有N数据，SSTable平均包含m数据。执行读操作时，对单一SSTable文件采用折半查找方法的时间复杂度为O(log2m)，则整体时间复杂度为O(N/m* log2m)；合并为一个SSTable后，时间复杂度可降低到O(log2N)其次是对读效率的影响，因为SSTable文件均处于同一层次，根据批量写的执行时序形成若干文件，所以不同文件中的Key（记录主键）会出现交叉重叠，这样在执行读操作时每个文件都要查找，产生非必要的I/O开销。
最后是空间上的放大（Space Amplification），最坏情况下LSM Tree需要与数据大小等同的自由空间以完成Compact动作，即空间放大了100%，而B+树的空间放大约为1/3。
3 Leveled LSM Tree
Leveled LSM Tree 的变化在于将SSTable做了进一步的分层，降低写放大的情况，缩小了读取的文件范围，在LevelDB 中率先使用，随后Cassandra 1.0也引入了该策略。
SSTable的层次化设计策略是：
- 单个SSTable文件大小是固定的，在Cassandra中默认设置为5M；
- 层级从Level 0开始递增，存储数据量随着层级的提升而增长，层级之间有一致的增长系数（Growth Factor）。Cassandra中Growth Factor设置为10，Level 1文件为1-10M则Level 2 文件为10-100M，这样10TB数据量会达到Level 7；
- Level 0的SSTable比较特殊，固定为4个文件，且文件之间存在Key交叉重叠的情况，从Level 1开始，SSTable不再出现Key交叉情况；
- Level 0层的SSTable超过容量大小时，向Level 1 Compaction，因为存在Key交叉，所以要读取Level 0的所有SSTable；当Level 1 的文件大小超过阈值时，将创建Level 2的SSTable并删除掉Level 1原有的SSTable；当Level 1的Key范围对应Level 2的多个SSTable时，要重写多个SSTable，但由于SSTable的大小固定，所以通常只会涉及少数的SSTable。
多个有序的SSTable，避免了Major Compaction这样的重量级文件重写，每次仅更新部分内容，降低了写放大率。
对于读取元数据来锁定相关的SSTable，效率显然超过了对所有SSTable的折半查找和Bloom Filter。因此，读取效率得到了显著提升。
该策略下，Compaction的操作更加频繁，带来了更多I/O开销，对写密集型操作而言，最终结果是否能够得到足够的效率提升存在不确定性，需要在应用中权衡。
4 NewSQL的策略
NewSQL 数据库的存储层普遍都采用K/V存储，所以基本沿用了LSM Tree模型。其中CockroachDB和TiDB都在KV层使用RocksDB。
OceanBase采用了不同的方法规避Major Compaction的影响，大体是利用闲置的副本（Follower）进行Compaction操作，避免了对读操作的阻塞，在Compaction完成后，进行副本的角色的替换。
5 小结
传统关系数据库的存储引擎设计都是面向磁盘的，大多都基于B+树。B+树通过降低树的高度减少随机读、进而减少磁盘寻道次数，提高读的性能，但大量的随机写会导致树的分裂，从而带来随机写，导致写性能下降。
NewSQL的底层存储引擎则多采用LSM，相比B+树LSM将对磁盘的随机写变成顺序写，大大提高了写的性能。不过LSM的的读由于需要合并数据性能比B+树差，一般来说LSM更适合应在写大于读的场景。当然这只是单纯数据结构角度的对比，在数据库实际实现时还会通过SSD、缓冲、bloom filter等方式优化读写性能，所以读性能基本不会下降太多。
NewSQL数据由于多副本、分布式事务等开销，相比单机关系数据库SQL的响应时间并不占优，但由于集群的弹性扩展，整体QPS提升还是很明显的，这也是NewSQL数据库厂商说分布式数据库更看重的是吞吐，而不是单笔SQL响应时间的原因。
