『MySQL』揭开索引神秘面纱

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

上一篇文章简单的介绍了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)。sql

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)。

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

第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点表示说每一个结点的关键字按小到大的顺序依次排列，同时各个结点之间也知足上面提到的二叉搜索树的特色，左孩子的值<父亲节点的值<右孩子的值。ui

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

第5点说的每一个结点关键字的数量的限制，不可能每一个结点能够无限存储关键字。t是最小度数，须要理解这些，能够谷歌一下度数和阶数的定义，上图是4阶的B-Tree。上图中t=2，则每一个内部结点能够容许有二、三、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. 算法导论（第三版）
复制代码

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