MySQL 数据库索引技术原理初探

概述

什么是索引

一本书 500 页的书，如果没有目录，直接去找某个知识点，可能需要找一会儿，但是借助前面的目录，就可以快速找到对应知识点在书的哪一页。这里的目录就是索引。

所以，为什么会有索引？为了提高数据查询效率。

常见索引算法

最简单也最容易想到的索引算法就是有序数组了，我们创建一个数组，数组按照顺序排列，

我们要查找某一条记录，使用二分法就可以快速得到(log N)，从图中我们可以看出，有序数组作为索引时，处理等值查询和范围查询时性能会非常优秀。既然这么优秀，为什么我们不使用它呢？

因为它的插入性能很差，每次往中间插入一条记录，就必须挪动后面所有的记录，这个成本太高了。

第二种算法时哈希表，哈希表时一种 KV 形式存储的数据结构，比如我们平时用的 HashMap。哈希表的思路非常简单，用一个哈希函数把 Key 换算成一个确定的位置，把 V 放到这个位置就可以了。

我们可以看得出，哈希表这种数据结构在进行等值查询的时候，效率时非常高的，我们常用的 Redis 以及以前比较流行的 Memcached 都使用了哈希表。但是哈希表有个致命缺陷，就是对范围查询的支持性非常差，因为数据的存储时无序的，无论我们要查询的范围有多大，都必须把所有的数据全部便利一遍做个排序才行。

在讲第三种索引方式之前，我们简单了解下机械硬盘存取数据的原理

要访问磁盘上的某个条数据，我们需要通过磁道，扇区来确定数据所在的 Block，然后通过 Offset 就可以定位到磁盘上的任意一个字节。从磁盘上读取数据时，都是以 Block 的形式读取的。这里我们可以看到，一个 Block 的大小是 512 Bytes，当然，这是针对磁盘设备的，对于 Linux 的文件系统来说，一个 Block 一般是 4KB。InnoDB 数据存取是以数据页为单位的，数据页相比磁盘 Block 要大一些，一般默认是 16KB。为了简化整个模型，我们这里抛开复杂的数据页或者文件系统 Block 概念，从磁盘的 Block 开始说起

假设我们的数据库里面存储了 1000 条记录，每条记录占用 128 Bytes，前面我们说过，一个磁盘的 Block 能够存储 512 Bytes，也就是说，一个 Block 可以存储 4 条记录，存储这些记录，一共需要 250 个 Blocks。当我们需要查询一条数据时，最多需要从磁盘加载 250 个 Blocks，想想读取 250 次磁盘会有多慢！

为了减少对磁盘的访问次数，我们可以把所有记录的 id 单独拿出来创建一个索引 L1，这个 id 和指向原始数据的地址组成了一个新的数据结构，它的长度这里是 16 Bytes，索引也是需要存储到磁盘的，一个 Block 可以存储 32 条索引记录，1000 条索引记录需要 （1000/32=31.25） 32 个 Blocks。这时候我们需要查询一条数据时，就变成了先从索引表中查询出对应数据的指针（读取 32 个 Blocks），然后再去源数据表中根据地址直接读取记录所在的数据块（1 个 Block）。看，通过增加一个索引，我们成功的将磁盘读取次数从 250 次减少到了 33 次。我们可不可以让读取磁盘次数更少呢，当然可以！再增加一级索引呗！

新添加的这一级索引指向了前面我们添加的索引 L1 所在的数据块。在这一级索引上，每一条记录都对应了 L1 索引所在的数据块，也就是 32 条 L1 索引记录所在的位置。1000 条数据在这里还剩多少呢，前面我们说过，1000 条数据共需要 32 个 L1 索引 Block，对应在这里也就是需要 32 条 L2 索引，总空间占用才 32x16 = 512 Bytes，刚好一个磁盘 Block 大小。到这一级，我们需要访问磁盘的次数就变成了 1+1+1=3 了！

我们把上面这个图抽象一下，去掉其中的细节，

当我们把它旋转一下的时候，我们就得到了这样一种数据结构

看！这不就是一棵树嘛

说到树，我们知道最简单的就是二叉树了，二叉树的典型特点是有序，左子树小于父节点，右子树大于父节点。无论是搜索效率还是插入效率，二叉树的效率都是非常高的（log N），但是大多数数据库并不使用它，这是为什么呢？

因为我们的数据是存储在磁盘上的，程序运行过程中要使用数据，必须从磁盘把数据加载到内存才行。二叉树随着节点的增多，树的高度页越来越高，对应到磁盘访问上，我们就需要访问更多的数据块。当我们的数据存储在机械硬盘的时候，从磁盘随机读取一个数据块就需要 10ms 左右的寻址时间，也就是说，如果我们扫描一个 100 万行的表，单独访问一行就可能需要 20 个 10ms，可想可知这个查询会有多慢！

当然，我们这棵树可不是二叉树，因为每个分支都可能有很多条记录。我们把这种树称为 N 叉树，也就是多叉树，树的分叉越多，每个节点的子节点就越多，树的高度就越低。因此就有 B-Tree 和 B+Tree。

B+Tree 索引

讲到 B+ 树索引，我们就不得不一下 B 树索引，前面我们简单了解了下二叉树，我们知道，二叉树的树高太大，会严重影响查询效率，为了解决这个问题，就有了 B 树

B 树是为了更好的实现索引结构而被创造出来的，它大幅度减少了磁盘访问的次数。除此之外，它还充分利用了“局部性原理”（数据有序，相关性强）。

局部性原理：在一段时间内，整个程序的执行仅限于程序的某一部分，相应的，执行所访问的存储空间也局限于某个内存区域。局部性原理分为时间局部性和空间局部性。

• 时间局部性：被引用过一次的存储器位置在未来会被多次引用（通常在循环中）

• 空间局部性：如果一个存储器的位置被引用，那么将来它附近的位置也会被引用

利用局部性原理可以实现磁盘预读，前面提过，InnoDB 一次是读取一页的数据（16K），也就是说，每次我们实际加载的数据比我们需要的可能会多一些，这些数据可以缓存在内存中，未来我们需要读取的时候，就可以避免磁盘 IO 了。

但是 B 树有着下面两个缺陷

• 每个节点都存储数据，因此索引会变得很大，每个 Block 能够容纳的索引数就会变少，我们也就需要访问更多次的磁盘

• 对范围查询支持不是很好，需要中序遍历

为了解决这两个问题，B+ 树就诞生了，

B+树只有叶子节点才存储数据，其它节点不再存储数据，所有的叶子节点都在同一层上，叶子节点之间增加了一条链表，通过这条链表，我们就可以依次直接遍历所有数据。这些变化，让 B+ 树拥有了比 B 树更优秀的特性：

• 非叶子节点不存储数据，可以实现查询加速（一次磁盘访问可以读取更多的索引记录，减少磁盘访问）

• 范围查询更加优秀，可以顺着叶子节点的链表直接查询出某一个范围内的数据

B+数是一棵 N 叉树，N 的大小取决于索引字段的大小，以整数字段索引为例，N≈1200，当树高为 4 的时候，就是 1200 的 3 次方，17 亿。一个 10 亿行的表上一个整数字段索引，查找一个值最多只需要访问 3 次磁盘（树根一般在内存中）。

MySQL 的 InnoDB 就是采用了 B+ 树作为默认的索引算法，前面我们说了，B+树只在叶子节点存储数据，但是这个叶子节点存储的是什么数据呢? 我们根据叶子存储数据类型的不同分为两种索引

• 主键索引，也成为聚簇索引（Clustered index），在叶子节点存储的是整行数据

• 非主键索引，也成为二级索引（Secondary index），叶子节点存储的是主键的值

正因为在 InnoDB 中，我们的数据也是存储在一个索引（主键索引）里的，因此，我们称 InnoDB 是索引组织表。二级索引存储的是数据的主键，当我们使用二级索引查询一条数据的时候，首先会从二级索引中查询到这条记录的 ID，然后拿这个 ID 去主键索引查询真正的数据，我们称这个过程为 回表。

因为二级索引存储的是主键的 ID，因此通常我们会选择 integer 或者 bigint 等整型类型作为主键，这样做的目的是可以减少二级索引占用空间的大小。如果用字符串作为主键，可想可知二级索引会有多大！

除了上面这个外，通常要求主键一定是要自增的，这样做是为了保证主键的有序，每次插入数据都是追加到 B+ 树，避免页分裂（如果数据页满了，则需要申请新的数据页，然后挪动部分数据过去，这个过程叫做 页分裂）的产生，提高数据写入性能。

从上面讲的这些，我们可以想到下面几个优化索引的技巧

• 索引应该尽可能小，这样一次磁盘读取可以返回尽可能多的索引数据，在查询数据时就可以减少磁盘 IO

• 大表查询尽可能的使用索引，不使用索引就会造成全表扫描，想想一个查询，需要遍历几百万数据，读取成千上百次磁盘会有多慢

• 如果可能，尽量使用主键索引进行查询，使用主键索引可以直接触达数据，不需要执行回表，减少磁盘 IO

• 如果索引中包含了我们要查询的所有字段，那就不需要在进行回表，可以减少磁盘 IO，显著提升查询性能，我们把这种查询数据都在索引里面的情况叫做覆盖索引

总结

这次分享中，我们先简单介绍了下两种简单的索引结构，然后从数据在磁盘的存储说起，从没有索引到建立多级索引，解释了为什么会出现树索引以及 B 树索引和 B+树索引，最后我们介绍了下 InnoDB 中关于主键索引和二级索引的概念和几个优化索引的技巧。

• https://blog.csdn.net/yin767833376/article/details/81511377

• https://time.geekbang.org/column/article/69236

• https://www.codeproject.com/Articles/1158559/B-Tree-Another-Implementation-By-Java