文章目录1 .背景2 .二叉树、平衡二叉树和红黑树3. B树(B-木)和B树) 3.2 B树) 3.2 B树和B树总结： 3.4为什么B tree比B树更实用的操作系统的文件索引和数据3.5 MySIAM和InnoDB的b树3.5.1 MySIAM索引实现3.5.2 InnoDB索引实现4. LSM树4.1 LSM树与其他结构的比较5 .总结| Ref
1 .背景
众所周知，底层存储(如MySQL MongoDB HBase )是典型的数据库，它使用各种树结构(如b树LSM树)，为什么要使用这些结构呢？
线性结构在插入搜索中需要大量时间。 这在数据量大的情况下尤为明显。 因此，MySQL引擎很少使用线性索引。 MySQL的所有主要存储引擎都使用B-/B树索引。
让我们先复习一下基础知识：
动态搜索树主要有二叉搜索树、平衡二叉树、红黑树、b树、b树。
前三种是典型的二叉搜索树，搜索的时间复杂度o(log2n )与树深有关，降低树深也可以提高搜索效率。 因此，提出了平衡多重搜索树，即b树及b树。
2 .二叉树、平衡二叉树和红黑树二叉树(binary search tree )，又称二叉树，是一种空树，或具有以下性质的二叉树：
如果该树左侧的子树不为空，则左侧的子树的所有节点的值小于根节点； 如果树的右子树不为空，则右子树的所有节点的值都大于根节点。 这棵树的左右子树也是二叉搜索树。 可能的二叉树索引如下。
二叉树在保留二叉树搜索的基础上，实现了可以直接修改插入和删除指针，大大提高了插入和删除的效率。 但是由于二叉树形状的不确定性，极端查询时间的复杂度和平均查询时间的复杂度相差很大。 例如，如果插入数据时本身按从小到大的顺序插入，则在创建索引时会创建一个极右倾斜的树。 他是二叉树，但此时索引的检索效率与扫描效率，即o(n )相等，在上图的情况下最多只需要检索两次。 所以有平衡的二叉树(AVL tree )和红黑树(redblack tree )
平衡二叉树上所有节点的平衡因子balance factor的值仅为- 1，0，1，保证了搜索时的效率问题，但同样频繁调整树的节点，降低了插入和删除的效率。 红黑树并不追求“完全的平衡”。 ——只是部分满足平衡要求，降低了对旋转的要求，提高了性能。
红海可以用o(log2n )的时间复杂度进行检索、插入、删除操作。 另外，由于其设计，任何不平衡都将在3圈内解决。 当然，还有更好的，但可以实现更复杂的数据结构，在进一步旋转内达到平衡。 但是红黑树给我们提供了比较“便宜”的解决方案。 红树算法的时间复杂度与AVL相同，但统计性能高于AVL树。
3. B树(B-树)和b树(3.1 B树) b树是平衡复用搜索树，它们与b树的最大区别在于，B树的结点可以有多个子女是几个到几千个。 那么为什么b树和红黑树很相似呢？ 因为，和红黑树一样，包含n个节点的b树的高度也是o(lgn )，但是有可能比红黑树的高度小很多，其分支因子应该很大。 因此，b树在o(logn )时间内，可以实现插入(insert )、删除)等各种各样的动态集合操作。
B树的定义如下。
根节点至少有两个子节点，每个节点有M-1个key，M-1和M key的子节点按升序排列的值介于M-1和M key对应的值之间，其他节点至少有M/2个子节点下图是M=4的四阶b树。
B树搜索:从根节点出发，对节点内的关键字(有序)数组进行二分搜索，如果找到则结束，否则进入查询关键字所属范围的子节点； 重复直到对应的儿子指针为空或已经成为叶的节点；
b树的特性：
关键词集合出现在整树分布的任意一个关键词，只出现在一个节点上； 搜索可能以非叶节点结束(树的所有节点都包含数据，与b树不同)； 其检索性能与在关键词全集内进行二分检索相同； 下面是插入b树的演示视频，依次插入：
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
3.2 B木b木是对b木的变形，与b木的区别如下。
有n个子树的节点中包含n个关键字，各关键字不保存数据，仅用于索引，所有的数据保存在叶节点中。 的所有叶节点中包含所有关键字的信息和指向包含这些关键字的记录的指针，叶节点本身按照关键字大小从小到大的顺序链接。 所有的非终结节点可以视为索引部分，并且每个节点只包括子树(根节点)中的最大(或最小)关键字。 将链指针添加到所有叶的节点将有助于查找和遍历区间。 所有的关键词都出现在叶子的节点上； 下图中M=3的b树：
B树搜索： B树也基本相同。 不同的是，b树只有到达叶节点才能命中。 (B-树可以在非叶节点上命中。 )其性能也与在关键词全集中进行一次二分搜索相同。
b的特性：
非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；B+树的叶子结点都是相链的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。 3.3 B树和B+树总结：B树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B+树虽然优点很多，但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。下面是B 树和B+树的区别图：
3.4 为什么说B+tree比B树更适合实际应用中操作系统的文件索引和数据库索引？B+tree的磁盘读写代价更低
B+tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
B+tree的查询效率更加稳定
由于非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。
3.5 MySIAM与InnoDB的B+树 3.5.1 MySIAM索引实现MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：
这里设表一共有三列，假设我们以Col1为主键，则图8是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，如图：
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
3.5.2 InnoDB索引实现InnoDB也使用B+Tree作为索引结构，但具体实现依然是有差异的。
第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：
这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
4. LSM树日志结构的合并树（LSM-tree）是一种基于硬盘的数据结构，与B+tree相比，能显著地减少硬盘磁盘臂的开销，并能在较长的时间提供对文件的高速插入（删除）。然而LSM-tree在某些情况下，特别是在查询需要快速响应时性能不佳。通常LSM-tree适用于索引插入比检索更频繁的应用系统。
LSM树核心思想的核心就是放弃部分读能力，换取写入的最大化能力。LSM Tree ，这个概念就是结构化合并树的意思，它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入到磁盘中，而可以先将最新的数据驻留在内存中，等到积累到足够多之后，再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的，可以通过合并排序的方式快速合并到一起)。
LSM树索引结构上图所示。内存部分导出形成一个有序数据文件的过程称为flush。为了避免flush影响写入性能，会先把当前写入的MemStore设为Snapshot，不再容许新的写入操作写入这个Snapshot的MemStore。另开一个内存空间作为MemStore，让后面的数据写入。一旦Snapshot的MemStore写入完毕，对应内存空间就可以释放。这样，就可以通过两个MemStore来实现稳定的写入性能。
目前常见的主要的三种存储引擎是：lcdxlc、B+树、LSM树：
lcdxlc存储引擎：是lcdxlc表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，lcdxlc表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，lcdxlc表性能最好。B+树存储引擎是B+树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（Mysql等）。LSM树（Log-Structured MergeTree）存储引擎和B+树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。上面三种引擎中，LSM树存储引擎的代表数据库就是HBase。和B+树不同的是，LSM树的索引对写入请求更友好。因为无论是何种写入请求，LSM树都会将写入操作处理为一次顺序写，而HDFS擅长的正是顺序写（且HDFS不支持随机写），因此基于HDFS实现的HBase采用LSM树作为索引是一种很合适的选择。
LSM树和B+树的差异主要在于读性能和写性能进行权衡。在牺牲的同时寻找其余补救方案：
LSM具有批量特性，存储延迟。当写读比例很大的时候（写比读多），LSM树相比于B树有更好的性能。因为随着insert操作，为了维护B+树结构，节点分裂。读磁盘的随机读写概率会变大，性能会逐渐减弱。
B树的写入过程：对B树的写入过程是一次原位写入的过程，主要分为两个部分，首先是查找到对应的块的位置，然后将新数据写入到刚才查找到的数据块中，然后再查找到块所对应的磁盘物理位置，将数据写入去。当然，在内存比较充足的时候，因为B树的一部分可以被缓存在内存中，所以查找块的过程有一定概率可以在内存内完成，不过为了表述清晰，我们就假定内存很小，只够存一个B树块大小的数据吧。可以看到，在上面的模式中，需要两次随机寻道（一次查找，一次原位写），才能够完成一次数据的写入，代价还是很高的。
LSM优化方式：
Bloom filter: 就是个带随机概率的bitmap,可以快速的告诉你，某一个小的有序结构里有没有指定的那个数据的。于是就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升，但付出的是空间代价。compact:小树合并为大树:因为小树性能有问题，所以要有个进程不断地将小树合并到大树上，这样大部分的老数据查询也可以直接使用log2N的方式找到，不需要再进行(N/m)*log2n的查询了 5. 总结 | Ref本文只粗略的讲解了几个树的结构，数据库真正使用的结构其实还有优化
https://mp.weixin.qq.com/s/u7jnYRiiHgGZYGwrf-sNbAHBase原理与实践https://draveness.me/whys-the-design-mongodb-b-tree/ 为什么MongoDB使用B树