MySQL中为什么要使用索引

边肖想和大家分享一下为什么在MySQL中使用这个索引。相信大部分人还是不太了解。因此，我想分享这篇文章供你参考。希望你看完这篇文章后收获多多。让我们一起来看看。

索引是什么？

MySQL正式将索引定义为帮助MySQL高效获取数据的数据结构。

除了数据之外，数据库系统还维护满足特定查找算法的数据结构,并且这些数据结构以某种方式引用(指向)数据，从而可以在这些数据结构上实现高级搜索算法。这个数据结构就是索引。

索引似乎可以提高查询效率，就像图书目录一样。其实说白了，索引要解决的就是查询问题。

查询是数据库提供的一个重要功能。我们都希望尽快得到目标数据，因此需要优化数据库的查询算法，选择合适的查询模型来实现索引。

此外，为表设置索引也要付出代价：一是增加了数据库的存储空间，二是在插入和修改数据时要花费较多的时间，因为索引也要随之变动。.

常见查询模型

指数的实现模式有很多。这里，我们先来了解一下常用的查询模型。

00-1010顺序数组是一种特殊的数组，其中元素按一定的顺序排列。

序列在查询上有一定的优势，因为它是有序数据，如果使用二分搜索法，时间复杂度为O(log(N))。

顺序数组的优点就是查询效率非常高，但是要更新数据的话，就非常麻烦了。删除和插入元素都要涉及到大量元素位置的移动，成本很高。

因此，对于顺序数组更适合查询的字段，适合存储一些变化不大的静态存储引擎。

顺序数组

哈希表是一个在键-值（key-value）,存储数据的结构，我们可以通过输入要搜索的值，即key，找到它对应的值，即value。

索引使用某种哈希算法。对于每一行，存储引擎计算索引字段的哈希代码，将哈希代码保存在索引中，并将指向每一行的指针保存在哈希表中。

这样，只需要一个哈希算法就可以立即定位到对应的位置，速度非常快。

由于Hash索引结构的特殊性，其检索效率非常高，应该是O(1)时间复杂度。

哈希索引虽然效率高，但由于其特殊性，哈希索引本身也带来了很多限制和弊端，主要包括以下几点：

1.Hash INdex只能满足=、in和=查询。如果它是范围查询检索,那么散列索引是无用的。

由于哈希算法后原始的有序键值可能会变得不连续，因此无法使用索引来完成范围查询和检索。

2.哈希索引无法利用索引完成排序,因为它是由Hash在存储时计算的，而计算出的Hash值不一定等于原始数据，所以无法排序；

3.在联合索引中，哈希索引是不能利用部分索引键查询.

计算哈希值时，哈希索引将索引键组合在一起，然后一起计算哈希值，而不是单独计算哈希值。

因此，对于联合索引中的多个列，哈希要么完全使用，要么根本不使用。当通过一个或多个以前的索引键进行查询时，不能使用哈希索引。

4.哈希索引总是不能避免表扫描.

我们知道，Hash索引是在对索引键进行Hash操作后，将Hash操作结果的Hash值和对应的行指针信息存储在Hash表中。由于不同的索引键可能具有相同的哈希值，因此即使获取了满足某个哈希值的数据记录数，也无法从哈希索引直接完成查询，或者需要访问表中的数据。

际数据进行相应的比较，并得到相应的结果。

5、在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。

综上，哈希表这种结构适用于只有等值查询的场景，比如 Memcached、redis 及其他一些 NoSQL 引擎。

二叉搜索树索引

二叉搜索树的每个节点都只存储一个键值，并且左子树（如果有）所有节点的值都要小于根节点的值，右子树（如果有）所有节点的值都要大于根节点的值。

当二叉搜索树的所有非叶子节点的左右子树的节点数目均保持差不多时（平衡），这时树的搜索性能逼近二分查找；并且它比连续内存空间的二分查找更有优势的是，改变树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销。

特殊情况下，根节点的左右子树的高度相差不超过 1 时，这样的二叉树被称为平衡二叉树；与之相对的是，二叉搜索树有可能退化成线性树。

下图展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。

为了加快 Col2 的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在 O(log2n) 的复杂度内获取到相应数据。

B树

看得出来，二叉树在查询和修改上做到了一个平衡，都有着不错的效率，但是现实是很少有数据库引擎使用二叉树来实现索引，为什么呢？

数据库存储大多不适用二叉树，数据量较大时，树高会过高。

你可以想象一下一棵 100 万节点的平衡二叉树，树高 20，每个叶子结点就是一个块，每个块包含两个数据，块之间通过链式方式链接。

树高 20 的话，就要遍历 20 个块才能得到目标数据，索引存储在磁盘时，这将是非常耗时的。

因此，为了减少磁盘的读取，查询时就要尽量少的遍历数据块，因此一般使用 N 叉树。

这里就有了 B树（Balanced Tree）。

究竟什么是 B 树？

我们先看一个例子：

从上图你能轻易的看到，一个内结点 x 若含有 n[x] 个关键字，那么 x 将含有 n[x]+1 个子女。如含有 2 个关键字 D H 的内结点有 3 个子女，而含有 3 个关键字 Q T X 的内结点有 4 个子女。

B 树的特性

普及一些概念：

节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
叶节点或终端节点：度为零的节点；
非终端节点或分支节点：度不为零的节点；

首先定义两个变量：d 为大于 1 的一个正整数，称为 B 树的度。h 为一个正整数，称为 B 树的高度。

B 树是满足下列条件的数据结构：

1、每个非叶子节点由 n-1 个 key 和 n 个指针组成，其中 d<=n<=2d。

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

3、除根结点和叶子结点外，其它每个结点至少有 [ceil(m / 2)] 个孩子（其中 ceil(x) 是一个取上限的函数）；

4、所有叶节点具有相同的深度，等于树高 h，且叶子结点不包含任何关键字信息。

5、key 和指针互相间隔，节点两端是指针。

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

7、每个指针要么为 null，要么指向另外一个节点。

8、每个非终端结点中包含有 n 个关键字信息： (n，P0，K1，P1，K2，P2，……，Kn，Pn)。

其中：
a) Ki (i=1…n) 为关键字，且关键字按顺序升序排序 K(i-1)< Ki。 
b) Pi 为指向子树根的接点，且指针 P(i-1) 指向子树种所有结点的关键字均小于 Ki，但都大于 K(i-1)。 
c) 关键字的个数 n 必须满足： [ceil(m / 2)-1]<= n <= m-1。

B 树查找过程

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

如上图所示，我们来模拟下查找文件 29 的过程：

1、根据根结点指针找到文件目录的根磁盘块 1，将其中的信息导入内存。【磁盘 IO 操作 1 次】

2、此时内存中有两个文件名 17、35 和三个存储其他磁盘页面地址的数据。根据算法我们发现：17<29<35，因此我们找到指针 p2；

3、根据 p2 指针，我们定位到磁盘块 3，并将其中的信息导入内存。【磁盘 IO 操作 20次】

4、此时内存中有两个文件名 26，30 和三个存储其他磁盘页面地址的数据。根据算法我们发现：26<29<30，因此我们找到指针 p2；

5、根据 p2 指针，我们定位到磁盘块 8，并将其中的信息导入内存。【磁盘 IO 操作 3 次】；

6、此时内存中有两个文件名 28，29。根据算法我们查找到文件名 29，并定位了该文件内存的磁盘地址。

分析上面的过程，发现需要 3 次磁盘 IO 操作和 3 次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。

B+ 树

B+ 树：是应文件系统所需而产生的一种 B 树的变形树。

一棵 m 阶的 B+ 树和 m 阶的 B 树的异同点在于：

1、每个节点的指针上限为 2d 而不是2d+1。

2、所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。（B 树的叶子节点并没有包括全部需要查找的信息）

3、所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字，不存储 data。（B 树的非终节点也包含需要查找的有效信息）

为什么说 B+ 树比 B 树更适合做数据库索引？

1）B+ 树的磁盘读写代价更低

B+ 树的内部结点并没有存储关键字具体信息。因此其内部结点相对 B 树更小。

如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说 IO 读写次数也就降低了。

2) B+ 树的查询效率更加稳定

由于非终端结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，进而每一个数据的查询效率相当。

几种树的对比

以上，为了介绍索引内容，我们花费了大量的篇幅介绍了几种数据结构模型，特别是树的相关概念。

另外，涉及到树的添加和删除元素，操作更加复杂，本文篇幅有限（其实是小编也搞不太明白），这里就不再展开。

有兴趣的，强烈建议钻研下参考链接里的内容。

好了，下面我们来看 MySQL 中的 InnoDB 引擎的索引是如何实现的。

MySQL 的索引模型

说了这么多，终于到索引出场了。

索引就是这种神奇伟大的存在。索引相当于数据库的表数据之外新建的数据结构，该数据结构的数据段中存储着字段的值以及指向实际数据记录的指针。

数据库表的索引从数据存储方式上可以分为聚簇索引和非聚簇索引（又叫二级索引）两种。

1、聚簇索引

表数据按照索引的顺序来存储的，也就是说索引项的顺序与表中记录的物理顺序一致。

对于聚簇索引，叶子结点即存储了真实的数据行，不再有另外单独的数据页。 在一张表上最多只能创建一个聚集索引，因为真实数据的物理顺序只能有一种。

聚簇集是指实际的数据行和相关的键值都保存在一起。

注意：数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的。

如果主键不是自增 id，那么可以想象，它会干些什么，不断地调整数据的物理地址、分页。如果是自增的，那就简单了，它只需要一页一页地写，索引结构相对紧凑，磁盘碎片少，效率也高。

聚簇索引的二级索引：叶子节点不会保存引用的行的物理位置,而是保存了行的主键值

2、非聚集索引

表数据存储顺序与索引顺序无关。对于非聚集索引，叶结点包含索引字段值及指向数据页数据行的逻辑指针，其行数量与数据表行数据量一致。

聚簇索引是对磁盘上实际数据重新组织以按指定的一个或多个列的值排序的算法。特点是存储数据的顺序和索引顺序一致。一般情况下主键会默认创建聚簇索引，且一张表只允许存在一个聚簇索引。

这两个名字虽然都叫做索引，但这并不是一种单独的索引类型，而是一种数据存储方式。

下面，我们可以看一下 MYSQL 中 MyISAM 和 InnoDB 两种引擎的索引结构。

MyISAM索引实现

MyISAM 引擎使用 B+ 树作为索引结构，叶节点的 data 域存放的是数据记录的地址，就是非聚集索引。

下图是 MyISAM 索引的原理图：

InnoDB索引实现

虽然 InnoDB 也使用 B+ 树作为索引结构，但具体实现方式却与 MyISAM 截然不同。

第一个重大区别是 InnoDB 的数据文件本身就是索引文件。

在 InnoDB 中，表数据文件本身就是按 B+ 树组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。

另外，第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。

对于聚簇索引存储来说，行数据和主键 B+ 树存储在一起，辅助索引只存储辅助键和主键，主键和非主键 B+ 树几乎是两种类型的树。

对于非聚簇索引存储来说，主键 B+ 树在叶子节点存储指向真正数据行的指针，而非主键。

为了更形象说明这两种索引的区别，我们假想一个表如下图存储了 4 行数据。其中 Id 作为主索引，Name 作为辅助索引。图示清晰的显示了聚簇索引和非聚簇索引的差异。

若使用辅助索引进行查询，对 Name 列进行条件搜索，则需要两个步骤：

1、第一步在辅助索引 B+ 树中检索 Name，到达其叶子节点获取对应的主键。
2、第二步根据主键在主索引 B+ 树种再执行一次 B+ 树检索操作，最终到达叶子节点即可获取整行数据。这个过程称为回表。

聚簇索引的优势在哪？

1、由于行数据和叶子节点存储在一起，这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，如果按照主键 Id 来组织数据，获得数据更快。

2、辅助索引使用主键作为指针而不是使用地址值作为指针的好处是，减少了当出现行移动或者数据页分裂时辅助索引的维护工作。

使用主键值当作指针会让辅助索引占用更多的空间，换来的好处是 InnoDB 在移动行时无须更新辅助索引中的这个指针。

也就是说行的位置会随着数据库里数据的修改而发生变化，使用聚簇索引就可以保证不管这个主键 B+ 树的节点如何变化，辅助索引树都不受影响。

以上是“MySQL中为什么要使用索引”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注行业资讯频道！