B/B+ 树和MySQL

B 树

B树是一种 多路平衡查找树, B是平衡（Balance）的意思，不是 Binary，也被翻译成 B-树（B-tree），许多数据库系统一般都使用B 树或者B 树的各种变形结构。由于它的分支比较多，所以B 树的高度一般比二叉树小很多。

m阶（m >= 2）的B树有如下特性：

1. 树中每个节点最多含有m个子节点;
2. 除根节点和叶节点外，其他每个节点至少有 ceil(m/2)个子节点；
3. 若根节点不是叶节点，则至少有2个子节点；
4. 所有 叶节点都出现在同一层；
5. 节点中的关键字按照生序排序；
6. 非叶节点中关键字数量在 [ceil(m/2)－1, m-1]。

所以假设一棵 3 阶 B树，除了关键字顺序排列，它还需要满足以下条件:

1. 每个节点最多 3 个子节点;
2. 除了跟节点和叶节点，其他节点至少有2个子节点；
3. 根节点如果不是叶节点，至少有2个子节点；
4. 非叶节点中关键字数量n， 则 2 <= n <= 3;

图1

.

插入操作

1. 首先判断插入元素是否已经在 B 树中，如果在的插入结束；
2. 然后在叶节点插入该元素，需要注意：
   1. 叶节点空间足够，只需要移动叶节点中大于插入元素的其他元素；
   2. 叶节点空间不够，则需要对该节点进行分裂，取插入后的节点的中间元素，上移到父节点（父节点满了也需要分裂，直到根节点）, 将大于中间元素的关键字分裂到新的相邻右节点中。

删除操作

1. 首先查找 B 树中是否有该元素，查找到后进行删除
   1. 如果该元素有左右子节点，则上移子节点中的相近元素（左子树的最右元素 或 右子树的最左元素）
   2. 如果没有则直接删除
2. 删除和移动元素后，如果某节点中元素个数小于 ceil(m/2)，则需要 合并 操作；
   1. 如果该节点相邻兄弟节点是“丰满”的节点（节点元素数量 大于 ceil(m/2)），则将父节点的元素挪到删除元素所在节点，“丰满”的兄弟节点上移一个元素到父节点上；
   2. 如果没有“丰满”的兄弟节点，则该节点与其某兄弟节点合并成一个节点来满足条件；

B+ 树

B+ 树是 B 树的一种变体，也是一种多路平衡查找树， 它和 B 树主要不同点在：

1. 每个节点最多含有 m 个关键字
2. 所有的叶节点中包含了全部关键字信息，以及指向还有这些关节字记录的指针，且叶节点本身按照关键字顺序相互连接；
3. 所有非叶节点可以看成是索引部门，节点中仅包含其子树中最大关键字。

图2

.

对比

| B 树 | B+ 树
------------- | ------------- | ------------------------
关键字 | 关键字分布在整颗树中，只出现一次 | 所有关键字都出现在叶节点的链表中，且有序
搜索命中 | 可能在树中任意节点命中，搜索结束 | 只可能在叶节点中命中，查询路径稳定
非叶节点 | 非叶节点包含关键字，也包含数据 | 非叶节点相当于索引帮助搜索到叶节点，叶节点相当于存储关键字数据的数据层
叶节点 | | 增加了链表指针，相当于存储关键字数据的数据层

B/B＋ 和数据库

B+ 树作为数据库索引的优势

1. B＋树所有的内部节点都没有关键字的具体信息，这样可以使内部节点相对于B 树更小。一个硬盘块中包含的节点信息更多，一次性读取内存中的关键字也更多，相对来说 IO 读写次数就降低了。
2. B+ 树的查询效率更加稳定，任务关键字的查找必须要走一条从根节点到叶节点的路径，所有关键字查询的路径差多相同，每个数据查询效率详单；
3. 由于叶节点的链表结构，更方便扫库和范围查询，B树必须用中序遍历的方法按序扫库， 而B+树直接从叶子结点挨个扫一遍就完了，B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。

聚簇

MySQL 上最主流的两个引擎 MyISAM 和 Innodb 虽然都采用 B+ 树作为索引树，但适用中存在差别：

非聚簇

MyISAM 在B＋ 树的叶节点存储关键字外，还存储对应数据的存放地址，主索引和辅助索引没有区别，只是主索引中的关键字一定是唯一的。这样的索引属于非聚簇索引。

聚簇

InnoDB 在B+ 树的叶节点存储关键字，同时也将对应数据存放在哪儿。这样聚簇索引的数据物理存放顺序与索引顺序是一致，即只要索引是相邻的，那么对应的数据一定也是相邻存放在磁盘上。如果主键不是自增id，那么可以想 象，它会干些什么，不断地调整数据的物理地址、分页，当然也有其他一些措施来减少这些操作，但却无法彻底避免。但，如果是自增的，那就简单了，它只需要一 页一页地写，索引结构相对紧凑，磁盘碎片少，效率也高。

如果是辅助索引，叶节点存储主索引。所以如果通过辅助索引查询数据，需要先找到辅助索引，然后根据叶节点的主索引再去搜索主索引叶节点获取对应数据。

因为MyISAM的主索引并非聚簇索引，那么他的数据的物理地址必然是凌乱的，拿到这些物理地址，按照合适的算法进行I/O读取，于是开始不停的寻道不停的旋转。聚簇索引则只需一次I/O。

不过，如果涉及到大数据量的排序、全表扫描、count之类的操作的话，还是MyISAM占优势些，因为索引所占空间小，这些操作是需要在内存中完成的。

索引建议

1. 索引大小应该尽可能小，减少IO读取，另索引最大长度是768 byte
2. 主索引尽量采用自增id
3. 辅助索引尽量不要有NULL
4. 字段数据可能很长，可以使用前几个字符作为索引，而不需要全部索引
5. 索引应该有选择性，即索引列的数据尽量每个纪录都不一样。

MongoDB

和关系型数据库不同，MongoDB 采用的是B 树作为其索引结构，至于其为什么要使用 B 树，好吧，我承认我不知道 。

参考来源

http://blog.csdn.net/v_july_v/article/details/6530142

https://en.wikipedia.org/wiki/B-tree

http://www.cnblogs.com/zl0372/articles/mysql_14.html

http://zhangliyong.github.io/posts/2014/02/19/mongodb-index-internals.html