一、概述

MySQL支援诸多储存引擎，而各种储存引擎对索引的支援可以各不相同，因此MySQL数据库支援多种索引型别，如BTree索引，杂凑索引，全文索引等等。本文只关注BTree。

二、资料机构及算法基础

1、索引的本质

MySQL官方对索引的定义为：索引是帮助MySQL高效获取资料的资料结构，所以索引是资料结构。

数据库除了维护资料之外，数据库系统还维护着满足特定算法的资料结构，这些资料结构以某种方式指向资料，这就可以在资料结构上实现高阶查询算法，这种资料结构，就是索引。

2、B-Tree和B+Tree

目前大部分数据库系统及其档案系统都采用B-Tree或者B+Tree作为索引结构。

B-Tree 指的是 Balance Tree，也就是平衡树。平衡树是一颗查询树，并且所有叶子节点位于同一层。

B+ Tree 是基于 B Tree 和叶子节点顺序访问指标进行实现，它具有 B Tree 的平衡性，并且通过顺序访问指标来提高区间查询的效能。

（1）B-Tree

为了描述B-Tree，首先定义一条资料记录为一个二元组[key, data]，key为记录的键值，对于不同资料记录，key是互不相同的；data为资料记录除key外的资料。那么B-Tree是满足下列条件的资料结构：

d为大于1的一个正整数，称为B-Tree的度。

h为一个正整数，称为B-Tree的高度。

每个非叶子节点由n-1个key和n个指标组成，其中d

每个叶子节点最少包含一个key和两个指标，最多包含2d-1个key和2d个指标，叶节点的指标均为null 。

所有叶节点具有相同的深度，等于树高h。

key和指标互相间隔，节点两端是指标。

一个节点中的key从左到右非递减排列。

所有节点组成树结构。

每个指标要么为null，要么指向另外一个节点。

如果某个指标在节点node最左边且不为null，则其指向节点的所有key小于v(key1)，其中v(key1)为node的第一个key的值。

如果某个指标在节点node最右边且不为null，则其指向节点的所有key大于v(keym)，其中v(keym)为node的最后一个key的值。

如果某个指标在节点node的左右相邻key分别是keyi和keyi+1且不为null，则其指向节点的所有key小于v(keyi+1)且大于v(keyi)。

d=2的B-Tree

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

B-Tree查询算法的虚拟码

B-Tree有一些性质，一个度为d的B-Tree，设其索引N个key:

其树高h的上限为logd((N+1)/2)，

检索一个key，时间复杂度为O(logdN)。

3、B+Tree

B+Tree是B-Tree的变种，MySQL普遍使用B+Tree实现索引结构。

与B-Tree相比，每个节点的指标上限为2d而不是2d+1；内存节点不储存data，只储存key；叶子节点不储存指标。

在 B+ Tree 中，一个节点中的 key 从左到右非递减排列，如果某个指标的左右相邻 key 分别是 keyi 和 keyi+1，且不为 null，则该指标指向节点的所有 key 大于等于 keyi 且小于等于 keyi+1。

由于并不是所有节点都具有相同的域，因此B+Tree中叶节点和内节点一般大小不同，这个B-Tree不同，虽然B-Tree中不同节点存放的key和指标可能数量不一致，但是每个节点的域和上限是一致的，所以在视线中B-Tree往往对每个节点申请同等大小的空间。

进行查询操作时，首先在根节点进行二分查询，找到一个 key 所在的指标，然后递回地在指标所指向的节点进行查询。直到查询到叶子节点，然后在叶子节点上进行二分查询，找出 key 所对应的 data。

插入删除操作会破坏平衡树的平衡性，因此在插入删除操作之后，需要对树进行一个分裂、合并、旋转等操作来维护平衡性。

4、代用顺序访问指标的B+Tree

一般在数据库系统或者档案系统中使用的B+Tree结构都在经典的B+Tree的基础上进行了优化，增加顺序访问指标。

在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指标，就形成了带有顺序访问指标的B+Tree，这个优化的目的是为了提高区间访问的效能。

三、为什么使用B-Tree(B+Tree)

一般来说，索引本身也很大，不可能全部储存在内存中，因此索引往往以索引档案的形式储存在磁盘上。这样的话，索引查询过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以一个数据结构作为索引的优劣最重要的指标就是在查询过程中磁盘I/O操作次数对的渐进复杂度。

1、主存存取原理

当系统需要读取主存时，则将地址讯号放到地址总线上传给主存，主存读到地址讯号后，解析讯号并定位到指定储存单元，然后将此储存单元资料放到资料总线上，供其它部件读取。

写主存的过程类似，系统将要写入的单元地址和资料分别放在地址总线和资料总线上，主存读取两个总线的内容，做相应的操作。

2、磁盘存取原理

当需要从磁盘读取资料时，系统会将资料逻辑地址传给磁盘，磁盘的控制电路按照定址逻辑将逻辑地址翻译成实体地址，即确定要读的资料在哪个磁道，哪个扇区。为了读取这个扇区的资料，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

3、区域性性原理和磁盘预读

区域性性原理：

当一个数据被用到时，其附近的资料也通常会马上被使用；程式执行期间所需要的资料通常比较集中；由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有区域性性的程式来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理储存器的逻辑块，硬件及操作系统往往将主存和磁盘储存区分割为连续的大小相等的块，每个储存块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换资料。当程式要读取的资料不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘讯号，磁盘会找到资料的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程式继续执行。

4、B-/+Tree索引的效能分析

根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙的利用磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，实现B-Tree还是用如下技巧：

（1）每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也储存在一个页里，加之计算机分配都是按页对齐的，就实现了一个节点只需要一次I/O。

（2）B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存)，时间复杂度为O(h) = O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小。

综上所述，用B-Tree作为索引结构效率是非常高的。

而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用区域性性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

上文还说过，B+Tree更适合外存索引，原因和内节点出度d有关。从上面分析可以看到，d越大索引的效能越好，而出度的上限取决于节点内key和data的大小：

d_{max}=floor(pagesize / (keysize + datasize + pointsize))

floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的效能。

欢迎工作一到五年的Java工程师朋友们加入Java架构开发：828697593

本群提供免费的学习指导架构资料以及免费的解答，同时大家可以多多关注一下小编纯干货大家一起学习进步