BTree与B+Tree

其实在之前的文章说说到过MySQL索引，只不过没细说，《JOIN查询与索引简介》 ，现在来看看回顾一下索引相关的数据结构，首先看看索引的定义： 索引(Index)是帮助MySQL高效获取数据的数据结构。 我不会索引就是类似于字典这样的话泛泛而谈，而是如何真正去理解索引。

根据列字段信息的特点，去用一种数据结构存储这些特点，这就是索引，如上图：我们需要把第二列的值通过二叉查找树存储起来，每一个节点都是以Key-Vlaue的形式存在，把值当做Key，把物理地址当做Value，那么只要根据二叉查找树的特性，很快就可以找到对应的物理地址，从而取出数据。

数据库常见的索引有Btree、B+tree、Hash索引等等，今天主要探讨的是BTree和B+Tree

B Tree

先看看Btree的定义：

• 根节点至少包括两个孩子
• 树中每个节点最多含有m个孩子( m>=2 )
• 除根节点和叶节点外，其他每个节点至少有ceil(m/2)个孩子，这里的ceil是取上限的意思
• 所有叶子节点位于同一层

假设每个非终端结点中包含有n个关键字信息，其中

• Ki (i=1..n)为关键字，且关键字按顺序升序排序K(i-1) < Ki
• 关键字的个数n必须满足: [ceil(m / 2) -1] <= n <= m-1
• 非叶子结点的指针: P[1]，P[2]，… P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1]，K[i])的子树

看起来是非常绕的，通过下面的图示其实是蛮好懂的：

由于B-Tree的特性，在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。

但是由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质，在这里先不讨论插入删除新的数据记录的问题。

B+Tree

B+树是B树的变体， B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。 B+树的定义基本与B树相同，除了:

• 非叶子节点的子树指针与关键字个数相同
• 非叶子节点的子树指针P[i]，指向关键字值[K[i]，K[i+1])的子树
• 非叶子节点仅用来作为索引，数据都保存在叶子节点中
• 所有叶子节点均有一个链指针指向下一个叶子结点

B+Tree更适合做索引

1、B+Tree的磁盘读写代价更低

B+Tree内部并没有指向关键字具体信息的指针，也就是不存放数据，只存放索引信息，所能容纳的关键字数量也就越多，一次性读入内存需要查找的关键字也就越多，相对来说IO读写次数也就降低了

2、B+Tree的查询效率更加稳定

由于B+Tree内部节点并不是直接指向文件内容的节点，而只是叶子节点中关键字的索引，所以任何关键字的查找必须走一条从根节点到叶子节点的路，所有关键字查询的路径长度相同，导致每一个数据的查询效率也几乎是相同的，所以查询效率更稳定

3、B+Tree更有利于对数据库的扫描

B Tree在提高了磁盘IO性能的同时，并没有解决元素遍历的效率底下的问题，而B+Tree只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对于数据库频繁使用的范围查询是非常有利的

这也就是选择B+Tree作为主流索引数据结构的原因

Hash索引

有些数据库存储引擎还支持Hash这个数据结构作为其索引哈希结构，想必大家已经非常熟悉了，就是根据哈希函数的运算，那只需经过一次定位便能找到需要的数据，相比起B+Tree索引，需要从根节点到非叶子节点，再到叶子节点才能访问到我们需要的数据，这样可能会经过多次的IO访问，所以呢，哈希索引的查询效率理论上要高于B+Tree索引。

但是Hash也是有非常明显的缺点的：

1、仅仅能满足“=” 、“IN”，不能使用范围查询

2、无法被用来避免数据的排序操作

3、不能利用部分索引建来查询

4、不能避免表扫描

5、遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高