Mysql 索引系列(一):索引的实现


Mysql 数据库是目前最流行使用最广泛的关系型数据库,通过本系列来复习一下 Mysql 索引相关的知识。
本篇文章来讲解一下索引的具体实现。

为什么要使用索引

1
什么是索引?为什么要使用索引?

索引就是存储引擎用于快速找到记录的一种数据结构。把数据库比做一本书,如果查找内容就需要每一页每一页的找,那岂不是效率很低。
那么我们设计了一套规则:

  • 将书分按照一章一章的分类,每一章又分为不同的小章节
  • 将分好的章节信息保存在目录页里

每次查询的时候我们先查找目录,找到目标的章节,最后一直找到想要找到的内容。

通俗来说,索引的设计就是用来加快数据库的访问速度。

索引的实现方式

通常为了加快数据的速度,一般两种数据结构来实现:

  • Hash 哈希
  • Tree 树

Hash 结构

通过 Hash 函数将数据映射到哈希桶里,哈希桶是顺序存储的数据结构,所以插入/更新/删除数据时,可以直接找到数据的位置,时间复杂度是 O(1)。可以说是非常快速

Mysql 的 memory 存储引擎使用的就是哈希索引。

Tree 结构

二叉搜索树

二叉搜索树是我们最熟悉页最常见的树结构,如下图所示:

二叉搜索树

我们看到,由于二叉搜索树是二叉的,所以当数据量很大的时候,存在以下问题:

  1. 树的高度比较高
  2. 每个节点只能存储一条记录,每次查询到该节点都要进行磁盘 I/O

二叉搜索树的查找时间复杂度是 O(logn)

B 树

为了适用数据库的查找,发明了 B 树的数据结构,实际上是一种多路搜索树,如下图所示:

B树

B 树的特点是:

  • 不再是二叉,而是多叉
  • 叶子节点和非叶子节点都存储数据
  • 每个非根节点可以存储多条记录,个数满足 (m/2 - 1) <= j <= m-1
  • 中序遍历可以获取所有节点

可以发现,B 树相对于二叉搜索树,高度大大降低,并且每个非叶子节点可以存储多条记录,这样做有什么好处?
这是因为这样做,可以利用局部性原理来降低磁盘 I/O,提高读取效率。

这里简单解释一下局部性原理。

局部性原理

  1. 磁盘的读取相对内存来说要慢很多,所以应尽量减少磁盘的读取操作。
  2. 磁盘预读,磁盘一次读取,并不会按需读取,而是按页读取,一次读一页,如果以后要读的数据就在这一页中,就可以避免再次读取磁盘,提高效率。
  3. 软件或程序设计过程中应该尽量遵循这样的原则,例如,对于 B 树的非叶子节点来说,每个节点可以设置为一页的数据,只需读取一次即可。

通常,磁盘读取一页的数据是 4k

B 树一般被用来设计做数据库的索引的优势:

  • 多叉搜索树,高度降低。
  • 每个节点存储多个记录,利用局部性原理,降低了磁盘读取次数,提高了读取效率
1
哈希索引更快更简单,数据库为什么不使用哈希索引?

哈希索引是更快,但是哈希索引对于 分组(group by)排序(order by)以及范围查找(> <)需要全表扫描才行,时间复杂读退化为 O(n)

Mysql Innodb 索引的实现

Mysql Innodb 存储引擎的索引使用的是在 B 树上优化的一种数据结构,B+ 树。
B+ 树也是多路搜索树,是在 B 树的基础上优化而来,如下图所示:

B+树

B+ 树具备 B 树的优点,同时又做了以下优化:

  1. 非叶子节点上不再存储数据,只记录记录的key,只有叶子节点上才存储数据记录
  2. 所有的叶子节点,都通过链表连接起来,方便了范围查找

优化的好处:

  1. 非叶子节点不存数据,只记录 key,相同内存下,B+树存储更多的索引
  2. 增加的链表,方便了范围查找。

聚集索引和非聚集索引

这里简单介绍下聚集索引和非聚集索引的区别。

聚集索引

聚集索引就是索引和数据记录存储在一起的索引,例如在上面说的 B+树的数据结构中,叶子节点最终保存的不仅是索引的 key ,还包括索引的数据。InnoDB 就是使用的聚集索引,
如下图就是 InnoDB 的主键索引的存储结构:

InnoDB 的主键索引结构

可以看到叶子节点上本身就存在数据,所以通过索引查找可以直接查找到数据。

聚集索引的好处:

  • 可以把数据保存在一起。只需要从磁盘读取少数的数据也就能获取数据。
  • 数据访问更快。
  • 使用覆盖索引扫描的查询可以直接使用节点的主键值

非聚集索引

和聚集索引相反,非聚集索引就是数据和索引分开存储的索引。MyISAM 使用的就是非聚集索引

MyISAM 的索引结构

可以看到,叶子节点存储的的是索引的 key 和 行号, 行号即索引数据在数据文件的位置。

二级索引

对于 InnoDB 来说,主键索引是聚集索引,但是二级索引(辅助索引)和聚集索引很不相同。InnoDB 二级索引的叶子节点存储的是主键值,所以,二级索引查找可能需要查找两次
首先根据索引查找到数据的主键值,然后再根据主键从主键索引查到数据。

所以,从这一点来看,我们就明白了 InnoDB 必须存在主键,如果没有显示的主键,InnoDB 会先查找非空的唯一索引当主键,否则会自己生成一个隐藏的主键。

对于 MyISAM 来说,二级索引和主键索引的实现方式一样。

总结

只有了解了索引的底层实现,才能更好的使用索引和优化索引。