索引是支持快速查询的数据结构，索引优化也是后端工程师必备的知识点。每个公司都有所谓的MySQL“无所不包”。其实这些所谓的优化和规定并不是什么先进的技术，只是要求大家正确建立和使用索引。要想做得好，工人必须先磨快他们的工具。如果他们想正确使用索引，他们需要知道底层的实现原理。本文将探讨什么是索引以及为什么。

MySQL中有很多关于索引的概念。为了避免混淆，在最后一篇文章中，解释了一些为索引分类设计的不同维度的名词，如辅助索引、唯一索引、覆盖索引、B树索引.不懂墙裂的朋友建议先看看图文并茂的MySQL索引(第一部分)——说说索引的分类，本文对索引类型的定义不再赘述。

00-1010 1.1磁盘IO

所谓磁盘IO，简单来说就是把磁盘里的数据读入内存或者从内存写到磁盘上。在系统开发设计过程中，磁盘IO的瓶颈不容忽视，因为这是一个相对耗时的操作。

上图为机械硬盘。虽然速度不如SSD，但由于价格低廉，仍然是主流的存储介质。它的IO操作通常需要三个步骤：查找、旋转和传输。

寻道是指将读写头移动到正确的磁道。寻道时间越短，IO操作越快。目前，磁盘的平均寻道时间一般在3-15毫秒左右。

旋转是指将磁盘旋转到请求数据所在的扇区，这部分所需的时间由硬盘的配置决定。旋转延迟由磁盘速度决定，通常称为7200转/分和5400转/分。

比如7200转意味着它每分钟可以旋转7200转，那么一转所需的时间是60*1000/7200 8.33ms，旋转延迟通常是一转时间的1/2，也就是4.17 ms左右。

传输方面，磁盘传输的速度通常为每秒几十到几百米，假设速度为20M/s，待传输的数据为64kb，那么传输时间为64/1024/20 * 1000=3.125ms，但目前流行的SSD传输速度大幅度提升，SATA II可达300M/s，传输速度往往比前两步低很多，因此传输时间往往可以忽略不计。

机械硬盘的连续读写性能很好，但随机读写性能很差，主要是磁头移动到正确的磁道需要时间。随机读写时，磁头需要不断移动，时间浪费在磁头寻址上，性能不高。

以上过程是对传统机械磁盘IO延迟的粗略介绍。目的是告诉大家，磁盘IO过程是一个耗时的过程，内存操作往往与其速度不是一个数量级的。即使是目前流行的固态硬盘，内存中的数据读取性能也必须在千里之外。

1.2地方性原则

磁盘IO是一项耗时的操作，操作系统在设计时定义了空间局部性原则。局部性原理是指当CPU访问内存时，无论是访问指令还是数据，被访问的内存单元往往聚集在一个连续的小区域内。

在操作系统的文件系统中，数据也是按照页面来划分的，通常是4k或者8k。当计算机访问一个地址数据时，不仅会加载当前数据所在的数据页，还会将与当前数据页相邻的数据页加载到内存中。事实上，在这个过程中只发生了一次磁盘IO。这一理论对索引的数据结构设计很有帮助。

00-1010索引是一种支持快速搜索的数据结构。在应用中，经常需要支持顺序搜索。常见的数据结构有很多，比如数组、链表、二叉树、哈希表、二叉查找树、平衡搜索二叉树、红黑树、跳表等等。仅从数据结构来看，那么为什么选择B树呢？

首先，对于数组、链表等线性表，适合存储数据而不是查找数据。同样，对于普通的二叉树，由于没有具体的规则，数据存储也不适合。

2.1满意的鼠标指标不能满足业务需求。

满意鼠标(Hash)是一种非常快速的搜索方法。一般来说，这种搜索的时间复杂度为O(1)，也就是说，通常只需要一次搜索就可以定位到数据。它广泛应用于各种编程语言和数据库，如Java、Python和Redis。

满意鼠标结构在单个数据的等价查询中性能优异，但只能用于搜索等价查询。对于范围查询，不支持模糊查询(最左边前缀原则)，不能很好地支持业务需求。因此，MySQL并没有明确支持Hash索引，而是根据数据访问的频率和方式，自动为热点数据页面建立一个满意的鼠标索引，称为自适应满意鼠标索引。

并且由于满意鼠标功能的随机性，Hash索引通常是随机内存访问。

2.2 二叉搜索树退化成链表

二叉搜索树，如果左子树不为空，则左子树上所有节点均小于根节点，右子树节点均大于根节点；由其属性不难看出，这种树非常适合数据查找。不过有个致命的缺点是二叉搜索树的树型取决于数据的输入顺序，极端情况下会退化成链表。

2.3 平衡二叉搜索树过于严格

为了解决上述问题，平衡二叉搜索树就诞生了。在保证数据顺序的基础上，又能维持树型，保证每个节点的左右子树高度相差不超过1。

不过由于要维持树的平衡，在插入数据时可能要进行大量的数据移动。平衡搜索二叉树过于严格的平衡要求，导致几乎每次插入和删除节点都会破坏树的平衡性，使得树的性能大打折扣。

2.4 红黑树高度过高，磁盘IO次数频繁

有没有一种数据结构，即能够快速查找数据，又不需要频繁的调整以维持平衡呢？这时红黑树就闪亮登场了。

红黑树和其他二叉搜索树类似， 都是在进行插入和删除操作时通过特定操作保持二叉查找树的性质，从而获得较高的查找性能。与之不同的是，红黑树的平衡性并不像平衡搜索二叉树一样严格的同时，又能保证在， O(log n) 时间复杂度内做查找和删除。

红黑树通过改变节点的颜色，可以有效减少节点的移动次数，由于红黑树的实现比较复杂，本文不再展开，感兴趣的小伙伴可以去深入学习。

看似红黑树是一种完美的数据结构，能够胜任索引的工作。但MySQL并未使用其作为索引的实现，主要原因在于红黑树的深度过大，数据检索时造成磁盘IO频繁，假设一个每个节点存储在一个page中，树的高度为10，则每次检索可能就需要进行10次磁盘IO。

2.5 B-Tree不支持顺序查询

B-Tree是一种自平衡的多叉搜索树，一个节点可以拥有两个以上的子节点。适合读写相对大的数据块的存储系统，例如磁盘。

由于MySQL索引一般都存储在内存中，如果使用B-Tree作为索引的话，索引和数据存储在一块，分布在各个节点中；而内存资源往往比较宝贵，一定内存的情况下可以存储的索引数量相对有限，毕竟每条数据的大小一般远大于索引列的大小，导致内存使用率不高。

数据查询过程中往往会有顺序查询，而B-Tree和红黑树对于顺序查询并不友好。

2.6 为什么选B+Tree

B+Tree是在B-Tree基础上演进而来的。与之不同的是B+Tree的数据页只存储在叶子节点中，并且叶子节点之间通过指针相连，为双向链表结构。

B+Tree的优点可以分为以四个：

三，MySQL中索引实现#

3.1 巧妙利用B+Tree

MySQL中的数据存储通常以Page为单位，俗称数据页，每个Page对应B+Tree的一个节点。页是InnoDB磁盘管理的最小单位，默认每个数据页的大小为16kb，也可以通过参数innodb_page_size将页的大小设置成其他值。

数据库的页大小和操作系统类似，是指存放数据时，每一块连续区域数据的大小。比如一个1M的数据存放在数据库中时， 需要大概64个页来存放（1024=64*16）。如果是在操作系统上安装的数据库，最好将数据库页大小设置为操作系统页大小的倍数，才是最佳设置。

3.2 树的高度-有效减少磁盘IO次数

通常情况下，一张MySQL表中有成千上万条数据，而磁盘IO次数往往与数的高度成正比。默认情况下一个Page的大小为16kb，由于每个Page中数据通过指针相连，且每个指针大小为6字节。

在工作中，我们通常使用长度为8个字节的bigint类型作为主键id的类型。已知，每一条数据都会包含一个6字节的指针（数据页中每条记录都有指向下一条记录的指针，但是没有指向上一条记录的指针）；所以一条索引数据大约占用8+6=14个字节，一个Page中能存储16 * 1024 / 14 ≈ 1170条索引数据。高度为2的B+Tree大约能存储1170*16 = 18720条这样的记录。同理，高度为3的B+Tree的B+Tree大约能存储1170 * 1170 * 16 = 21902400，大约两千万条数据。 （每个节点大约能存储1170条记录，可以理解为此时B+Tree为1170叉树）

例如，要检索id=008的数据，则需要进行三次磁盘IO找到对应的数据页（最多三次，因为Page可能在缓存中），然后在数据页中进行二分查找，定位到对应的记录。

四，总结#

大家耳熟能详的B+Tree索引是一种非常优秀的数据结构，也是面试热点问题。本文从数据结构和磁盘IO两个方面分析了为什么使用B+Tree，以及MySQL的InnoDB存储引擎的索引实现。在笔者面试过程中，被问到MySQL索引时通常也是从底层数据结构特点以及结合磁盘IO两个角度去分析，屡试不爽。

学习一门技术时，我们不仅要知道其优点更要了解其缺点和瓶颈。在分析MySQL索引的实现时，不妨试试从其他数据结构的缺点入手！在Redis中使用跳表实现了有序集合Zset，同样支持高效的顺序查询，对比MySQL索引实现，跳表能否替换B+Tree？如果不行，是因为什么呢？

作者：浪人

来源：https://www.cnblogs.com/liqiangchn/p/12995831.html