Database
索引技术原理初探

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

mylxsw, 11/27/2022 mysql

概述

什么是索引

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

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

常见索引算法

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

img

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

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

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

img

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

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

image-20210326092749979

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

image-20210326092835533

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

image-20210326092923323

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

image-20210326093000953

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

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

image-20210326093031086

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

image-20210326093055460

看!这不就是一棵树嘛

image-20210326104832514

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

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

_images/binary-tree.png

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

Image 1

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),叶子节点存储的是主键的值

image-20210326115557786

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

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

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

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

  • 索引应该尽可能小,这样一次磁盘读取可以返回尽可能多的索引数据,在查询数据时就可以减少磁盘 IO
  • 大表查询尽可能的使用索引,不使用索引就会造成全表扫描,想想一个查询,需要遍历几百万数据,读取成千上百次磁盘会有多慢
  • 如果可能,尽量使用主键索引进行查询,使用主键索引可以直接触达数据,不需要执行回表,减少磁盘 IO
  • 如果索引中包含了我们要查询的所有字段,那就不需要在进行回表,可以减少磁盘 IO,显著提升查询性能,我们把这种查询数据都在索引里面的情况叫做覆盖索引

总结

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