『MySQL』揭开索引神秘面纱

MySQL知识梳理图，一图看完整篇文章:

上一篇文章简单的介绍了MySQL的执行流程，这一篇想详细介绍一下索引，一直想全面搞懂索引，尝试写一篇关于它的博文。

1.索引是什么？

索引是什么了，查阅了官方文档。官方文档写了索引的作用和没有索引会带来全表扫描，非常费时间。 Indexes are used to find rows with specific column values quickly. Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows. 简单的说索引是提高查询速度。这个很好理解，就像是以前的英文词典，找单词如果没有前面目录的话，效率很低，得全文找一遍。

2.索引实现原理

要搞清楚索引的实现原理，先看看索引的底层实现，MySQL索引大部分采用B-Tree实现，B-Tree又有B-树和B+树。还有一些使用Hash索引。本文主要介绍B-Tree(Balance Tree)。

2.1 二叉搜索树

再说B-Tree之前，先简单了解一下二叉搜索树（Binary Search Trees）。

理解二叉搜索树，对于后面理解B-和B+树很有帮助，因为这2种有些特性跟二叉搜索树很像。二叉搜索树的特点是左孩子的值小于父亲节点的值，父亲节点的值小于右孩子的值，即按二叉树的中序遍历，刚好是一个按小到大排序的。二叉搜索树的查找就可以使用二分查找，如果要查找10，因为10比27小，所以往左孩子找，10<14，还在左孩子找。最坏的情况下，查找的次数等于树的高度。

2.2 B-树

通常意义上说B-Tree，一般是指B-树，也可以叫平衡多路搜索树，平衡的意思可以区了解一下平衡二叉树(它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。)，多路的意思就是非叶子节点的孩子至少有2个。 B-Tree的特征也是非常烧脑，查看了算法导论书籍，也是琢磨了很久。下图为算法导论书中一张图，浅阴影部分为查找字母R时检查过的结点。

下面算法导论书中对B-树的特征：

1. 每个结点x有如下属性：
   1. x.n。它表示储存在 x中的关键字的个数；
   2. x.key1,x.key2,...,x.keyn。它们表示x的n个关键字，以非降序存放，即x.key1≤x.key2≤...≤x.keyn；
   3. x.leaf。它是一个布尔值，如果x是叶结点，它为TRUE；否则为FALSE；
2. x.c1,x.c2,...,x.cn+1。它们是指向自己孩子的指针。如果该结点是叶节点，则没有这些属性。
3. 关键字x.keyi对存储在各子树中的关键字范围进行分割，即满足：k1≤x.key1≤k2≤x.key2≤...≤x.keyn≤kn+1。其中，ki(i=1,2,....,n+1)表示任意一个储存在以x.ci为根的子树中的关键字。
4. 每个叶结点具有相同的深度，即叶的高度h。
5. 每个结点所包含的关键的个数有上下界。用一个被称为最小度数的固定整数t(t≥2)来表示这些界：
   1. 下界：除了根结点以外的每个结点必须至少有t−1个关键字。因此，除了根结点外的每个内部结点至少有t个孩子。
   2. 上界：每个结点至多包含2t−1个关键字。因此，一个内部结点至多可能有2t个孩子。当一个结点恰好有2t−1个关键字时，称该结点为满的(full)。

是不是还是一头雾水，接下来根据上图一一解释一下这几个特征。

第1点是说每一个节点包括的信息：n表示结点中存储关键字的个数，比如上图上M的左孩子就存了2个关键字，D和H；x.key，说的是具体的关键字的信息，比如D，D实际是有2个部分组成，可以理解为一个map，{key: data}，x.key广义上就是表示这个map，包括了具体的key和存储的数据data，通常说是一条记录；x.leaf是说整个结点是否是叶子结点。

第2点表示如果不是叶子结点，每个结点还有一个属性，就是指向它n个孩子的指针，比如上图中的DH结点，有3个孩子，则有3个指针指向自己的孩子。

第3点表示说每个结点的关键字按小到大的顺序依次排列，同时各个结点之间也满足上面提到的二叉搜索树的特点，左孩子的值<父亲节点的值<右孩子的值。

第4点是说每个叶子结点高度一样，看图就可以明白，这也是平衡二字的由来。

第5点说的每个结点关键字的数量的限制，不可能每个结点可以无限存储关键字。t是最小度数，需要理解这些，可以谷歌一下度数和阶数的定义，上图是4阶的B-Tree。上图中t=2，则每个内部结点可以允许有2、3、4个孩子。孩子数范围[t, 2t]，每个结点的关键字范围[t-1, 2t-1]。这个要区分。

下面更加形象的给出4阶的B-Tree。

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

2.3 B+树

终于写完了B-树，B+树其实是B-树变种。 与B-树最大的区别是内部结点不存储data，只存储key。如下图：

一般数据库系统中使用的B+树再上图经典的基础上再进行了优化，变成了带顺序访问指针的B+树， 如下图。这样就提高区间访问的性能，例如如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

3. 为什么是B-Tree(B+)来实现数据库索引

3.1 磁盘存取原理

数据导论书中开头就是说： B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。上面提到了辅助存储设备，那我们就来看看其中原理，到底由来是什么？ 计算机系统有主存和基于磁盘的辅存，主存通常就是我们说的RAM，也就是内存，这里不展开说它。索引文件本身很大，一般不会存在内存里，因此索引往往是以文件的形式存储在磁盘里，所以索引检索需要磁盘I/O操作。下图为一个典型的磁盘驱动器。

磁盘读取数据靠的是磁盘的机械运动。每次磁盘读取的时间有三部分：寻道时间、旋转延迟、传输时间。寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms；传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略。那么访问一次磁盘读取数据的时间，即一次磁盘I/O操作的时间约9ms左右，这相对于主存存储时间50ns高出5个数量级。看着还不错的，但是一台500 -MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。

为了缩短磁盘读取的时间，计算机做了一些优化：磁盘预读。磁盘预读是基于局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。所以磁盘I/O操作时不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。

说了那么多，总结一下：

• 文件很大，不可能全部存储在内存中，故要存储到磁盘上。
• 索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数，因为每次磁盘I/O消耗时间都是非常多的。
• 局部性原理与磁盘预读，预读的长度一般为页（page）的整倍数。

3.2 B-/B+的查找性能

数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。B-树也利用这一点，每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一次磁盘I/O就读取了一页的数据。下面是B-树的示例图：

根据B-Tree的定义，可知检索一次最多需要访问h个节点（h个树的高度）。B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。所以B-Tree作为索引效率是非常高，相比平衡二叉树、红黑树要高很多，因为这些树的h一般都比较深。

下面附一张B+树的直观图:

B+树比B-树更加适合作为磁盘的索引数据结构，原因是B+树的内部结点不存储data，内部结点的出度d越大，那么渐进复杂度越小。出度d的上限取决于节点内key和data的大小： dmax=floor(pagesize/(keysize+datasize+pointsize))

一般3层B+树可以存储上百万的数据，也就是读取上百万的数据，只需要3次磁盘I/O，可见这效率，大大提升了。如果没有索引，那每次查询一次数据项，都需要一次I/O，几百万次，可怕。

4. 不同引擎的索引实现原理

4.1 MyISAM索引实现

MyISAM的索引采用B+树实现，MyISAM的索引和数据时分开的，叶子节点data存取的是数据的地址。如下主键索引的示例图：

由图可以看出，要根据索引找到数据，先根据索引找到叶子节点，再根据叶子节点找到数据的地址，然后再根据数据地址取出数据。

MyIASM的辅助索引的实现与主键索引没有区别，如下图：

单独出来说，是为了待会跟InnoDB作区分。

4.2 InnoDB索引实现

InnoDB，在实际项目接触是非常多的，索引的实现也是使用B+树，但是实现原理跟MyISAM不同。 第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。如下图：

这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

第二个区别就是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。如下图所示：

4.3 意义

了解不同的引擎的实现原理，对于我们日常做数据库的设计是非常有帮助的。

1. InnoDB辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录，从而能够明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
2. 不建议用非单调的字段作为InnoDB的主键，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时，数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，所以一般使用自增字段作为主键。

这一篇先到这里吧，下一篇总结索引的优化策略。

参考:

 1. http://blog.codinglabs.org/articles/theory-of-mysql-index.html
 2. 算法导论（第三版）

更多精彩文章，请关注公众号：「 天澄技术杂谈 」