概述

前边我们已经了解了二叉查找树、红黑树。这里我们认识下B树和B+树，我们经常会听到说，mysql里的索引用的B+树...本篇就探索一下它的原理，要了解B+树，还需要先了解B树，因为B+树是B树的一个变种。

B树

B树 ，B-tree,即Balanced Tree ，因为有些人译作B-树，其实就是B树。它和二叉查找树不同，是一种多路平衡查找树,它有以下几种特征:

• 根结点至少有两个子节点。
• 每个中间节点都包含k-1个元素和k个子节点，其中 m/2 <= k <= m
• 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
• 所有的叶子节点都位于同一层。
• 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个子节点包含的元素的值域分划。

B树

上图中M=3,拿其中的(8,12)节点为例,有三个指针指向(3,5)、(9,10)、(13,15),(3,5)中的元素小于8,(9,10)大于8并小于12，(13,15)中的元素大于12，符合B树的特征

B树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的子节点指针为空，或已经是叶子节点。
B树的查询次数可能不比二叉查找树少,但是磁盘的IO次数少，性能高。

B树的节点插入和删除 需要实现B树的各类特征，保持自平衡，需要更新树的结构。
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占
M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并

B树主要运用于文件系统及部分数据库索引,比如MongoDB这类文档型数据库。

B+树

B+树是B树的变体，也是一种多路搜索树,查询性能比B树更高。它除了有B树的特性外,还有自身的特征,一个m阶的B+树有如下几个特征:

• 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
• 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树

上图中M=3,中间子节点存的是索引,到达叶子节点才是所存的数据，每个叶子节点中都带有指向下一个叶子节点的指针，形成一个有序的链表。B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找。

B+树比较适合文件索引系统,Mysql的索引采用的是B+树。