关于后端:MySQL-数据库索引技术原理初探

4次阅读

共计 3745 个字符，预计需要花费 10 分钟才能阅读完成。

一本书 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 索引，总空间占用才 32×16 = 512 Bytes，刚好一个磁盘 Block 大小。到这一级，咱们须要拜访磁盘的次数就变成了 1+1+1=3 了！

咱们把下面这个图形象一下，去掉其中的细节，

当咱们把它旋转一下的时候，咱们就失去了这样一种数据结构

看！这不就是一棵树嘛

说到树，咱们晓得最简略的就是二叉树了，二叉树的典型特点是有序，左子树小于父节点，右子树大于父节点。无论是搜寻效率还是插入效率，二叉树的效率都是十分高的（log N），然而大多数数据库并不应用它，这是为什么呢？

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

当然，咱们这棵树可不是二叉树，因为每个分支都可能有很多条记录。咱们把这种树称为 N 叉树，也就是多叉树，树的分叉越多，每个节点的子节点就越多，树的高度就越低。因而就有 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+ 树，防止页决裂（如果数据页满了，则须要申请新的数据页，而后移动局部数据过来，这个过程叫做页决裂）的产生，进步数据写入性能。

从下面讲的这些，咱们能够想到上面几个优化索引的技巧