[转帖]深入理解mysql-第六章 mysql存储引擎InnoDB的索引-B+树索引

深入,理解,mysql,第六章,存储,引擎,innodb,索引 · 浏览次数 : 0

小编点评

**索引** **3.1 聚簇索引** 聚簇索引是存储在索引中,以快速找到特定记录的方法索引。它可以存储在 B 树叶子节点中,或存储在单独的索引记录中。 **3.2 二级索引** 二级索引是存储在 B 树中,以快速找到特定记录的方法索引。它可以存储在记录的 c2 列中,或存储在单独的索引记录中。 **3.3 联合索引** 联合索引是存储在 B 树中,以快速找到多个记录的方法索引。它可以存储在记录的 c2 列中,或存储在单独的索引记录中。 **索引创建 SQL 命令** ```sql CREATE TABLE 表名 ( 各种列的信息 ··· , [KEY|INDEX] 索引名 (需要被索引的单个列或多个列)) ``` **例如** ```sql CREATE TABLE index_demo( c1 INT, c2 INT, c3 CHAR(1), PRIMARY KEY(c1), INDEX idx_c2_c3 (c2, c3) ); ``` **索引创建语句** ```sql CREATE INDEX idx_c2_c3 ON index_demo (c2, c3); ```

正文

一、引入索引

     在没有索引的情况下,不论是根据主键列或者其他列的值进行查找,由于我们并不能快速的定位到记录所在的页,所以只能从第一个页沿着双向链表一直往下找,因为要遍历所有的数据页,时间复杂度就是O(n),所以这种方式显然是超级耗时的。所以我们需要采取一定的数据结构来存储数据,方便我们进行数据的增删改查操作。

    问题的需求大致定义清楚了,我们现在回想一下,能否利用已经学习过的数据结构解决这个问题呢?支持快速查询、插入等操作的动态数据结构,我们已经学习过散列表、平衡二叉查找树、跳表。

    我们先来看散列表。散列表的查询性能很好,时间复杂度是 O(1)。但是,散列表不能支持按照区间快速查找数据。所以,散列表不能满足我们的需求。

    我们再来看平衡二叉查找树。尽管平衡二叉查找树查询的性能也很高,时间复杂度是 O(logn)。而且,对树进行中序遍历,我们还可以得到一个从小到大有序的数据序列,但这仍然不足以支持按照区间快速查找数据。

    我们再来看跳表。跳表是在链表之上加上多层索引构成的。它支持快速地插入、查找、删除数据,对应的时间复杂度是 O(logn)。并且,跳表也支持按照区间快速地查找数据。我们只需要定位到区间起点值对应在链表中的结点,然后从这个结点开始,顺序遍历链表,直到区间终点对应的结点为止,这期间遍历得到的数据就是满足区间值的数据。

这样看来,跳表是可以解决这个问题。实际上,数据库索引所用到的数据结构跟跳表非常相似,叫作 B+ 树。不过,它是通过二叉查找树演化过来的是m叉查找树,而非跳表。B+ 树发明于 1972 年,跳表发明于 1989 年,有可能跳表发明者参考了B+树的设计。

二、B+树索引的设计

  上一章我们讲到,InnoDB数据页的7个组成部分,知道了各个数据页可以组成一个双向链表,而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表,每个数据页都会为存储在它里边儿的记录生成一个页目录,在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽,然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

    以上是数据在页中的查找过程,当数据页中插入数据呢?因为数据是从小到大排序的(主键值),同时每个数据页是固定大小的(16K),所以当数据插入一个满的数据页时,会发生页的分裂,将大的数据迁移到新数据页(页码数随机),这也叫页分裂。当然删除数据也会造成数据页的删除。

     以上是数据在页中的操作,那在查找数据时如何快速定位到具体的数据页呢?这时候目录页(实际也是数据页,为了和实际存储数据的数据页区分开)就出现了,目录页和数据页的结构一样,目录页的key存储各个页的最小记录的主键值,page存储对应的页号。这样我们就可以快速定位要找到的页,然后进行上面讲的数据页中的查找。

  目录页中的目录项其实长得跟我们的用户记录一样,只不过目录项中的两个列是主键页号而已,所以复用了之前存储用户记录的数据页来存储目录项,为了和用户记录做一下区分,表示目录项的记录称为目录项记录,他们的记录头信息里的record_type属性和普通数据不一样:

  • 0:普通的用户记录
  • 1:目录项记录
  • 2:最小记录
  • 3:最大记录

目录项记录和普通的用户记录的不同点:

  • 目录项记录record_type值是1,而普通用户记录的record_type值是0。

  • 目录项记录只有主键值和页的编号两个列,而普通的用户记录的列是用户自己定义的,可能包含很多列,另外还有InnoDB自己添加的隐藏列。

  • 还记得我们之前在唠叨记录头信息的时候说过一个叫min_rec_mask的属性么,只有在存储目录项记录的页中的主键值最小的目录项记录min_rec_mask值为1,其他别的记录的min_rec_mask值都是0

除了上述几点外,这两者就没啥差别了,它们用的是一样的数据页(File Header中页面类型都是0x45BF),页的组成结构也是一样的(就是我们前边介绍过的7个部分),都会为主键值生成Page Directory(页目录),从而在按照主键值进行查找时可以使用二分法来加快查询速度。

   当然如果我们表中的数据非常多则会产生很多存储目录项记录的页,那我们怎么根据主键值快速定位一个存储目录项记录的页呢?其实就是目录页上一层在生成自己的目录页。如下图:

 从图中可以看出来,一个B+树的节点其实可以分成好多层。因为每一个数据页能放很多条数据,所以树的高度不会很高,假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录,所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录,那么:

  • 如果B+树只有1层,也就是只有1个用于存放用户记录的节点,最多能存放100条记录。

  • 如果B+树有2层,最多能存放1000×100=100000条记录。

  • 如果B+树有3层,最多能存放1000×1000×100=100000000条记录。

  • 如果B+树有4层,最多能存放1000×1000×1000×100=100000000000条记录。

扩展一下,B-树、B 树跟 B+ 树的不同点主要集中在这几个地方:

  • B- 树就是 B 树,英文翻译都是 B-Tree,这里的“-”并不是相对 B+ 树中的“+”,而只是一个连接符。
  • B+ 树中的节点不存储数据,只是索引,而 B 树中的节点存储数据;
  • B 树中的叶子节点并不需要链表来串联。

三、索引的分类

 3.1 聚簇索引

   上面我们介绍索引时候,实际已经了解到,mysql的存储引擎InnoDB在存储数据记录的时候,已经使用记录主键值的大小进行记录和页的排序,按照B+树的数据结构存储目录,叶节点存储页码,也可以理解为叶子结点存储了数据,非叶子节点都是存储的目录信息,也就是索引信息,或者说这本身就是一个索引,也就是聚簇索引。他的主要存储结构:

  • 页内的记录是按照主键的大小顺序排成一个单向链表。

  • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。

  • 存放目录项记录的页分为不同的层次,在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。

  • B+树的叶子节点存储的是完整的用户记录(实际也可以理解为叶子节点是页码,B+不存储数据)。

  聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建(后边会介绍索引相关的语句),InnoDB存储引擎会自动的为我们创建聚簇索引。

 

 3.2 二级索引

    聚簇索引只能在搜索条件是主键值时才能发挥作用,因为B+树中的数据都是按照主键进行排序的。我们针对某一列的查询条件快速定位,可以对特定的列进行B+树的创建,构建索引,提高查询效率。这样我们构建这一列的B+树的特点就是:

  • 页内的记录是按照c2列的大小顺序排成一个单向链表。
  • 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表。
  • 存放目录项记录的页分为不同的层次,在同一层次中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表。
  • B+树的叶子节点存储的并不是完整的用户记录,而只是c2列+主键这两个列的值。
  • 目录项记录中不再是主键+页号的搭配,而变成了c2列+页号的搭配。

  当我们进行查询的时候,查询步骤和聚簇索引一样,限定从目录页定位到数据页页码,然后根据数据页内查找找到对应的行,拿到行中数据的主键进行聚簇索引的查找和定位具体数据,这就是回表操作,因为建立非主键的索引会重新建一个b+树,查询数据因为要有回表操作二查询两次B+树,所以也是二级索引命名的由来。

 3.3 联合索引

   同二级索引,我们也可以对多个列进行加索引操作,实际就是以两个列的大小排序建立一个B+树,比方说我们想让B+树按照c2c3列的大小进行排序:

  • 先把各个记录和页按照c2列进行排序。
  • 在记录的c2列相同的情况下,采用c3列进行排序。
  • 每条目录项记录都由c2c3页号这三个部分组成,各条记录先按照c2列的值进行排序,如果记录的c2列相同,则按照c3列的值进行排序。

  • B+树叶子节点处的用户记录由c2c3和主键c1列组成。

 

 四、索引创建SQL命令

 

  我们可以在创建表的时候创建非主键字段的二级索引和联合索引:

  1. CREATE TALBE 表名 (
  2. 各种列的信息 ··· ,
  3. [KEY|INDEX] 索引名 (需要被索引的单个列或多个列)
  4. )

其中的KEYINDEX是同义词,任意选用一个就可以。我们也可以在修改表结构的时候添加索引:

ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的单个列或多个列);

也可以在修改表结构的时候删除索引:

ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;

 比方说我们想在创建index_demo表的时候就为c2c3列添加一个联合索引,可以这么写建表语句:

  1. CREATE TABLE index_demo(
  2. c1 INT,
  3. c2 INT,
  4. c3 CHAR(1),
  5. PRIMARY KEY(c1),
  6. INDEX idx_c2_c3 (c2, c3)
  7. );

 

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览48031 人正在系统学习中

与[转帖]深入理解mysql-第六章 mysql存储引擎InnoDB的索引-B+树索引相似的内容:

[转帖]深入理解mysql-第六章 mysql存储引擎InnoDB的索引-B+树索引

一、引入索引 在没有索引的情况下,不论是根据主键列或者其他列的值进行查找,由于我们并不能快速的定位到记录所在的页,所以只能从第一个页沿着双向链表一直往下找,因为要遍历所有的数据页,时间复杂度就是O(n),所以这种方式显然是超级耗时的。所以我们需要采取一定的数据结构来存储数据,方便我们进行数据的增删改

[转帖]深入理解mysql-第五章 InnoDB记录存储结构-页结构

前言: 页是InnoDB管理存储空间的基本单位,上一章我们主要分析了页中的主要的构成行的存储结构-行格式,其中简单提了一下页的概念。这章我们详细讲解一下页的存储结构。 一、数据页结构 前边我们简单提了一下页的概念,它是InnoDB管理存储空间的基本单位,一个页的大小一般是16KB。和存储一条条数据的

[转帖]深入理解mysql-第十章 mysql查询优化-Explain 详解(上)

目录 一、初识Explain 二、执行计划-table属性 三、执行计划-id属性 四、执行计划-select_type属性 一条查询语句在经过MySQL查询优化器的各种基于成本和规则的优化会后生成一个所谓的执行计划,这个执行计划展示了接下来具体执行查询的方式,比如多表连接的顺序是什么,对于每个表采

[转帖]Redis 运维实战 第01期:Redis 复制

https://cloud.tencent.com/developer/article/1986816 作者简介 马听,多年 DBA 实战经验,对 MySQL、 Redis、ClickHouse 等数据库有一定了解,专栏《一线数据库工程师带你深入理解 MySQL》作者。 从这篇文章开始,将出几期 R

[转帖]深入理解mysql-第十一章 mysql查询优化-Explain 详解(中)

一、执行计划-type属性 执行计划的一条记录就代表着MySQL对某个表的执行查询时的访问方法,其中的type列就表明了这个访问这个单表的方法具体是什么,比方说下边这个查询: mysql> EXPLAIN SELECT * FROM s1 WHERE key1 = 'a';+ + + + + + +

[转帖]深入理解mysql-第十二章 mysql查询优化-Explain 详解(下)

我们前面两章详解了Explain的各个属性,我们看到的都是mysql已经生成的执行计划,那这个执行计划的是如何生成的?我们能看到一些过程指标数据吗?实际mysql贴心为我们提供了执行计划的各项成本评估指标的以及优化器生成执行计划的整个过程的方法。 一、查看执行计划计算的成本数据 我们上边介绍的EXP

[转帖]MySQL 慢查询日志深入理解

https://www.jb51.net/article/210312.htm + 目录 什么是慢查询日志 MySQL的慢查询日志是 MySQL提供的一种日志记录,它用来记录在 MySQL 中响应时间超过阀值的语句,具体指运行时间超过long_query_time 值的 SQL,则会被记录到慢查询日

[转帖]Intel PAUSE指令变化如何影响MySQL的性能

https://zhuanlan.zhihu.com/p/581200704 导读 x86、arm指令都很多,无论是应用程序员还是数据库内核研发大多时候都不需要对这些指令深入理解,但是 Pause 指令和数据库操作太紧密了,本文通过一次非常有趣的性能优化来引入对 Pause 指令的理解,期望可以事半

【转帖】mysql一个索引块有多少指针_深刻理解MySQL系列之索引

索引 查找一条数据的过程 先看下InnoDB的逻辑存储结构:node 表空间:能够看作是InnoDB存储引擎逻辑结构的最高层,全部的数据都存放在表空间中。默认有个共享表空间ibdata1。若是启用innodb_file_per_table参数,须要注意每张表的表空间内存放的只是数据、索引和插入缓冲B

[转帖]深入理解同步机制---内核自旋锁

https://switch-router.gitee.io/blog/spinlock/ 进程(线程)间的同步机制是面试时的常见问题,所以准备用一个系列来好好整理下用户态与内核态的各种同步机制。本文就以内核空间的一种基础同步机制—自旋锁开始好了 自旋锁是什么 自旋锁就是一个二状态的原子(atomi