深入浅出数据库索引

基本概念

数据库系统中文件索引的工作方式非常类似于书的索引。索引的出现就是为了提高数据查询的效率。

例如,为了根据给定ID检索一条student记录,数据库首先会查找索引,找到对应记录的磁盘块,然后取出该磁盘块,得到对应的记录。

有两种基本的索引类型:

  • 顺序索引:基于值得顺序排序
  • 散列索引:基于将值平均分布到若干bucket中,一个值所属的bucket是由一个散列函数决定。

用于在文件中查找记录得属性或属性集称为搜索码,一个文件有多个索引就有多个搜索码。

如果包含记录得文件按照某个搜索码指定的顺序排序,那么该搜索码对应的索引称为聚集索引。搜索码指定得顺序与文件记录的物理顺序不同的索引称为辅助索引

索引的常见模型

Hash表

Hash表是一种以Key-Value存储数据的结构。Hash把值放在数组里,通过Hash函数把key换算成一个确定的位置,然后将value存放在数组的这个位置。当然可能存在Hash冲突,可以通过拉链法,再Hash法等方法来解决Hash冲突。

Hash表示意图

当然,Hash表结构存在一定的局限性,如果需要查找指定区间的所有用户,就必须全部扫描一遍。所以,Hash表这种结构适用于只有等值查询的场景

有序数组

有序数组在等值查询和范围查询的场景中的性能都非常优秀,使用二分法进行查询,这个时间复杂度就是O(logN)。如果使用有序数组存储上文用户信息,示意图如下所示:

有序数组示意图

但是有序数组存在一些问题,在中间插入记录就必须挪动后面所有的记录,成本过高,所以,有序数组只适用于静态存储引擎。也就是不会再修改的数据。

二叉搜索树

二叉搜素树的特点:

  • 节点的左儿子节点小于父节点,右节点大于父节点。

二叉搜索树的查询复杂度为O(logN),但是需要维护该树为平衡二叉树,维护的复杂度为O(logN)

BST示意图

二叉树的搜索效率非常高,但是实际上大多数数据库存储并不使用二叉树,原因是:索引不仅存在内存中,还要写到磁盘中。

例如,一颗100万节点的平衡二叉树,树高为20,一次查询可能需要访问20个数据块,对于机械硬盘,从磁盘随机读一个数据库需要10ms左右的寻址时间,也就是用二叉树存储,单独访问一个行可能需要20个10ms的时间。

为了让一个查询尽量少读磁盘,就必须让查询过程访问尽量少的数据块,因此使用N叉树,N取决于数据块的大小。

在MySQL中,索引是在存储引擎层实现的,并没有统一的索引标准,即不同存储引擎的索引的工作方式并不一样,而即使多个存储引擎支持同一种类型的索引,其底层的实现也可能不同。下文介绍InnoDB存储引擎的索引模型。

InnoDB的索引模型

在InnoDB中,表是按照主键顺序以索引的形式存放的,这种存储方式的表称为索引组织表,InnoDB使用了B+树索引模型,所以数据都是存放在B+树中的。每一个索引在InnoDB中对应一棵B+树。

假设有一个主键为ID的表,有字段k,并且k上有索引。

1
2
3
4
5
create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;

数据为:

id k
100 1
200 2
300 3
400 4
500 5

该表有两棵B+树,示意图如下:

该表B+树示意图

根据叶子节点的内容,索引类型分为主键索引(聚簇索引)和非主键索引(二级索引)。主键索引的叶子节点存的是整行数据,非主键索引叶子节点内容是主键的值。

区别

如果语句为select * from T where ID = 500,则只需要搜索ID这棵B+树。

如果语句为select * from T where k = 5,则向搜索k这棵B+树,得到的值为500,再到ID这棵B+树搜索一次,这个过程称为回表

索引维护

B+树在插入新值的时候必须做必要的维护,如果添加新值的时候,所在数据页已经满了,这时需要申请一个新的数据页,然后挪动部分数据过去,这个过程称为页分裂。如果删除数据,可能导致页的合并。

覆盖索引

如果执行的语句为select ID from T where k between 3 and 5,这时只需要查ID的值,而ID的值已经在k索引树上了,因此不需要回表,也就是,索引k已经覆盖了我们的我们的查询请求,这被称为覆盖索引

由于覆盖索引可以减少树的搜索次数,显著提升查询性能,所以使用覆盖索引是一个常用的性能优化手段。

最左前缀原则

B+树这种索引结构,可以利用索引的最左前缀,来定位记录。

如果你创建了一个三列的联合索引包含(col1, col2, col3), 你的索引会生效于(col1), (col1, col2), 以及(col1, col2, col3)。

问题:在建立联合索引的时候,如何安排索引内的字段顺序?

  • 第一原则是,如果通过调整顺序,可以少维护一个索引,那么这个顺序往往是需要优先考虑采用的。

如果有一个联合索引(a,b),查询条件里面如果只有b的语句,是无法使用这个联合索引的。

这时候需要考虑的原则就是空间。

索引下推

以联合索引(name, age)为例,如果查找”名字第一个字是张,年龄是10岁的所有男孩”,SQL语句如下:

1
select * from user where name like '张%' and age = 10 and ismale = 1;

根据最左前缀原则,找到第一个满足第一个字是张的记录之后,判断其他条件是否满足。

在MySQL 5.6之前,只能从该记录开始一个个回表,到主键索引树上找到指定数据行,进行字段值比对。

在MySQL5.6引入索引下推优化,可以在索引遍历的过程中,对索引中包含的字段先进行判断,直接过滤掉不满足条件的记录,减少回表次数。

文章作者: L1nker4
文章链接: https://l1n.wang/2020/05/db-index/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 L1nker4's Blog