MySQL 索引原理

MySQL 索引原理,第1张

MySQL索引深入剖析

官方定义是: 索引(Index)是帮助MySQL高效获取数据的数据结构,简单来说,索引是一种数据结构。以协助快速查询、 更新数据库表中数据。

数据是以文件的形式存放在磁盘上面的,每一行数据都有它的磁盘地址,如果没有索引的话,我们要从千万行数据里面检索一条数据,只能依次遍历这张表的全部数据, 直到找到这条数据。
但是我们有了索引之后,只需要在索引里面去检索这条数据就行了,因为它是一种 特殊的专门用来快速检索的数据结构,我们找到数据存放的磁盘地址以后,就可以拿到 数据了。

生活中随处可见索引的例子,如火车站的车次表、图书的目录等。它们的原理都是一样的,通过不断的缩小想要获得数据的范围来筛选出最终想要的结果,同时把随机的事件变成顺序的事件,也就是我们总是通过同一种查找方式来锁定数据。

一:索引类型

1.1逻辑维度

  • 主键索引:是一 种特殊的唯一索引它还多了一个限制条件,要求键值不能为空。主键索引用primay key 创建。
  • 普通(Normal):也叫非唯一索引,是最普通的索引,没有任的限制。
  • 联合索引:多个字段创建的索引,使用时遵循最左前缀原则。
  • 唯一 (Unique):索引列中的值必须是唯一的,但是允许为空值。
  • 空间索引:MySQL5.7之后支持空间索引,在空间索引这方面遵循OpenGIS几何数据模型规则。

1.2数据结构维度

  • 哈希索引: 适合等值查询,检索效率高,一次到位。
  • B+树索引:所有数据存储在叶子节点,复杂度为O(logn),适合范围查询。
  • 全文(Fulltext):针对比较大的数据,比如我们存放的是消息内容、一篇文章,有 几KB的数据的这种情况,如果要解决like査询在全文匹配的时候效率低的问题,可以创建全文索引。只有文本类型的字段才可以创建全文索引,比如char、varchar、text。
  • R-Tree索引: 用来对GIS数据类型创建SPATIAL索引

1.3物理存储维度

  • 聚集索引:聚集索引就是以主键创建的索引,在叶子节点存储的是表中的数据。
  • 非聚集索引:非聚集索引就是以非主键创建的索引,在叶子节点存储的是主键和索引列。

二:索引存储模型推演

2.1、二分查找

二分查找的一种思想,也叫折半查找,每一次,我们都把候选数据缩小了一半。如果数据已经排过序的话,这种方式效率比较高。 所以第一个,我们可以考虑用有序数组作为索引的数据结构。

2.2、模型推演

1、有序数组,它用于等值查询和比较查询效率非常高,但是更新数据的时候会出现一个问题, 可能要挪动大量的数据(改变index),所以只适合存储静态的数据。

2、哈希结构,类似k-v结构,也就是,key和value是一对一关系。它用于「等值查询」还可以,但是范围查询它是无能为力的。

3、为了支持频繁的修改,比如插入数据,我们需要采用链表。链表的话,如果是单链 表,它的查找效率还是不够高,所以,有没有可以使用二分査找的链表呢?为了解决这个问题,BST (Binary Search Tree)也就是我们所说的二叉査找树诞生

4、二叉查找树的特点是什么?

  • 每个结点最多两个子树,分别称为左子树和右子树
  • 左子节点的值小于当前节点的值,当前节点值小于右子节点值
  • 顶端的节点称为根节点,没有子节点的节点值称为叶子节点

投影到平面以后,就是一个有序的线性表。二叉查找树既能够实现快速查找,又能够实现快速插入。

但是二叉查找树有一个问题,就是它的查找耗时是和这棵树的深度相关的,二叉树在最坏的情况下会退化成一个链表,在最坏的情况下时间复杂度会退化成O(n),相当于全表扫描。因此,一般二叉树不适合作为索引结构。

5、造成它倾斜的原因是什么呢?

因为左右子树深度差太大,这棵树的左子树根本没有节点——也就是它不够平衡。
所以,我们有没有左右子树深度相差不是那么大,更加平衡的树呢,这个就是平衡二叉树,叫做Balanced binary search trees,或者AVL树

平衡二叉树特点:它也是一颗二叉查找树,任何节点的两个子树高度最大差为1。所以就不会出现特殊化一个链表的情况

6、AVL树用于存储索引数据

首先,索引的数据,是放在硬盘上的。查看数据和索引的大小,当我们用树的结构来存储索引的时候,访问一个节点就要跟磁盘之间发生一次10 *** 作。InnoDB *** 作磁盘的最小的单位是一页(或者叫一个磁盘块),大小是16K(16384 字节)。那么,一个树的节点必须设计成16K的大小,不然就会出现读不完或者读不够的情况。

如果我们一个节点只存一个键值+数据+引用,例如整形的字段,可能只用了十几个或者几十个字节,它远远达不到16K的容量。

想象一下,我们基于索引査找数据的时候,肯定是希望一次从磁盘加载很多的数据 到内存中进行比较,这样就可以尽快拿到完整的数据。如果一个节点只存1个这样的单 元,就需要读更多的节点,发生更多的I/O *** 作。如果是机械硬盘时代,每次从磁盘读取数据需要10ms左右的寻址时间,交互次数 越多,消耗的时间就越多

所以AVL树就会有下面的问题:

  • 平衡二叉树插入或者更新时,需要左旋右旋维持平衡,维护代价大
  • 如果数量多的话,树的高度会很高。因为数据是存在磁盘的,以它作为索引结构,每次从磁盘读取一个节点, *** 作IO的次数就多,消耗的时间就越多。

7、怎么解决这个问题?

  • 第一个就是让每个节点存储更多的数据。
  • 第二个节点上的关键字的数量越多,也就是意味着可以有更多的分叉(我们把它叫做"路数”)
  • 第三因为分叉数越多,树的深度就会减少

这样,我们的树是不是从原来的高瘦高瘦的样子,变成了矮胖矮胖的,这个时候,我们的树就不再是二叉了,而是多叉,或者叫做多路。

8、多路平衡查找树(Balanced Tree)

这个就是B树,B树在枝节点和叶子节点存储键值、数据地址、节点引用。
特点:

  • 分叉数(路数)永远比关键字数多1

比如:我们画的这棵树,每个节 点存储两个关键字,那么就会有三个分叉指向三个子节点(当然肯定不只存3个这么少)

9、那B树又是怎么实现一个节点存储多个关键字,还保持平衡的呢?跟AVL树有什 么区别?

B Tree在做检索时,检索效率非常高,但是在做数据插入和删除时,会破坏B Three本身的行知,所以为了保持B Tree的平衡,需要对节点进行分裂、合并、转移等 *** 作,跟AVL树的左旋和右旋是不一样的,而这个 *** 作在节点数量较多的情况下性能影响较大。,所以 解释了为什么我们不要在频繁更新的列上建索引,或者为什么不要更新主键。

节点的分裂和合并,其实就是InnoDB页的分裂和合并。如果索引键值有序,写满一页接着开辟一个新的页,如果索引键值无序,存储过程造成大量磁盘碎片,带来频繁的page分裂和合并。

B树相对于平衡二叉树,就可以存储更多的数据,高度更低。但是最后会选择B+树呢?因为B+树是B树的升级版

10、B+Tree

  • B+树非叶子节点上是不存储数据的,仅存储键值,而B树节点中不仅存储键值,也会存储数据。innodb中页的默认大小是16KB,如果不存储数据,那么就会存储更多的键值,相应的树的阶数(节点的子节点树)就会更大,树就会更矮更胖,如此一来我们查找数据进行磁盘的IO次数有会再次减少,数据查询的效率也会更快。
  • B+树索引的所有数据均存储在叶子节点,而且数据是按照顺序排列的,链表连着的。那么B+树使得范围查找,排序查找,分组查找以及去重查找变得异常简单。

总结一下,InnoDB中的B+Tree特性带来的优势:

  • 它是BTree的变种,BTree能解决的问题,它都能解决
    B Tree解决的两大问题 :每个节点存储更多关键字;路数更多

  • 扫库、扫表能力更强
    如果我们要对表进行全表扫描,只需要遍历叶子节点就可以 了,不需要遍历整棵B+Tree拿到所有的数据

  • B+Tree的磁盘读写能力相对于B Tree来说更强
    根节点和枝节点不保存数据区, 所以一个节点可以保存更多的关键字,一次磁盘加载的关键字更多

  • 排序能力更强
    因为叶子节点上有下一个数据区的指针,数据形成了链表

  • 效率更加稳定
    永远是在叶子节点拿到数据,所以I0次数是稳定的

三:为什么不用红黑树?

红黑树也是BST树,但是不是严格平衡的,不需要像AVL树那样严格平衡,通过变色和旋转来保持平衡。

  • 节点分为红色或者黑色。
  • 根节点必须是黑色的。
  • 叶子节点都是黑色的N U LL节点。
  • 不允许两个相邻的红色节点。
  • 从任意节点出发,至惧每个叶子节点的路径中包含相同数量的黑色节点。
  • 从根节点到叶子节点的最长路径(红黑相间的路径)不大于最短路径(全部是黑色节点)的2倍。

为什么不用红黑树?

  • 1、只有两路
  • 2、不够平衡

红黑树一般只放在内存里面用。例如Java的Map,它可以用来实现一致性哈希。

四:B+Tree作为索引的数据结构带来的好处

由于在B+ Tree中,每个节点不存存储数据区,只需要存储键值+指针,使得B+ Tree在每个节点存储的路数更多。

假设索引字段+指针大小一共是16个字节,那么一个Page页(一个节点)能存储1000个这样的单元(键值+指针)。假设一条记录是16bytes,一个叶子节点(一页)可以存储10条记录!

当数的深度是3的时候,就有1000^2个叶子节点,可存储的数据为1000 x1000 x 10 =10000000(千万)

也就是说,在InnoDB中B+树的深度在3层左右,就能满足千万级别的数据存储。

4.1、InnoDB 索引存储:每张InnoDB的表有两个文件(.frm和.ibd)

在InnoDB的某个索引的叶子节点上,它直接存储了我们的数据。 所以,为什么说在InnoDB中索引即数据,数据即索引,就是这个原因。

  • 但是这里会有一个问题,一张InnoDB的表可能有很多个多索弓|,数据肯定是只有—份的那数据在哪个索引的叶子节点上呢?

    这里的就是聚集索引(聚簇索引),就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。InnoDB组织数据的方式就是(聚集)索引组织表(clustered index organize table)如果说一张表创建了主键索引,那么这个主键索引就是聚集索引,决定数据行的物理存储顺序。

  • 那主键索引之外的索引,会不会也把完整记录在叶子节点放一份呢?

    并不会,因为这会带来额外的存储空间浪费和计算消耗。刚才已经讲了,如果有主键索引,那么主键索引就是聚集索引。其他的索引统一叫做"二级索引”(secondary index)。二级索引存储的是二级索引的键值,例如在name上建立索引,节点上存的是name 的值(很明显,它的键值逻辑顺序跟物理行的顺序不一致)。而二级索引的叶子节点存的是这条记录对应的主键的值。

  • 二级索引检索数据的流程是这样的

    当我们用name索引查询一条记录,它会在二级索引的叶子节点找到,然后拿到主键值,然后再到主键索引的叶子节点拿到数据。

  • 为什么不存地址而是存键值?因为地址会变化。

    从这个角度来说,因为主键索引比二级索引少扫描了一棵B+Tree (避免了回表), 它的速度相对会快一些。

  • 如果一张表没有主键怎么办?

    那完整的记录放在哪个索引的叶子节点?或者, 这张表根本没有索引呢?数据放在哪里?
    1、 如果我们定义了主键(PRIMARY KEY),那么InnoDB会选择主键作为聚集索弘
    2、 如果没有显式定义主键,则InnoDB会选择第一个不包含有NULL值的唯一索引 作为主键索引。
    3、 如果也没有这样的唯一索引,则InnoDB会选择内置6字节长的ROWID作为隐 藏的聚集索引,它会随着行记录的写入而主键递增。

五:B+树 索引搜索过程

###表结构
CREATE TABLE `user` (
  `id` int(11) NOT NULL,
  `name` varchar(255) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `sex` int(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_age` (`age`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

insert into user values(100,'1',43,'0');
insert into user values(200,'2',48,'0');
insert into user values(300,'3',36,'1');
insert into user values(400,'4',32,'0');
insert into user values(500,'5',37,'1');
insert into user values(600,'6',49,'0');
insert into user values(700,'7',28,'1');
select * from user where age=32;
  • idx_age索引的索引结构图:


id主键索引,聚族索引结构图

  • 1搜索idx_age索引树,将磁盘块1加载到内存,由于32<37,搜索左路分支,到磁盘寻址磁盘块2。
  • 2将磁盘块2加载到内存中,在内存继续遍历,找到age=32的记录,取得id = 400.
  • 3拿到id=400后,回到id主键索引树。
  • 4搜索id主键索引树,将磁盘块1加载内存,在内存遍历,找到了400,但是B+树索引非叶子节点是不保存数据的。索引会继续搜索400的右分支,到磁盘寻址磁盘块3.
  • 5将磁盘块3加载内存,在内存遍历,找到id=400的记录,拿到R4这一行的数据,好的,大功告成。

什么是回表?拿到主键再回到主键索引查询的过程,就叫做「回表」

六:覆盖索引

覆盖索引:在查询的数据列里面,不需要回表去查,直接从索引列就能取到想要的结果。换句话说,你SQL用到的索引列数据,覆盖了查询结果的列,就算上覆盖索引了。

这就是项目中不要select *, 而是要使用具体的字段 select id,age 的原因

七:索引下推

可以在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数。

八:联合索引之最左前缀原则

  • 联合索引的最左N个字段。比如组合索引(a,b,c)可以相当于建了(a),(a,b),(a,b,c)三个索引,大大提高了索引复用能力。
  • 最左前缀也可以是字符串索引的最左M个字符。

九:索引创建建议

1、在用于where判断order排序和join的(on)、group by的字段上创建索引
2、索引的个数不要过多——浪费空间,更新变慢。
3、过长的字段,建立前缀索引。
4、区分度低的字段,例如性别,不要建索引——离散度太低,导致扫描行数过多。
5、频繁更新的值,不要作为主键或者索引——B+树的平衡导致 页分裂 ,影响效率
6、随机无序的值,不建议作为索引,例如身份z、UUID、MD5——无序,分裂
7、组合索引把散列性高(区分度高)的值放在前面
8、创建复合索引,而不是修改单列索引

9.1、大表添加索引
可以参考以下方法:
1.先创建一张跟原表A数据结构相同的新表B。
2.在新表B添加需要加上的新索引。
3.把原表A数据导到新表B
4.rename新表B为原表的表名A,原表A换别的表名;

十:索引失效

1、查询条件包含or,可能导致索引失效
2、如果字段类型是字符串,where时一定用引号括起来,否则索引失效
3、like条件中前面带%
4、联合索引,查询时的条件列不是联合索引中的第一个列,索引失效。
5、在索引列上使用mysql的内置函数,列运算(如,+、-、*、/),索引失效。
6、字符串不加引号,出现隐式的类型转化
7、负向查询:索引字段上使用(!= 或者 < >,not in,not like)时,可能会导致索引失效。
8、索引字段上使用is null, is not null,可能导致索引失效。
9、左连接查询或者右连接查询查询关联的字段编码格式不一样,可能导致索引失效。
mysql估计使用全表扫描要比使用索引快,则不使用索引

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/733554.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-27
下一篇 2022-04-27

发表评论

登录后才能评论

评论列表(0条)

保存