MySQL索引
本文最后更新于:2023年3月24日 下午
一、索引概述
虽说是概述,但是想要理解其中的内容就得把整个索引学了才明白,所以如果有不懂的没关系,学完再回来看就好,更像是小结一样的存在
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,红黑树
红黑树的特点:
每个节点的最长子树的只要不超过最短子树的两倍即可
上图所示,左图在插入数值为3时,红黑树的算法发现有偏向,就会重新调整树结构;调整到右边保持平衡,如持续递增,之前的数据1~7持续递增的树,会变成如下图所示
递增插入过程红黑树会自动左旋右旋节点以及节点变色,调整树的形态,使其保持基本的平衡状态,也就保证了查找效率不会明显减低。
如上图所示,红黑树下查找 id=7 的所要比较的节点数为 4,依然保持二叉树不错的查找效率。
红黑树很好的解决线性链表问题,但红黑树问题也比较大。
每次插入都要检查规则,再把树进行重新平衡,这个是非常消耗时间,数据量大的话,红黑树的深度会比较深,并且产生“右倾”,树一旦深就代表着我们读取磁盘次数就会增加,因此,不能直接用于实现MySQL底层索引
我们如果把有序二叉树变成有序多叉树,就能降低树的高度,这个就是基于红黑树演变出来的B树的核心思想。
3,B-Tree(B树)
磁盘 IO 特点:
从磁盘读取1B 数据和 1KB 数据所消耗的时间是基本一样的(空间局部性与时间局部性决定),根据这个思路,可以在一个树节点上尽可能多地存储数据,一次磁盘 IO 就尽可能多的加载数据到内存,影响数据查询时间的是树的高度,高度越高,比较的次数越多,尽量把树的高度降低,这就是B树的设计原理了
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+树是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,主键索引
1 |
|
主键索引是唯一索引的特定类型。主键索引是唯一的,通常以表的ID设置为主键索引,一个表只能有一个主键索引,这是他跟唯一索引的区别。
该索引要求主键中的每个值都唯一。当在查询中使用主键索引时,它还允许对数据的快速访问。
聚簇索引
- 按照数据存放的物理位置为顺序的,聚簇索引能提高多行检索的速度
- 通常由主键或者非空唯一索引实现的,叶子节点存储了一整行数据
非聚簇索引
- 不按照数据存放的物理位置排序,对于单行检索很快
- 又称二级索引,就是我们常用的普通索引,叶子节点存了索引值和主键值,在根据主键从聚簇索引查
3,单列索引
1 |
|
以某一个字段为索引
4,组合(联合)索引:
1 |
|
在多个字段上进行创建索引,只有在查询中
四、索引的优化
待补充
五、参考
我的评价是:教科书
也没多简洁