B+树和LSM树比较
前言
由于传统的机械磁盘具有快速顺序读写，慢速随机读写的访问特性，为了改变这个特性，文件系统或数据系统通常会对数据进行排序后存储，加快数据检索速度，这就需要保证数据在不断更新、插入、删除保持依然有序，目前最广泛的做法就是使用B+树和LSM树。
B+树
B+树是一种专门针对磁盘存储而优化的N叉排序树，以树节点为单位存储在磁盘中，从根开始查找所需数据所在的节点编号和磁盘位置，将起加载到内存中然后继续查找，直到找到所需的数据。
B+ 树的三个特点：
- 节点的子树数和关键字数相同
- 非叶子节点仅用作索引，它的关键字和子节点有重复元素
- 叶子节点形成有序链表，包含了全部数据，同时符合左小右大的顺序
- B+树改进了B树, 让内结点只作索引使用, 去掉了其中指向data record的指针, 使得每个结点中能够存放更多的key, 因此能有更大的出度. 这有什么用? 这样就意味着存放同样多的key, 树的层高能进一步被压缩, 使得检索的时间更短。
- B树和B+树，首先从二叉树说起，因为会产生退化现象，提出了平衡二叉树，再提出怎样让每一层放的节点多一些来减少遍历高度，引申出m叉树，m叉搜索树同样会有退化现象，引出m叉平衡树，也就是B树，这时候每个节点既放了key也放了value，怎样使每个节点放尽可能多的key值，以减少遍历高度呢（访问磁盘次数），可以将每个节点只放key值，将value值放在叶子结点，在叶子结点的value值增加指向相邻节点指针，这就是优化后的B+树。
- 由于底部的叶子结点是链表形式, 因此也可以实现更方便的顺序遍历。
目前数据库多采用两级索引的B+树，树的层次最多三层，因此可能需要5次磁盘访问才能更新一条记录（三次磁盘访问获得数据索引以及行id，然后再进行一次数据文件读操作及一次数据文件写操作）
代表数据库：MySQL、Oracle等关系型数据库
LSM树
LSM树（Log-Structured Merge Tree）可以看作一个N阶合并树，数据写操作（包括插入、修改、删除）都是内存中进行，并且都会创建一个新记录（修改会记录新的数据值，而删除会记录一个删除标志），而这些数据在内存中仍然是一颗排序树，当数据量超过内存阈值后，会将这个排序树和磁盘最新的排序树合并。当这颗排序树数据量超过内存阈值后，和磁盘上下一级的排序树合并，合并过程中，会用最新更新的数据覆盖旧的数据（或者记录成不同版本）
理论上，可以是内存中树的一部分和磁盘中第一层树做合并，对于磁盘中的树直接做update操作有可能会破坏物理block的连续性，但是实际应用中，一般LSM树有多层，当磁盘中的小树合并成一个大树的时候，可以重新排好顺序，使得block连续，优化读性能。
LSM树的特点：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘
LSM树的核心思想：放弃部分读性能，提高写性能
代表数据库：nessDB、LevelDB、HBase等非关系型数据库
对比
1、当写比读多时，LSM树相比于B+树有更好的性能，因为随着insert操作，为了维护B+树结构，节点分裂。读磁盘的随机读写概率会变大，性能会逐渐减弱。 LSM树相比于B+树，多次单页随机写变成一次多页随机写,复用了磁盘寻道时间，极大提高写性能。不过付出代价就是放弃部分读性能。
2、B+ 树每次都需要查询到叶子节点，查询性能稳定，叶子节点形成有序链表，范围查询方便
参考《大型网站技术架构 核心原理与案例分析》