MySQL数据库索引的研究

摘要：数据库索引是用于提高数据检索速度的关键数据结构，该文结合常用的数据库索引结构B树，分析索引的原理，并结合外存储的原理，分析大多数数据库使用B+树作为索引结构的原因，并结合MySQL数据库中InnoDB存储引擎中的索引实现，分析其优缺点。

关键词：B树结构；外存储原理；MySQL索引

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）34-8079-02

本文的内容结构如下所示：

第一部分主要从数据结构及算法理论层面讨论B-Tree。

第二部分结合外存储器的存储原理，讨论使用BTree作为索引的原因。

第三部分讨论MySQL数据库中InnoDB数据存储引擎中的索引——改进的B+Tree的结构，及其优点。

1 索引的数据结构及算法基础

数据库查询是数据库的最主要功能之一，提高数据查询速度是数据库索引的主要目标，通常，研究者通过优化检索算法来提高查询速度。查找算法有几类，一种是顺序查找，算法的复杂度为O（n），另外有二分查找、二叉树查找等。一般来说，一种查找算法对应一种数据结构，例如顺序查找对应连续的数据，二分查找对应排好序的数据，二叉树搜索对应二叉查找树。但是，这类数据结构还完全不能满足各种查找需求。比如，二分查找的条件要求将数据排序，但是数据库中不可能同时将两列都按顺序存储。所以，数据库系统必须维护满足特定查找算法的数据结构——索引，以实现更高级的查找算法。

当前，大部分数据库系统都采用BTree作为索引结构，其原因在于BTree的数据结构和主流外存储器的存储原理。下面先介绍B-树的基本结构。

B-树的基本属性：

1） 定义任意非叶子结点最多只有M个儿子；且M>2；

2） 根结点的儿子数为[2， M]；

3） 除根结点以外的非叶子结点的儿子数为[M/2， M]；

4） 每个结点存放至少M/2-1（取上整）和至多M-1个关键词；（至少2个关键词）；

5） 非叶子结点的关键词个数=指向儿子的指针个数-1；

6） 非叶子结点的关键词：K[1]， K[2]， …， K[M-1]；且K[i] < K[i+1]；

7） 非叶子结点的指针：P[1]， P[2]， …， P[M]；其中P[1]指向关键词小于K[1]的子树，P[M]指向关键词大于K[M-1]的子树，其它P[i]指向关键词属于（K[i-1]， K[i]）的子树；

8） 所有叶子结点位于同一层；

如图1所示，是B-树的基本结构。关于如何在一棵B-树中按照key的值去检索数据，描述如下：

1） 以根节点作为入口，对key集合作二分查找，如果找到目标key，则可以直接返回data数据。否则进入第二步。

2） 找到相应区间，根据区间的指针指向的point，得到对应的节点，执行1中过程。如此递归，直到找到目标节点，或者最终返回null point。

加速一个B-树的度为d，有N个key，现在为其建立索引，那么这棵B-树的高h最大为logd（（N+1）/2），查找目标key，查找过程中需要遍历节点个数的复杂度为O（logdN），与二叉查找和顺序查找相比，B-树是一个效率很高的索引数据结构。

图1 B-Tree的结构

通常，数据库中数据都很多，导致建立的索引也很大，很难全部存储在内存中，因此，通常将索引保存在磁盘中。这样，在索引中查找时，就需要进行磁盘I/O，而与内存存取速度比较，磁盘I/O的速度要慢几个数量级。所以，通常我们将在查找过程中磁盘的操作次数作为我们评价一种数据结构是否适合作为索引的关键信息。那么，建立好的索引就是要尽量减少查找过程中磁盘I/O的次数。

了解磁盘的存取原理，对应理解使用B-树作为索引结构必不可少。

2 磁盘的存储原理

磁盘的内部结构如图2所示。

操作系统在读取磁盘数据时，将数据逻辑地址传给磁盘，磁盘会将操作系统传来的逻辑地址转换为物理地址以确定需要读取的数据的具体位置，即数据所在的磁道和扇区，那么，为了读取目标数据，磁盘需要将磁头移动到对应的那个扇区上，磁盘是通过横向移动磁头做到这点的。移动磁头的过程叫做寻道，而这个过程所耗费时间叫做寻道时间。然后磁盘需要通过旋转将目标扇区旋转到磁头下，这个过程所花费的时间叫做旋转时间。

图2 磁盘的内部构造图

磁盘的存储结构和寻址方式，导致了磁盘的存取速度比通常的主存储器慢几个数量级。磁盘在寻址过程中的需要的机械运动的时间，是导致磁盘在查找存储数据速度缓慢的主要原因。所以，如果想要提高数据库存储速度，减少磁盘IO次数是主要途径。其中一个可行的操作方案就是：每次寻址之后，预读一定的磁盘空间的内容。这样在读取相同大小空间的数据内容时，减少了机械寻址的时间，可以大大减少磁盘的存储速度。实际上，磁盘也正是这样做的。通常，磁盘在读取数据的时候，都会预取出一定长度的数据块，称为页。通常，页是4k大小。由前面对B树的介绍我们可以知道，进行一次检索需要访问h（B树的高度）个节点。那么，h的大小即是衡量一个索引好坏的标准。假设一个数据库表中需要保存N条信息，B树中每个节点保存d个key，那么由前文可知：h=logdN；d越大，h就越小。利用磁盘的预读机制，我们可以将一棵B的节点大小设定为一个页的大小，那么，在磁盘在预读的时候，取出的一个页都是有用key信息，这样大大提高了数据的存储效率，加快了检索的过程。

由以上内容可以判断，B-树非常适合作为索引结构，其查找效率是非常高的。

3 MySQL中的索引结构分析

B-树有多重改进版本，MySQL使用的B+树就是其中一种。

B+树的改进有以下两点：

1） 节点的指针数量可key数量一一对应。

2） 内节点不保存data，只保存key和指针；叶子节点只保存key和data，不存储指针。

MySQL中索引的结构如图3所示：

B+树的性能分析：

从B+树的性质我们可以知道，B+树的内节点不保存data值，只保存key和指针。那么，假设一个页的大小空间用于保存一个节点，这样在同一个节点中能够保存的key值比B-树结构会更多，即d更大。由h=logdN可知，h更小。所以B+树比B-树更适合作为索引结构。

由图3中可以看到，MySQL索引的结构，是一种改进的B+树，其每个叶子节点中都包含一个指向相邻叶子节点的指针。添加这个指针的目的是为了提高区间访问的性能。如图3所示，查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

4 总结

使用数据库索引是提高数据库查询速度的关键因素，合理利用索引，对于提高数据库性能有很大帮助。数据库的性能优化需要对数据库的索引内部结构及其原理有深入的了解。该文阐述了BTree索引的基本原理，并说明了MySQL数据库的索引实现，为索引调优和数据库性能优化提供了有效的帮助。

参考文献：

[1] D Comer.Ubiquitous B-tree； ACM Computing Surveys （CSUR）， 1979.

[2] Codd E F.A relational model of data for large shared data banks L[M].Communications of the ACM， 1970，13（6）：377-387.

[3] Baron Scbwartz.高性能MySQL[M].王小东，译.北京：电子工业出版社，2010.

[4] 姜承尧.MySQL技术内幕-InnoDB存储引擎[M].北京：机械工业出版社，2011.

由以上内容可以判断，B-树非常适合作为索引结构，其查找效率是非常高的。

3 MySQL中的索引结构分析

B-树有多重改进版本，MySQL使用的B+树就是其中一种。

B+树的改进有以下两点：

1） 节点的指针数量可key数量一一对应。

2） 内节点不保存data，只保存key和指针；叶子节点只保存key和data，不存储指针。

MySQL中索引的结构如图3所示：

B+树的性能分析：

从B+树的性质我们可以知道，B+树的内节点不保存data值，只保存key和指针。那么，假设一个页的大小空间用于保存一个节点，这样在同一个节点中能够保存的key值比B-树结构会更多，即d更大。由h=logdN可知，h更小。所以B+树比B-树更适合作为索引结构。

由图3中可以看到，MySQL索引的结构，是一种改进的B+树，其每个叶子节点中都包含一个指向相邻叶子节点的指针。添加这个指针的目的是为了提高区间访问的性能。如图3所示，查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

4 总结

使用数据库索引是提高数据库查询速度的关键因素，合理利用索引，对于提高数据库性能有很大帮助。数据库的性能优化需要对数据库的索引内部结构及其原理有深入的了解。该文阐述了BTree索引的基本原理，并说明了MySQL数据库的索引实现，为索引调优和数据库性能优化提供了有效的帮助。

参考文献：

[1] D Comer.Ubiquitous B-tree； ACM Computing Surveys （CSUR）， 1979.

[2] Codd E F.A relational model of data for large shared data banks L[M].Communications of the ACM， 1970，13（6）：377-387.

[3] Baron Scbwartz.高性能MySQL[M].王小东，译.北京：电子工业出版社，2010.

[4] 姜承尧.MySQL技术内幕-InnoDB存储引擎[M].北京：机械工业出版社，2011.

由以上内容可以判断，B-树非常适合作为索引结构，其查找效率是非常高的。

3 MySQL中的索引结构分析

B-树有多重改进版本，MySQL使用的B+树就是其中一种。

B+树的改进有以下两点：

1） 节点的指针数量可key数量一一对应。

2） 内节点不保存data，只保存key和指针；叶子节点只保存key和data，不存储指针。

MySQL中索引的结构如图3所示：

B+树的性能分析：

从B+树的性质我们可以知道，B+树的内节点不保存data值，只保存key和指针。那么，假设一个页的大小空间用于保存一个节点，这样在同一个节点中能够保存的key值比B-树结构会更多，即d更大。由h=logdN可知，h更小。所以B+树比B-树更适合作为索引结构。

由图3中可以看到，MySQL索引的结构，是一种改进的B+树，其每个叶子节点中都包含一个指向相邻叶子节点的指针。添加这个指针的目的是为了提高区间访问的性能。如图3所示，查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

4 总结

使用数据库索引是提高数据库查询速度的关键因素，合理利用索引，对于提高数据库性能有很大帮助。数据库的性能优化需要对数据库的索引内部结构及其原理有深入的了解。该文阐述了BTree索引的基本原理，并说明了MySQL数据库的索引实现，为索引调优和数据库性能优化提供了有效的帮助。

参考文献：

[1] D Comer.Ubiquitous B-tree； ACM Computing Surveys （CSUR）， 1979.

[2] Codd E F.A relational model of data for large shared data banks L[M].Communications of the ACM， 1970，13（6）：377-387.

[3] Baron Scbwartz.高性能MySQL[M].王小东，译.北京：电子工业出版社，2010.

[4] 姜承尧.MySQL技术内幕-InnoDB存储引擎[M].北京：机械工业出版社，2011.