B+树和LSM树是最常见的单机存储引擎，前者代表是Mysql等事务性数据库，后者代表是Rocksdb等nosql KV数据库。

B树和B+树

B树是一种平衡的多叉树，通常说m 阶B树，树的阶指的是B树中节点的子节点数目的最大值。

B树必须满足如下条件：

  1. 所有叶子节点都在同一层级；
  2. 除了根节点以外的其他节点包含的key值数量在[m/2]-1到m-1的数据范围；
  3. 除了根节点和叶子节点外，所有中间节点至少有m/2个子节点；
  4. 根节点如果不是叶子节点的话，它必须包含至少2个孩子节点；
  5. 拥有n-1个key值非叶子节点必须有n个孩子节点；这要求每个key的前后都有指向子节点的指针
  6. 一个节点的所有key值必须是升序排序的；

Btree

B+树是应文件系统所需而产生的 B 树的变形树。B+树的特征：

  1. B+树包含2种类型的节点：内部节点（也称索引节点）和叶子节点。根节点本身即可以是内部节点，也可以是叶子节点。
  2. B+树与B树最大的不同是内部节点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子节点中；
  3. m阶B+树表示了内部节点最多有m-1个key（或者说内部节点最多有m个子树，和B树相同），阶数m同时限制了叶子节点最多存储m-1个记录；
  4. 内部节点中的key都按照从小到大的顺序排列，对于内部节点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子节点中的记录也按照key的大小排列；
    每个叶子节点都存有相邻叶子节点的指针，叶子节点本身依key的大小自小而大顺序链接；

B+tree

B+ 树相比 B 树，最大差异是非叶子节点不再存储具体数据，以及叶子节点是链表结构。非叶子节点不再存储具体数据，这使得 B+ 树更加扁平化，查找效率更高。叶子节点是链表结构，这使得 B+ 树更适合用在范围查找的场景中。

在Mysql的InnoDB中，每个数据表的索引都会有一个B+树维护。在主键索引中，B+树的节点是16K固定大小的page，page内部由记录链表构成，每个记录的key是主键，value则是行数据。B+树查询相当于一个巨大的二分查找，先根据主键和区间定位到主键所属的page，然后在page内部遍历记录链表找到key所在的记录和行数据。

B+树的优势

  1. B+树的非叶子节点不存储数据，内存可以容纳，实际磁盘IO数量只有访问叶子节点的一次。
  2. B+树叶子节点有序，互相有链接，范围查询能充分利用磁盘的顺序读优势
  3. B+树的节点是固定大小的page，page对齐落盘。但如果数据页没有在cache，写操作需要等待数据页从磁盘中读取，写性能不如读

LSM树

LSM（Log-Structured Merge Tree）相比B+树，写性能高，读性能稍逊。

LSM 树由两部分组成：

  1. MemTable（内存表）

是一个可变的有序数据结构（如红黑树或跳表），存储数据的最新写入。使用redolog保证memtable的数据安全，写操作先顺序写redolog和MemTable，提高写性能。

  1. SSTable（Sorted String Table）

当 MemTable 达到一定大小时，会作为SSTable文件写入磁盘。SSTable 是不可变的。
SSTable 通常通过多个层级组织，使用compaction策略减少存储。

LSM的特点

  1. 写性能高
  2. 读性能不稳定，随着需要读的数据位置层次由高到低，读性能逐渐下降。读操作存在大量不必要的磁盘读操作，可用布隆过滤器缓解
  3. 写放大，写操作先写redolog和memtable，memtable后台dump到sst, 旧sst再重新comapction到新的sst，后台存在大量读写。大量写放大可能增加磁盘IO压力影响前台IO，磁盘寿命。
  4. 空间放大。更新键和删除键同样写入到redolog和memtable，不同层级的SSTable可能存在相同但新旧不同的键。