在介绍 B-Tree 前先稍稍介绍两个东西
二叉查找树
二叉查找树的几个性质：
- 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点（no duplicate nodes）。
- 中序遍历就可以得到一个有序的序列
二叉查找树查找、插入的时间复杂度为 O(log n)
二叉查找树的具体查找，添加，删除操作这里就不展开了
二分查找
二分查找每次把搜索区域减少一半，时间复杂度为 O(log n)。
其优点是比较次数少，查找速度快，平均性能好；缺点是要求待查表为有序表，且插入删除困难。
大致的核心实现如下（当然你很容易将递归改为循环）：
int a[100];
int search(int left, int right, int value)
{
int middle = left + ((right - left) >> 1);
if (value < a[middle])
{
right = middle - 1;
return search(left, right, value);
}
else if (value > a[middle])
{
left = middle + 1;
return search(left, right, value);
}
return middle;
}折半查找方法适用于不经常变动而查找频繁的有序列表。
很简单的一个算法，但是据说很多人不能一次性正确的写出实现。
首先是要注意数组边界，其次上边计算中间值时没有使用 ‘(right + left) >> 1’, 是因为 当量级足够大时，’+’ 操作会造成溢出。
B-Tree
与二叉查找树、平衡二叉查找树、红黑树等二叉树形结构相比，B-Tree 是一种多路查找树。不像前者每个节点最多可以有两个孩子节点， B-Tree 可以有许多子女，而且B树也可以在O(logn)时间内，实现各种如插入，删除等集合操作。更大的分支因子可以降低树的高度从而降低 频繁磁盘I/O读写所造成的查询效率低下。许多数据库系统都会使用B树或者B树的各种变形结构。
B-Tree 又叫平衡多路查找树。 一棵m阶的B-Tree有如下性质：
- 树中每个结点最多含有m个孩子（m>=2）
- 除根节点和叶子节点外，其它每个节点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）
- 根结点至少有2个孩子，根节点同时是叶子节点除外
- 所有叶子结点都出现在同一层
- 内部节点至少半满
下图就是一个简单的3阶 B-Tree:
对于它的查找其实也很简单，比如我们要查找31：那么首先根据算法发现 31>20 & 31<33，找到指向块[24,28]的指针；根据指针找到块[24,28]， 根据算法发现 31>28，找到指向[29,31]的指针；根据指针找到块[29,31]，最终找到31。
我们知道，在一个有序序列中进行插入操作简直是个灾难，我们不但要给插入对象制造空间，还要对后续对象进行移位。
接下来来看一下 B-Tree 的插入过程（B-Tree是从叶子节点进行插入的）
我们拿一颗5阶树做例子，这样每个节点最多有5个孩子，同理每个节点最多就只能有4个关键字：
- 例如插入16，发现节点空间是足够的（小于4），直接插入就行了
- 再插入18，发现节点空间已经满了（等于4），这时就需要进行分裂操作，将一半数量的关键字元素分裂到新的其相邻右节点中，中间关键字元素上移到父节点中，并移动相关指针。 插入时，发现空间不够所以将节点分裂为两个节点并将中间关键字18上移到父节点，关键字12、16留在当前节点，关键字20、24右移组成新节点。
- 那如果根节点满了怎么处理呢，根节点满了的话也要进行分裂操作，同时中间关键字元素向上移动形成新的根节点，这时树的高度就会增加。 如下图，如果我们要插入35，发现节点[29，31，33，36]已经满了，对此节点进行分裂操作并把中间关键字元素33向上移入上级节点，这时发现上级节点也满了， 故对上级节点进行分裂，把中间关键字元素33向上移动形成新的根节点，树的高度增加1。
那么删除操作：
- 例如删除41，通过查找发现该元素并没有左右孩子节点，直接删除即可，删除后其后的43、45依次向前移位
- 那如果删除52，通过查找发现有左右孩子节点，则上移左孩子最右边的节点或右孩子最左边的节点（看其孩子结点是否丰满，也就是节点中元素个数大于ceil(m/2)-1） 到父节点中，移动后其孩子节点中元素个数大于ceil(m/2)-1，操作结束
- 删除36，删除后发现节点只剩一个关键字元素，这不符合 “每个节点至少有[ceil(m / 2)]个孩子” 的规则，将从相邻兄弟节点中比较丰满的节点来处理， 先从父节点下移一个元素，然后将最丰满的相邻兄弟结点中上移最后或最前一个元素到父节点中。那么在这里的处理就是先移除36，然后发现节点[41,43,45]是丰满的， 从父节点下移元素39，然后上移41进入父节点。
- 删除非叶子结点中的28，有左右孩子节点，故上移孩子节点中的29进入父节点，然后发现移动后子节点只剩一个元素，而兄弟节点都不丰满所以只能进行合并操作， 将[12,14]节点与[31]节点合并形成节点[12,14,29,31]，这时父节点[10]只剩一个元素，然后查看发现其兄弟节点[39,52]不丰满只能进行合并操作， 父节点合并形成新的根节点[10,33,39,52]，同时树的高度减1。
B-Tree 的特点：
- 保持键值有序，以顺序遍历
- 使用层次化的索引来最小化磁盘读取
- 使用不完全填充的块来加速插入和删除
- 通过优雅的遍历算法来保持索引平衡
- 通过保证内部节点至少半满来最小化空间浪费
- 一棵B树可以处理任意数目的插入和删除
B+ -Tree
B+ -Tree是B-Tree的一个变种。那么它们有什么不一样呢（同为m阶）：
- 叶子节点存储了所有的关键字信息
- 叶子节点的最后一个指针指向相邻的下一个叶子节点
图
MySQL普遍使用B+Tree实现其索引结构，在InnoDB引擎中数据文件本身就是索引文件，其树形结构的每个叶子节点都包含了完整的数据记录， 这棵树的主干是由数据表的主键组成的，因此InnoDB表数据文件本身就是主索引。这也是为什么建议主键使用自增张字段，因为如果我们的主键是不规则的， 那么在新增数据的时候由于key的出现不规则就可能导致频繁的分裂合并节点操作，这是非常低效的。
上面提到 B+ -Tree 的各叶子节点间是有指针顺序相连的，这极大的提高了区间查询的效率，我们在查询一个区间内的数据时，只需要先查到区间头数据然后 顺着指针向后遍历即可得到区间内所有数据。
另外如果我们在非主键字段上建立索引时所使用的结构与主键索引是基本一致的，只有一点是这时的叶子节点将不会存储完整的数据记录，而是存储相应记录主键的值。