浅入浅出 MySQL 索引

索引是什么？为什么要有mysql 索引，解决了什么问题，其底层的原理是什么？为什么使用B+树做为解决方案？用其他的像哈希索引或者B树不行吗？

1.简单了解索引

首先，索引（Index）是什么？如果我直接告诉你索引是数据库管理系统中的一个有序的数据结构，你可能会有点懵逼。为了避免这种情况，我打算举几个例子来帮助你更容易的认识索引。

我们查询字典的时候可以根据字的部首、笔画来查找到对应的字，这样可以快速的找到对应的字所在页，在字典开头那玩意就叫索引 还有一本书的目录，可以帮我们快速的跳到不同的章节，此时这里的目录也是索引 甚至，景区的地图，会告诉你你现在在哪里，其他景点在哪儿，这个地图从某些方面来说也是索引

2.为什么需要索引

索引的存在的目的就是：

• 字典中的索引帮助我们快速的找到对应的字
• 书的目录帮助我们快速的跳到我们需要看的章节
• 景区的地图帮助我们快速的找到想要去的景区的路

在数据库中，索引可以帮助我们快速的查询到对应的数据行，从而顺利的取出所有列的数据。这个过程必须要快，对于现在的 Web 应用来说，DB 如果响应慢，将会直接影响到整个请求的响应时间，而这对用户体验来说是灾难性的。
对于点个按钮，等个好几秒才有返回，那么之后用户大概率是不会再使用你开发的应用了。

3.MySQL中的索引

首先，MySQL 和索引其实没有直接的关系。索引其实是 MySQL 中使用的存储引擎 InnoDB 中的概念。在 InnoDB 中，索引分为：

• 聚簇索引
• 非聚簇索引

对于聚簇索引，是 InnoDB 根据主键（Primary Key）构建的索引。你可以暂时理解为 key 为主键，value 则是整行数据。并且一张表只能有一个聚簇索引。当然，你可以不定义主键。但是正常情况下我们都会创建一个单调递增的主键，或者是通过统一的 ID 生成算法生成。如果没有定义任何主键，InnoDB 会有自己的兜底策略。InnoDB 会选择我们定义的第一个所有值的都不为空的唯一索引作为聚簇索引。

不过实际的生产环境中，的确会有这样的 Corner Case。InnoDB 还有一个究极兜底，如果连仅剩的唯一索引也不符合要求，InnoDB 会自己创建一个隐藏的6个字节的主键 RowID，然后根据这个隐藏的主键来生成聚簇索引。
而对于非聚簇索引，是根据指定的列创建的索引，也叫二级索引（Secondary Index），一张表最多可以创建64个二级索引。key 为创建二级索引的列的值，value 为主键。换句话说，如果通过非聚簇索引查询，最终只能得到索引列本身的值 + 主键的值，如果想要获取到完整的列数据，还需要根据得到的主键去聚簇索引中再查询一次，这个过程叫回表。

这里说明一下，现在有很多的博客说，MySQL 使用 InnoDB 时，一张表最多只能创建 16 个索引，首先这是错的，明显是从其他的地方直接抄过来的，自己没有去做任何的验证。 在 MySQL 的官方文章中，明确的说明了，一张表最多可以创建 64 个非聚簇索引，而且创建非聚簇索引时，列的数量不能超过16个。 注意，是创建非聚簇索引的列不能超过16个！

这也顺便提一下题外话，所谓的技术严谨，什么叫严谨？对你通过其他渠道获取到的知识，它最多叫作者的观点，我们持一种怀疑态度，并想办法自己去求证。求证后，它才会变成事实。
而不是对某些名词死记硬背，现在的新玩意层出不穷，但当你溯其根源，你会发现就那么回事。

索引底层原理

前面提到了 InnoDB 中索引的类型，简单的了解了其分类和区别，那 InnoDB 中的索引是如何做到加速查询的呢？其底层的原理是啥呢？InnoDB 中的索引的底层结构为 B+ 树，是B树的一个变种。

先给大家看看B+树到底长个什么鸟样，下图是一颗存储了数字「1-7」的B+树。

可以看到，B+树中，每个节点可以有多个子节点，而像我们平常熟悉的二叉树中，每个节点最多只能有2个。并且，B+树中，节点的存储数据是有序的，而有序的数据结构就可以让我们进行快速的精确匹配和范围查询。而且B+树中的叶子结点之间有指向下一个节点的指针，而B树中的叶子节点是没有的。

在 MySQL InnoDB 的实际实现中，页节点之间其实是个双链表，存储了分别指向上一个、下一个节点的指针

下图是包含了整数「1-7」的B树，这个图应该会帮助你加深对两者区别的理解。

并且，在B+树中，除了叶子节点存储了真实的数据之外，其余的节点都只存储了指向下一节点的指针。换句话说，数据全部都在叶子节点上。而在B树中，所有的节点都可以存储数据，这是一个最主要的区别。
知道了B树和B+树的基础结构长啥样之后，我们需要再深入了解 InnoDB 是如何利用B+树来存储数据的。首先，MySQL 并不会把数据存储在内存中，内存只是作为运行时的一种优化，关于 InnoDB 内存架构相关的东西，之前已经写了一篇文章，感兴趣的可以先去看看。
InnoDB 会将数据存储在磁盘上，而当我们查询数据的时候，OS 会将存储在磁盘上的数据一页一页的加载到内存里。这里的页是 OS 管理内存的一种方式，当其加载数据到内存时，会将某个磁盘块上的数据按照页的大小加载。在这里，你可以理解为B树中每个节点就是一个磁盘块。
那既然B树和B+树在查找的时候都需要进行 I/O 操作将需要的节点加载到内存，B+树相对于B树的优势到底在哪儿？

个人认为主要有三点。
一是B+树能够减少 I/O 的次数。为啥呢？凭啥数据结构长的差不多，B+树就能够减少 I/O 的次数？之前说到，单个节点就代表了一个磁盘块，而单个磁盘块的大小是固定的。B+树仅有叶子结点才存储值，相对于所有节点都存完整数据的B树而言，B+树中单个磁盘块能够容纳更多的数据。

单个磁盘块，容量固定的前提下，存储的元素大小越小，则能够存储的元素的数量就会更多。换句话说，一次 I/O 能够把更多的数据加载进内存，而这些多加载的元素很可能是你会用到的，而这就一定程度上能减少 I/O 的次数。
除此之外，单个节点能够存储的元素增多了，还能够起到减少树的高度的作用。
二是查询效率更加稳定。什么叫更稳定呢？那就在数据量相同的情况下，不会因为你查询的数据 ID 不同而造成查询所耗费时间大相径庭，换句话说，这次请求可能花了10ms，下一次同样的请求啪的一下花了20ms，这就让人很不能接受，合着接口的性能还要看你数据库的心情？
那为什么说使用B+树就能够做到查询效率稳定呢？因为B+树非叶子结点不会存储数据，所以如果要获取到最终的数据，必然会查到叶子结点，换句话说，每次查询的 I/O 次数是相同的。而B树由于所有节点均可存储数据，有的数据可能1次 I/O 就查询到了，而有的则需要查询到叶子结点才找到数据，而这就会带来查询效率的不稳定。
三是能够更好的支持范围查询。那B树为啥就不能很好的支持呢？让我们回到B树这张图。

假设我们需要查询 [3, 5] 这个区间内的数据，会经历什么呢？不废话，直接把图给出来。

可以看到，如果到叶子结点仍然没有查询到完整的数据，会重新返回到根结点再次进行遍历。而反观 B+ 树，当找到了叶子结点之后就可以通过叶子结点之间的指针直接进行链表遍历，可以大大的提升范围查询的效率。

知道了这点之后，举一反三就能够知道，为什么 InnoDB 不使用 Hash 在做底层的数据结构了。即使查询时 Hash 的时间复杂度甚至能做到 O(1)

最后聊聊 I/O

全篇提到了很多次 I/O，以及在 MySQL 的索引设计中，需要尽量的减少 I/O 次数，为啥呢？是因为 I/O 很昂贵。当我们执行一次 I/O，到底发生了什么？

本来像详细讲讲磁盘结构的，但是看了一眼篇幅，已经快超了，所以这里就简单的聊聊就好

机械硬盘中，一次 I/O 操作，由三个步骤组成：
首先需要寻道，寻道是指磁盘的磁头移动道磁盘上的磁道上面，这个时间一般在3-15ms内。
然后是旋转，磁盘会将存储对应数据的盘片旋转至磁头下方，这又花掉2ms左右，具体的时延与磁盘的转速有关。
最后是数据传输。
一波操作下来，花费就在10ms左右。不要以为10ms还好…对比于SSD（固态硬盘）和内存的微秒、纳秒来说，简直有着天壤之别。

这也是为啥在 MySQL 中，随机 I/O 对其查询的性能影响很大的原因。