MySQL索引

本文最后更新于:2022年10月15日 凌晨

一、索引概述

虽说是概述,但是想要理解其中的内容就得把整个索引学了才明白,所以如果有不懂的没关系,学完再回来看就好,更像是小结一样的存在

1,定义

MySQL官方对索引的定义为:索引是帮助MySql高效获取数据的数据结构。在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用数据,这样就可以在这些数据结构上实现高级查找算法,这就是索引。

2,概述

因为不同的存储引擎会让数据以不同形式存储在磁盘中,所以索引底层采用哪种数据结构是跟数据库的存储引擎相关的(戳此学习MySQL的三种存储引擎)。

  • 如果是MyISAM或者是InnoDB存储引擎,那么对应的底层的数据结构为B+树
  • 如果是MEMORY存储引擎,那么对应的底层的数据结构为Hash表

采用B+树的最根本的原因是由于二叉树的树太高,树太高则直接影响到磁盘IO的次数,影响数据查询的效率。
采用B+树的数据结构,可以在某个数据节点里面尽可能多的存储数据,使树的高度尽量的变低,提高效率。

日常开发过程中,遇到的比较多的可能就是聚簇索引和联合索引,里面又涉及到了覆盖索引,最左匹配,回表,索引下推等各方面的知识点,在编写SQL语句的时候,我们就可以利用这些点来进行优化,提高数据的查询效率。

3,使用条件

  • 对于非常小的表、大部分情况下简单的全表扫描比建立索引更高效;

  • 对于中到大型的表,索引就非常有效;

  • 但是对于特大型的表,建立和维护索引的代价将会随之增长。这种情况下,需要用到一种技术可以直接区分出需要查询的一组数据,而不是一条记录一条记录地匹配,例如可以使用分区技术。

4,优缺点

索引的优势劣势

优势

  • 类似于书籍的目录索引,提高数据检索的效率,降低数据库的IO成本。
  • 通过索引列对数据进行排序,降低数据排序的成本,降低CPU的消耗。

劣势

  • 实际上索引也是一张表,该表中保存了主键与索引字段,并指向实体类的记录,所以索引列也是要占用空间的。
  • 虽然索引大大提高了查询效率,同时却也降低更新表的速度,如对表进行 INSERT、 UPDATE、 DELETE。因为更新表时,MSQL不仅要保存数据,还要保存一下索引文件每次更新添加了索引列的字段,都会调整因为更新所带来的键值变化后的索引信息。

二、索引底层数据结构

MySql之索引 这篇文章堪称教科书哇,太详细了
本想记录学习,却发现原文就已经非常完善了
如果写个简洁版的不如直接看CS Note,所以本文权当我的抄写背诵做笔记吧

1,哈希索引

哈希索引是一种基于哈希表的索引结构,它是一种需要精确匹配才生效的索引结构。

实现原理:对索引列计算哈希值把记录映射到哈希槽中,然后指向对应记录行的地址。

左边是哈希槽,右边是对应的数据列:
哈希索引
优势:

哈希索引能以 O(1) 时间进行查找(除非哈希冲突很高)

劣势:

失去了有序性:

  • 无法用于排序与分组;
  • 只支持精确查找,无法用于部分查找和范围查找。

InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”,当某个索引值被使用的非常频繁时,会在 B+Tree 索引之上再创建一个哈希索引,这样就让 B+Tree 索引具有哈希索引的一些优点,比如快速的哈希查找。

2,红黑树

红黑树的特点:

每个节点的最长子树的只要不超过最短子树的两倍即可

红黑树例1
上图所示,左图在插入数值为3时,红黑树的算法发现有偏向,就会重新调整树结构;调整到右边保持平衡,如持续递增,之前的数据1~7持续递增的树,会变成如下图所示
红黑树例2
递增插入过程红黑树会自动左旋右旋节点以及节点变色,调整树的形态,使其保持基本的平衡状态,也就保证了查找效率不会明显减低。

如上图所示,红黑树下查找 id=7 的所要比较的节点数为 4,依然保持二叉树不错的查找效率。

红黑树很好的解决线性链表问题,但红黑树问题也比较大。
每次插入都要检查规则,再把树进行重新平衡,这个是非常消耗时间,数据量大的话,红黑树的深度会比较深,并且产生“右倾”,树一旦深就代表着我们读取磁盘次数就会增加,因此,不能直接用于实现MySQL底层索引

我们如果把有序二叉树变成有序多叉树,就能降低树的高度,这个就是基于红黑树演变出来的B树的核心思想。

3,B-Tree(B树)

磁盘 IO 特点:

从磁盘读取1B 数据和 1KB 数据所消耗的时间是基本一样的空间局部性与时间局部性决定),根据这个思路,可以在一个树节点上尽可能多地存储数据,一次磁盘 IO 就尽可能多的加载数据到内存,影响数据查询时间的是树的高度,高度越高,比较的次数越多,尽量把树的高度降低,这就是B树的设计原理了

B-Tree特点:

  • 叶节点具有相同的深度。
  • 节点中的元素从左向右递增排序
  • 所有的元素不重复

B-Tree结构图:

B-Tree结构图
B树简单地说就是多叉树,每个叶子会存储数据,和指向下一个节点的指针。

例如要查找9,步骤如下

我们与根节点的关键字 (17,35)进行比较,9 小于 17 那么得到指针 P1;
按照指针 P1 找到磁盘块 2,关键字为(8,12),因为 9 在 8 和 12 之间,所以我们得到指针 P2;
按照指针 P2 找到磁盘块 6,关键字为(9,10),然后我们找到了关键字 9。

小结

总结来说,B 树用作数据库索引有以下优点:

  • 优秀检索速度
  • 尽可能少的磁盘 IO,加快了检索速度
  • 可以支持范围查找

4,B+Tree(B+树)

有了B树知识铺垫,一个树节点我们应该尽可能的包含更多的子节点,但又不能超过一个磁盘页(16kb)的大小。发现B树的节点中还包含了一些关键字信息data,这个data也占据着一定的数据量,如果把data去掉,这样就又能多加很多子节点了。这也就是B+树的核心思想。

对于聚簇索引来说,data存的是数据行,对于非聚簇索引来说,data存的是主键的值

B+Tree特点:

  • 非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
  • 叶子节点包含所有索引字段
  • 叶子节点用双向指针相连,提高区间访问性
  • B+树是通过二叉树,平衡二叉树,B树和索引顺序访问演化而来,是对B树的进一步优化。

B+Tree结构图:

B+Tree结构图
B+树是B树的改进,简单地说是:只有叶子节点才存数据,非叶子节点是存储的指针;所有叶子节点构成一个有序链表

例如要查找关键字16,步骤如下

与根节点的关键字 (1,18,35) 进行比较,16 在 1 和 18 之间,得到指针 P1(指向磁盘块 2)
找到磁盘块 2,关键字为(1,8,14),因为 16 大于 14,所以得到指针 P3(指向磁盘块 7)
找到磁盘块 7,关键字为(14,16,17),然后我们找到了关键字 16,所以可以找到关键字 16 所对应的数据。

B+树和B树有什么不同:

  • B+树非叶子节点不存储数据的,仅存储键值(索引地址),而B树节点中不仅存储键值,也会存储数据。B+树之所以这么做是因为在数据库中页的大小是固定的,innodb中页的默认大小是16KB。如果不存储数据,那么就会存储更多的键值,相应的树的阶数(节点的子节点树)就会更大,树就会更矮更胖,如此一来我们查找数据进行磁盘的IO次数会再次减少,数据查询的效率也会更快

  • B+树索引的所有数据均存储在叶子节点,且数据是按照顺序排列的。B+树使得范围查找,排序查找,分组查找以及去重查找变得简单高效

  • B+树各个页之间是通过双向链表连接,叶子节点中的数据是通过单向链表连接的。我们通过双向链表和单向链表连接的方式可以找到表中所有的数据。

三、常见索引类型

1,唯一索引:

1
2
3
4
5
6
create table User(
`name` varchar(50) not null,
`uid` int(4) not null,
`gender` int(2) not null,
unique key(`name`)
);

进行唯一索引的列,不允许出现两个重复的值(允许空值)

唯一索引主要用于业务上的唯一约束,他跟主键索引的区别是,一个表可以有多个唯一索引

2,主键索引

1
2
3
4
5
6
create table User(
`name` varchar(50) not null,
`uid` int(4) not null,
`gender` int(2) not null,
primary key(`uid`)
);

主键索引是唯一索引的特定类型。主键索引是唯一的,通常以表的ID设置为主键索引,一个表只能有一个主键索引,这是他跟唯一索引的区别。

该索引要求主键中的每个值都唯一。当在查询中使用主键索引时,它还允许对数据的快速访问。

聚簇索引

  • 按照数据存放的物理位置为顺序的,聚簇索引能提高多行检索的速度
  • 通常由主键或者非空唯一索引实现的,叶子节点存储了一整行数据

非聚簇索引

  • 不按照数据存放的物理位置排序,对于单行检索很快
  • 又称二级索引,就是我们常用的普通索引,叶子节点存了索引值和主键值,在根据主键从聚簇索引查

3,单列索引

1
2
3
4
5
6
create table User(
`name` varchar(50) not null,
`uid` int(4) not null,
`gender` int(2) not null,
key(`name`)
);

以某一个字段为索引

4,组合(联合)索引:

1
2
3
4
5
6
create table User(
`name` varchar(50) not null,
`uid` int(4) not null,
`gender` int(2) not null,
key(`name`,`uid`)
);

在多个字段上进行创建索引,只有在查询中

四、索引的优化

待补充

五、参考

MySQL之索引

我的评价是:教科书

MySQL | CS-Notes

也没多简洁


MySQL索引
https://moechun.fun/2022/10/14/MySQL索引/
作者
Knight Kilito
发布于
2022年10月14日
许可协议