MySQL-索引的结构与分类

索引概述

介绍:

索引(index)是帮助MySQL高效获取数据数据结构(有序)。在数据之外,数据库系统还维护者满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法,这种数据结构就是索引。

执行一条sql语句:select * from user where age = 45

无索引的情况:

image-20240731145802428

会从第一条记录开始匹配,判断age是否为45;直到匹配成功之后,因为不确定后面会不会还有age = 45的情况,所以仍然会继续匹配,直到把整张表都遍历一遍。这种情况称为全表扫描,性能极低

有索引的情况:

image-20240731150232981

以二叉树为例(并不是真实的索引结构,只是以二叉树为例),如果要对age建立索引,当要往表中插入一条数据时,就要维护二叉树的节点,而这个节点要指向这行数据的地址。

当要45和36匹配时,45比36大,所以往右边走,跟48匹配;

比48小,所以往左边走,就找到了45。

找到45之后,就能通过这个节点的指向找到这一行数据。有索引的情况下只需匹配3次就能找到对应的数据。这个搜索效率是非常高效的。

索引的优缺点:

优势:

  • 提高数据检索的效率,降低数据库的IO成本
  • 通过索引列对数据进行排序,降低数据排序的成本,降低CPI的消耗

劣势:

  • 索引列也是要占用空间的
  • 索引大大提高了查询效率,同时却也降低更新表的速度,如对表进行INSERT、UPDATE、DELETE时,效率降低

索引结构

在MySQL体系结构中,索引是在第三层,存储引擎层实现的。这也意味着,根据存储引擎的不同,索引的结构也会不同。主要包含以下几种:

image-20240731152625720

  1. B+Tree索引:最常见的索引类型,大部分引擎都支持B+树索引。
  2. Hash索引:底层数据结构是用哈希表实现的,只有精确匹配索引列的查询才有效,不支持范围查询
  3. R-tree(空间索引):空间索引是MyISAM引擎的一个特殊索引类型,主要用于地理空间数据类型,通常使用较少。
  4. Full-text(全文索引):是一种通过简历倒排索引,快速匹配文档的方式。类似于Lucene,Solr,ES。

二叉树

从二叉树的根节点开始,比根节点大的走右边,比根节点小的走左边。这样往往会有两个缺点:

  1. 顺序插入时,会形成一个链表,查询性能大大降低。
  2. 大数据量情况下,层级较深,检索速度慢。

image-20240731153117127

为了解决第一个问题,可以利用红黑树:

红黑树虽然解决了第一个问题,但是依然会存在第二个问题,大数据量情况下,层级较深,检索速度慢。

image-20240731153641500

B-Tree(多路平衡查找树)

以一棵最大度数(max-degree)为5(5阶)的b-tree为例(每个节点最多存储4个key,5个指针):

image-20240731154145145

比20小的数在第一个子节点,20到30之间的数在第二个子节点,以此类推。

简单介绍一下B-Tree的裂变方式:

通过数据结构可视化网站来演示

  1. 一个节点中有4个元素
    image-20240801093537066

  2. 当我再往里面插入元素的时候,中间的元素会往上裂变,把两边的元素分成两个子节点

    image-20240801093725454

  3. 以此类推,当某子节点中的元素达到了裂变条件,也会像步骤2一样裂变

    比如在下面元素中再插入元素8

    image-20240801093916928

    当插入元素8之后,元素6就会往上裂变,而裂变的元素会跟元素3处于同一个节点中,直至根节点再次发生裂变

    image-20240801093944071

  4. 当子节点需要往父节点发生裂变后,父节点也需要裂变时,就会往上裂变一层,如下图

    image-20240801094333105

    当插入元素17时,子节点就会发生裂变,而元素15裂变到根节点后,根节点也需要发生裂变了

    image-20240801094524691

B+Tree

B+Tree实际上是B-Tree的变种,以一棵最大读书(max-degree)为4(4阶)的B+Tree为例:

image-20240801095338196

在B+Tree中,叶子节点形成一个单向链表。所有的元素都会出现在叶子节点,叶子节点用来存放数据,而黄色部分的非叶子节点只起到索引的作用

裂变过程跟B-Tree一样,但是裂变到上层节点的元素在子节点也会存在,并不会消失。如:

image-20240801110950494

再插入一个元素12,该B+Tree就达到了裂变的条件

image-20240801111033780

虽然11裂变到了上一层节点,但是在叶子节点中,11元素依然会保留。

与B-Tree的区别:

  1. 所有的数据都会出现在叶子节点
  2. 叶子节点形成一个单项列表

MySQL中B+Tree的索引结构

MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上,增加一个指向相邻叶子节点的链表指针,就形成了带有顺序指针的B+Tree,提高区间访问的性能。

image-20240801111422341

Hash索引

哈希索引就是采用一定的hash算法,将键值换算成新的hash值,映射到对应的槽位上,然后存储在hash表中。

如果两个(或多个)键值,映射到同一个槽位上,他们就产生了hash冲突(也成为hash碰撞),可以通过链表来解决。

如下表,要为name字段创建一个hash索引,

需要先算出这个表中每一行数据的hash值,再拿到name字段是所有值,针对name字段的所有值,通过内部的哈希函数算法去计算每一个name值应该落在哪个hash表的对应槽位上。

如金庸,算出来槽位值为005,那么在005槽位中就会存储金庸(key)和58dda(值),58dda代表的是金庸这个key,对应的这一行所代表的hash值。

image-20240801141949681

出现hash冲突时,就会在对应的槽位里形成一个链表,如下图杨逍计算出来的槽位值也是005。

image-20240801143151609

Hash索引特点:

  1. Hash索引只能用于对等比较(=,in),不支持范围查询(between,>,<,…)。
  2. 无法利用索引完成排序操作。
  3. 查询效率高,通常只需一次检索就可以了,效率通常要高于B+Tree索引。

存储引擎支持:

在MySQL中,支持hash索引的是Memory引擎,而InnoDB中具有自适应hash功能(在指定的条件下会自动的将B+Tree索引构建为Hash索引)。

为什么InnoDB存储引擎选择使用B+Tree索引结构

  1. 相对于二叉树,层级更少,搜索效率高。
  2. 对于B-Tree,无论是叶子节点还是非叶子节点,都会保存数据,这样导致一页中存储的键值减少,指针跟着减少,要同样保存大量数据,只能增加树的高度,导致性能降低。
  3. 相对Hash索引,B+Tree支持范围匹配以及排序操作。

第2点说明:如下图所示。在InnoDB中,页是磁盘操作的最小单元,一个页的大小是固定的16k。如果在非叶子节点中也存储数据,就占用了页的一部分空间,导致一页中存储的键值减少。从而导致存储相同的数据,用的页就会多,也就是增加了树的高度。

image-20240801111422341

索引分类

image-20240813150304282

索引主要分为4类:

  1. 主键索引
  2. 唯一索引
  3. 常规索引
  4. 全文索引

主键索引只能有一个其他索引可以有多个

聚集索引和二级索引

image-20240813150722506

在InnoDB存储引擎中,根据索引的存在形式,又可以分为:聚集索引、二级索引。

在很多地方会把二级索引称为辅助索引非聚集索引

聚集索引选取规则:

  1. 如果存在主键,主键索引就是聚集索引。
  2. 如果不存在主键,将使用第一个唯一索引作为聚集索引。
  3. 如果表没有主键,或没有合适的唯一索引,则InnoDB会自动生成一个rowid作为隐藏的聚集索引。

聚集索引结构图:

image-20240813151548108

上图中,第一个叶子节点5中的row,值的就是id为5的这一行对应的数据。

二级索引结构图:

image-20240813151844924

根据name字段再建立一个索引,是一个二级索引。二级索引的叶子节点下面挂着的是叶子节点的name值对应的这一行元素的id

回表查询

image-20240813174435300

当执行select * from user where name = 'Arm'的时候,会走下面的索引,找到Arm之后,就拿到了ID。然后根据ID再走一次聚集索引。这个过程称为回表查询

回表查询指先走二级索引找到对应的主键值,再根据主键值到聚集索引中拿到这一行的行数据。

总结:

聚集索引B+Tree的叶子节点下面挂着的是这一行的数据。

二级索引B+Tree的叶子节点下面挂着的是对应的id。

执行效率判断

问题一:以下SQL语句那个执行效率高?为什么?

1. select * from user where id = 10;
2. select * from user where name = 'Arm'
备注:id为主键,name字段创建的有索引

SQL1的执行效率高。因为只用经过一次聚集索引就可以查出来。

SQL2需要进行回表查询,先经过二级索引查出id,再通过聚集索引查出行数据。

问题二:InnoDB主键索引的B+Tree高度有多高呢?

假设:一行数据大小为1k,一页中可以存储16行这样的数据。InnoDB的指针占用6个字节的空间,主键即使为bigint,占用字节数为8。

高度为2:n * 8 + (n+1) * 6 = 16*1024,算出n约为1170,1171 * 16 = 18736。

创作不易!转载请注明作者及文章链接或作者博客链接——
- 作者:pidanxia
- 链接:https://pidanxia.ink
(链接可为:**文章链接**或者**作者博客链接**)
暂无评论

发送评论 编辑评论


				
上一篇
下一篇