十步杀一人，千里不留行
上一篇讲到了bupt的老师使用了数据库来管理学校的图书，从此事半功倍，那么进入了21世纪，我们的老一辈管理员都退休了，新上任的小伙子是个技术宅，总喜欢倒腾，于是他尝试选择不同的数据结构的数据库存储引擎 ，于是他首选了B+ 树和LSM tree，于是故事就从这里开始了。
当今的计算机都是冯诺依曼体系结构，我们的计算机师以运算器为中心，I/O设备与存储器间的数据传送都要经过运算器，事实上我们现在的处理器的速度是相当之高，相对来说我们的硬盘等IO设备就慢多了，就拿当今服务器上使用的较多的韩国三星的SSD或者东芝的SSD来说，IO也是远低于RAM的读写速率，当然了ROM和RAM的存储方式不同也无可厚非（关键是RAM不具备可靠性，掉电数据就会丢失）。那么当我们需要数据库读写足够快的时候，我们的IO读写的耗时就成了消耗时间的罪魁祸首，所以减少IO次数，且随着数据量增加IO次数稳定是数据库存储引擎的核心要务，当然了cpu等指标也是很重要滴，只是不是今天的主人公。下边就分析B+树和LSM两者是如何有效的控制IO次数的。
B+ 树的结构如下图：
非叶子结点的子树指针与关键字个数相同；
非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树 ;
为所有叶子结点增加一个链指针；
所有关键字都在叶子结点出现；
看完上图我相信大家都清楚了B+树的结构了，那么不得不唠叨一句B-树，它和B+树的最大区别在于它的非叶子节点还存储了data数据，于是导致数据量很大的时候，树的层数可能会比较高，导致随着数据量增加IO次数的控制不如B+树优秀。就不细讲了，有兴趣的同学可以百度一下，都说的非常清楚。
B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。
可能上面例子中只有22条数据记录，看不出B+Tree的优点，下面做一个推算：
InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或long（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为10^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。
在数据库中，B+Tree的高度一般都在2~4层。mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。
数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。
(以上三段摘选自https://me.csdn.net/hao65103940的博客，由于写的很好，所以我就不赘述了，更详细的可以移步去看这篇文章)
那么接下来就来说说缺点：B+树在查询过程中应该是不会慢的，但如果数据更新或者插入完全无序的时候，比如先插入0 ，然后80000，然后200，然后666666， 这样跨度很大的数据的时候，由于不在一个磁盘块中，就需要先去查找到这个数据。数据非常离散，那么就意味着每次查找的时候，他的叶子节点很可能都不在内存中，这时候性能的瓶颈就出现了。并且随机写产生的子树的分裂等等，产生很多的磁盘碎片，也是不太友好的一面。
接下来说说LSM tree：原名log structed merge tree
原理很简单就是先顺序写log，log就是每一次的操作内容，比如操作type，操作的数据的key，value等信息，写入硬盘，再把每一次的数据先写在内存中，等内存中数据达到一定的数量的时候再按照数据的排序方式有序的写入硬盘，这时候每一次数据的写入都是顺序写，并且只是写入内存，所以对外体现的速度会很快。可靠性上由于已经写入了log，即使内存掉电，内存数据丢失，重新启动的时候也可以通过盘中的log来恢复丢失的数据。综上，LSM tree变随机写为顺序写，内存写，所以LSM tree的写入性能非常优秀。
LSM tree的结构图如下，先写内存中的memtable，写到一定大小变成imemtable，不再允许写入，开始写新的memtable，immemtable开始做flush，写入到硬盘。L0层的数据写道一定大小的时候，就开始做整理，按照排序方式将其compactio到L1层，同样L1层写到一定大小也是如此，LSM tree最大的点是没有删除，删除也是一次写入，比如先写入Key：1 ，value：1的数据，现在要修改成Key：1 ，value：2，那么直接插入新数据即可，读取的时候从上往下读取，最先写入的一定会被先读取到，等下一次做compaction的时候会把Key：1 ，value：1这条数据从硬盘上删除。删除也是如此，插入一条本数据，带上删除标志位，下一次做compation，会将这个key的数据彻底删除。所以LSM相当于启动了前后两个面，对于新数据来说都是在内存中写，但是硬盘中的数据在源源不断地往下一层做着compation，不断地往下做着整理。这样保证了写入的性能又保证了数据不会混乱，当然了当compation的性能赶不上的时候也会出现流控的问题，这个以后再论。
说完了LSM的写，再来说说读，由于每一层的数据都是有序的（L0层是单个SST文件中有序，其他层都是整层有序），举个例子L0的第一个文件是a-z之间排序的，L1的第一个文件可能只是a-c之间有序。所以查询的时候对于硬盘上的读取，除了L0每一层只需要读取一个文件即可判断该数据是否存在于当前层，并且由于Bloom 过滤器的存在（过滤器下一节再详细讲吧），这样我们对于每一层的读取并不需要将该文件完全读取，只需要读取一小部分即可判断要查询的数据是否在当前的文件中（这部分通常会被放入cache，一般都是百分之百命中），这样，LSM tree的读取性能也不会非常差，总之是差于B+树，但是差距并不是非常的大。也是可以接受。
读写两方面的综合衡量，LSM树和B+树可以说各有千秋。根据不同而的场景，选择不同的存储引擎才是最重要的。
