关于后端:别告诉我你还不懂索引

8次阅读

共计 8170 个字符，预计需要花费 21 分钟才能阅读完成。

大家好，我是🐟老师，明天咱们来学习索引。

文章浏览时长约 13 分钟。

什么是索引呢

索引是一个对存储的数据进行疾速检索的数据目录，在数据磁盘的索引区内存储的就是数据的目录，数据磁盘的数据区就是具体存放数据的区域。

索引是帮忙 MySQL 高效获取数据的排好序的数据结构（存储构造）

索引的数据结构有很多种：

  • 二叉树
  • 红黑树
  • Hash 表
  • B-Tree
  • ……

上面咱们用较为简单的二叉树来体验一下索引是如何高效的查找 mysql 表数据的？
其中二叉树的节点构造为 key 和 value 两个属性，key 为字段的数值，value 为索引指向的磁盘地址文件指针
以后执行 select * from temp where b = 22：

  • 执行 sql 语句时，会去找以后的字段是否建设了索引文件，没有建设则全表扫描（完结）
  • 依据以后字段依据二叉树的搜寻办法（遍历）索引构造找到对应的 key
  • 依据 key，则依据 value 的磁盘地址的文件指针去找到对应的数据文件

能够发现当咱们适当的应用索引能够疾速的进步咱们的查问效率！！！

为什么应用 B + 树作为 MySQL 底层构造

在理解“为什么应用 B + 树作为 MySQL 底层数据结构”的前提下，咱们须要学习一下对于树的数据结构的小前置知识点（这样能够帮咱们更好的了解数据结构之间劣势和劣势比照）：

二叉搜寻树

均衡二叉搜寻树（AVL 树）

B 树

红黑树

以上这些树结构，都有一个特点就是

  • 右节点元素值 > 其父亲节点元素值
  • 左节点元素值 < 其父亲节点元素值

插入：从根节点开始，依据节点进行遍历，依据节点进行比照，

  • 当 插入节点 > 以后节点的时候，则将 插入节点与以后节点的右节点比照
  • 当 插入节点 < 以后节点的时候，则将 插入节点与以后节点的左节点比照
  • 始终循环此步骤比照，直到没有节点进行比照，则插入实现

查问：从根节点开始，依据节点进行遍历，依据节点进行比照，

  • 当 查问节点 > 以后节点的时候，则将 查问节点与以后节点的右节点比照
  • 当 查问节点 < 以后节点的时候，则将 查问节点与以后节点的左节点比照
  • 始终循环此步骤比照，直到呈现 查问节点 = 以后节点，则进行或者曾经没有节点能够进行比照即完结

应用二叉搜寻树（毛病：单边增长）

依据 主键索引（id 自增）字段插入 ，应用二叉树会变成 线性链表 ，跟 数据库的表的遍历一样没区别，某些特定场景（单边增长）效率太低

应用均衡二叉搜寻树（AVL 树）（毛病：旋转次数多，保护均衡老本大）

  • 应用均衡二叉搜寻树，通过节点之间的旋转（每个节点的左右子树高度差不超过 1）解决了二叉搜寻树的单边增长问题。
  • 然而为了保护均衡，频繁的插入和删除时须要屡次旋转，旋转是十分耗时的，并且插入新节点时旋转的次数不能确定。
  • 因而适宜用于插入与删除次数比拟少，但查找多的状况。

应用红黑树（比照均衡叉树，缩小旋转次数，性能更优）

  • 应用红黑树（是均衡二叉搜寻树的增强版）能够解决二叉树的单边增长问题（例如：Jdk1.8 对 hahsmap 的链表优化为红黑树，不会导致单边增长过分）
  • 通过旋转，红黑树谋求大抵均衡（通过红黑节点的一些规定束缚）。在和均衡二叉搜寻树查找时间复杂度相差不大的状况下，保障每次插入最多 只用三次旋转 就能达到均衡。
  • 红黑树就义了局部平衡性以换取插入 / 删除操作时的大量的旋转操作，整体来说红黑树要优于均衡二叉搜寻树

  • 如果索引底层应用红黑树，红黑树的最大高度是 2 * log2（n+1）

    当一百万表数据的时候，红黑树的最大高度为 20 左右，也就是当咱们要查找的元素在叶子节点，就会达到最大的查问次数，这样查问的次数是特地久。

  • 如何让应用查找次数到 3 -5，使高度为 3 -5？

应用 B -Tree（B 树一个节点存储更多元素）

在 B -Tree 中，一个节点能够存储多个索引元素，想比照红黑树一个节点存储一个元素而言，树的高度更矮，能够缩小查问的次数。

应用 B +Tree（B-Tree 的加强版，存储元素更多）

比照 B -Tree 而言，B+Tree 则是它的增强版本，其非叶子节点不存储 data，只存储冗余的索引，这样子一个节点就能够放更多的索引。

  • 叶子节点：没有孩子节点的节点叫作叶子节点
  • 非叶子节点：跟叶子节点相同，有孩子节点的节点

叶子节点蕴含了所有索引字段和元素值，下面一层寄存两头叶子节点的元素（作为冗余）
B+Tree 多了指针叶子节点用指针链接，进步了区间拜访的性能。

为什么要冗余？

  • 为了非叶子节点只存储索引，叶子节点须要存储全副的元素值，那么就必须冗余。
  • 等同大小的节点如果只存储索引的话，不存储元素，能够存储更多的索引。

那么到这里有同学要问了，为什么不把所有节点索引以及数据全副存储到一个节点，这样不是更快吗？

  1. 在 MySQL 中一个节点的大小是有限度的
  2. 当咱们加载节点的时候，会先把节点内容全副加载到内存中去，而后在内存中进行比照要查找的值，如果一次性把全副节点放在一行，数据扫描加载须要很多的内存和工夫。

上面咱们来剖析一下：

# 查问 innodb 引擎一页的大小（一页就是一个节点）SHOW GLOBAL STATUS LIKE 'Innodb_page_size';

# 查问后果  1KB=1024Byte
16384Byte = 16KB

咱们对 B + 树（多叉均衡树）做以下假如：

  • 索引元素占用 bigint，8Byte
  • 空白中央指向下一个大节点的磁盘文件的地址指针，占 6Byte
  • data 假如占用为 1KB

非叶子节点存储一个索引（空白指针 + 索引）须要 14Byte(8Byte + 6Byte)
节点默认大小给了 16KB，16384Byte / 14Byte = 1170.2857，也就是一个非叶子节点能够存储 1170 个索引
叶子节点没有空白节点，data 数据和索引元素假如为 1KB，16KB / 1KB = 16  这棵树能够存储 16 个索引元素

依照这样计算的话，咱们依照树的高度为 3 来计算，那么一颗 B +Tree 能够存储 1170 _1170 _16 = 21902400 = 2100w 差不多。这样应用 B +Tree 来存储，当树高度为 3 的时候，就能够存储几千万行的索引元素啦！！！
因而当咱们有千万级别的表的时候，如果不建设索引可能要几十秒，建设所以可能就是几百毫秒。

数据如何加载？

因为数据库的索引是存储在磁盘上的，须要将该节点进行加载到内存，在进行遍历检索比拟。这样就称之为一次的磁盘加载，也就做磁盘 I /O。当咱们的磁盘 I / O 的次数越多，那么所须要耗费的工夫也就越大。

对于 myisam 和 innodb 引擎中实现 B + 树的存储原理

汇集索引：指的是数据和索引文件寄存在一起存储

非汇集索引：指的是数据和索引文件离开存储

MyISAM 存储引擎索引实现

  • 数据库文件的寄存（表构造，数据文件，索引文件）
  • 寄存在数据库文件夹的 data 目录下的数据库目录
  • 存储引擎为 MyISAM，frm 为表构造，MYD 数据文件，MYI 索引文件

MyISAM 引擎中的索引文件和数据文件是拆散的 (非汇集索引)
流程（当咱们发动一条 select *from temp where id = 49）：

  1. 先依据字段 id 判断是否是索引元素（也就是是否建设了索引）
  2. 建设了索引则依据值 49 去根节点去查找，根节点是常驻内存的，始终往下找
  3. 进行比对，找到 key=49 索引元素，对应的 data 寄存的是索引所在的那一行的磁盘文件地址的指针
  4. 拿到指针后，去到 myd 文件，疾速定位到这一行

以下为应用主键建设索引：

以下为应用非主键列建设索引：

InnoDB 存储引擎索引实现

  • 数据库文件的寄存（表构造，数据文件，索引文件）
  • 寄存在数据库文件夹的 data 目录下的数据库目录
  • 存储引擎为 innodb，frm 表构造，ibd 文件包含了数据文件和索引文件（表数据文件自身就是按 B +Tree 组织的一个索引构造文件）

InnoDB 引擎中的主键索引：索引文件和数据文件是在一起的(属于汇集索引)
InnoDB 引擎中的二级索引：索引文件和数据文件不是在一起的(属于非汇集索引，叶子节点存储的是主键值)

流程（当咱们发动一条 select *from temp where id = 49）：

  1. 先依据字段 id 判断是否是索引元素（也就是是否建设了索引）
  2. 建设了索引则依据值 49 去根节点去查找，根节点是常驻内存的，始终往下找
  3. 进行比对，找到 key=49 索引元素，其对应的存储了该行数据的所有内容

以下为应用主键建设索引（也称之为主键索引）：

以下为应用非主键列建设索引（也称之为二级索引）：

流程 1（当咱们发动一条 select * from temp where name = Alice）：

  1. 先依据字段 name 判断是否是索引元素（也就是是否建设了索引）
  2. 建设了索引则依据值 Alice 去根节点去查找，根节点是常驻内存的，始终往下找
  3. 进行比对，找到 key=Alice 索引元素，其对应的存储了该行数据的主键 id
  4. 依据主键 id，到主键索引去查问，则能够获取到该条数据的全副信息

通过二级索引的主键值，去主键索引查问对应的数据，这个操作叫做回表！！！

流程 2（当咱们发动一条 select id，name from temp where name = Alice）：

  1. 先依据字段 name 判断是否是索引元素（也就是是否建设了索引）
  2. 建设了索引则依据值 Alice 去根节点去查找，根节点是常驻内存的，始终往下找
  3. 进行比对，找到 key=Alice 索引元素，其对应的存储了该行数据的主键 id

须要查问的列信息，在二级索引里能找到，则不须要去主键索引查问回表，这个操作叫做索引笼罩！！！

发问 1: 为什么倡议 InnoDB 表必须建主键，并且举荐应用整型的自增主键？

  • innodb 优先应用用户自定义主键作为主键
  • 没有建设主键，则选取一个惟一列作为主键
  • 没有惟一列，会为表默认增加一个名为 row_id 的暗藏列作为主键。

不必整形主键，应用 uuid 字符串（随机流水号）

  • B+ 树进行比拟，整形进行比拟大小的时候运算更快更高效
  • uuid 字符串，字符串比大小，还要转成 asii 码，进行比拟
  • uuid 字符串的占用空间大，磁盘空间应用更大，整形小
  • uuid 字符串插入（不能保证数据有序性），如果算进去的值是比拟小的话，那么将往两头插入，且在一个满了一个节点 16kb 的状况下，这样就须要进行决裂，均衡，向上合并，导致高度变高，并且插入的时候也是须要去保护索引的。

发问 2: 为什么非主键索引构造（二级索引）叶子节点存储的是主键值？(一致性和节俭存储空间)

如果咱们不应用主键值来组织整张表的数据（主键索引），应用其余非主键列来组织整张表的数据
  • 当咱们一颗树有多个索引的时候，须要多个非主键列来保护
  • 其次咱们在插入二级索引，须要保护两颗 B + 树的数据
  • 在而后咱们必须非主键索引保护组织的表数据和二级索引都插入胜利，才算胜利
  • 如果主键来组织整张表的数据，咱们能够让主键索引插入胜利，在建设二级索引设置值

行格局

  • 咱们平时是以记录为单位来向表中插入数据的，这些记录在磁盘上的寄存形式也被称为行格局或者记录格局。
  • InnoDB 存储引擎设计了 4 种不同类型的行格局，别离是 Compact、Redundant、Dynamic 和 Compressed 行格局。
  • 而在 innodb 默认的行格局为 Dynamic（当然咱们能够在创立或批改表的语句中指定行格局：CREATE TABLE 表名 (列的信息) ROW_FORMAT= 行格局名称）。

数据溢出

1. 对于数据溢出：

指的是 存储的列的数据所占字节大小 > 该列数据类型所能存储的最大字节，导致一页寄存不了这条记录

2. 在 Compact 和 Redundant 行格局中:

  • 对于占用存储空间十分大的列，在记录的实在数据处只会存储该列的该列的
    前 768 个字节的数据，而后把残余的数据扩散存储在几个其余的页中.
  • 记录的实在数据处用 20 个字节存储指向这些页的地址。这个过程叫做溢出。
  • 存储超出 768 字节的那些页面也被称为溢出页。

3.Dynamic 和 Compressed 行格局:

  • 不会在记录的实在数据处存储字段实在数据的前 768 个字节
  • 而是把所有的字节都存储到其余页面中，只在记录的实在数据处存储其余页面的地址。

4. 为什么长度少于等于 768 字节，则溢出页并不会被应用：

  • 这个 768 是通过测试的最佳字节大小，应用溢出页会减少磁盘的 I / O 次数。
  • 因为数据溢出，当前页的行记录某列数据存储指针指向别的页进行了存储，这样会导致多些磁盘 I /O。

COMPACT 行格局

行格局的数据结构以及形容如下：

变长字段长度列表（记录可变的数据类型的实在长度）：

  • 在 msql 中有些数据类型须要存储多少的字节的数据是不确定的（例如 varchar，txt 等）。
  • 因为这些数据类型的内存空间是能够变动的，咱们须要在存储实在数据的时候把其存储的理论数据的占用的字节存起来。

NULL 值列表（应用二进制的形式治理 null 值，节俭内存空间）：

  • 表中的某些列可能存储 NULL 值，如果把这些 NULL 值都放到记录的实在数据中存储会很占中央。
  • 所以 Compact 行格局把这些值为 NULL 的列对立治理起来，存储到 NULL 值列表。
  • 每个容许存储 NULL 的列对应一个二进制位，二进制位的值为 1 时，代表该列的值为 NULL。二进制位的值为 0 时，代表该列的值不为 NULL。

Redundant 行格局

Redundant 行格局是 MySQL5.0 之前用的一种行格局。

Dynamic 和 Compressed 行格局

Dynamic 和 Compressed 行格局和 Compact 行格局挺像，只不过在解决行溢出数据时有所不同。Compressed 行格局和 Dynamic 不同的一点是，Compressed 行格局会采纳压缩算法对页面进行压缩，以节俭空间。

索引的外部架构（页）

InnoDB 是一个将表中的数据存储到磁盘上的存储引擎，所以即便关机后重启，咱们的数据还是存在的。而真正解决数据的过程是产生在内存中的，所以须要把磁盘中的数据加载到内存中，如果是解决写入或批改申请的话，还须要把内存中 的内容刷新到磁盘上。而咱们晓得读写磁盘的速度十分慢，和内存读写差了几个 数量级，所以当咱们想从表中获取某些记录时，InnoDB 存储引擎须要一条一条的把记录从磁盘上读出来么？

咱们晓得数据库的表记录是依照行来存储的，假如数据库的读取是依照行来读取的（读取一次为一次磁盘 I /O），这样效率非常低，所耗时间十分长。因为 MySQL 是高性能的，不可能这样形式思考去读取数据的。
因而 InnoDB 引擎采取的形式是：将数据划分为若干个页，以页作为磁盘和内存之间交互的根本单位，InnoDB 中页的大小个别为 16 KB。也就是在个别状况下，一次起码从磁盘中读取 16KB 的内容到内存中，一次起码把内存中的 16KB 内容刷新到磁盘中。

索引页的构造（B+ 树 -> 索引页）

索引页的形成如下图所示：

咱们本人存储的记录会依照咱们指定的行格局存储到 User Records 局部

以后记录数据插入：

  • 在一开始生成页的时候，其实并没有 User Records 这个局部。
  • 当插入一条记录，会从 Free Space 局部（尚未应用的存储空间）中申请一个记录大小的空间划分到 User Records 局部。
  • 当 Free Space 局部的空间全副被 User Records 局部代替掉之后，如果还有新的记录插入的话，就须要去申请新的页了。

以后记录被删除：

  • 会批改记录头信息中的 delete_mask 为 1（打一个删除标记），也就是说被删除的记录还在页中，还在实在的磁盘上。因为移除它们之后把其余的记录在磁盘上重新排列须要性能耗费以及调配空间也须要耗费工夫。
  • 所有被删除掉的记录都会组成一个垃圾链表，在这个链表中的记录占用的空间称之为所谓的可重用空间。
  • 之后如果有新记录插入到表中的话，可能把这些被删除的记录占用的存储空间笼罩掉。

页之间的关联（索引页 -> 索引页）

咱们晓得一个索引页存储多个记录，那么多个行记录如何进行关联的呢？
索引页之间通过上一个页、下一个页建设一个双向链表把许许多多的页就串联起来，而无需这些页在物理上真正间断。

索引页的数据关联（索引页 -> 行格局记录）

一个主键索引页 内部结构具体如下：

前缀概念：

分组：
索引页形成的局部中的 User Records（用户记录 -> 蕴含了多条记录）进行分组，进行分组可能更好的治理咱们的记录。每个分组的最初一条 记录的头信息中的 n_owned 字段 会存储该组一共有多少条记录。

槽：
在索引页形成局部中的 页面目录 外面蕴含了 多个槽

  • 第一个槽的地址偏移量指向 索引页形成局部中的的 infimum（最小记录，虚构行记录），且限度只能 1 条记录
  • 两头的槽的地址偏移量指向了 以后分组中的最大的主键的行记录，限度只能有 4 - 8 记录
  • 最初一个槽的地址偏移量指向了 索引页形成局部中的的 Supremum（最大记录，虚构行记录），限度只能有 1 - 8 条记录

之所以对不同的地位的槽进行了条数限度，是因为槽中的记录是单链表的模式，检索的时候须要通过指针去一条条遍历，如果一个槽的条数太多，那么会导致工夫耗费太长。所以限度了地位在两头的槽只能 4 -8，当槽中的数量为 4 - 8 条的时候，链表的查问遍历性能是最好的（想比照其余的数据结构的查问插入删除的老本保护而言）
（参考 hashmap 中的当链表长度大于 8，数组长度大于 64，须要转换成红黑树）。

一个数据页中查找指定主键值的记录的过程分为两步：

  • 通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最大的那条记录。
  • 通过记录的 next_record 属性遍历该槽所在的组中的各个记录。

上面咱们以 B + 树的角度来看看索引：

🎣

发问 1: 为什么抉择 B + 树作为索引？

  • 因而咱们的数据是存储在磁盘中的，每次进行数据的检索的时候，须要将数据加载到内存，而后进行解决检索数据，这样的操作为一次磁盘 I /O。
  • 磁盘 I / O 是十分耗时的。因而为了检索的速度，须要最大限度的缩小磁盘 I /O，缩小磁盘的数据加载到内存中。
  • 因为一个数据库的节点页的可存储的大小无限为 16KB（能够自行调整），在无限的大小存储下，B+ 树非叶子节点只存储索引元素，叶子节点存储数据，利用冗余索引的形式的来实现。这样能够使一个节点页存储最大限度的的索引，最大限度的缩小磁盘 I /O。

发问 2: myisam 和 innodb 引擎在实现 B + 树的存储的区别是什么？

  • myisam 属于非汇集索引，索引文件和数据文件离开

（myisam 索引文件和数据文件离开存储，查找两次，myi 索引文件 -> myd 数据文件）

  • innodb 的主键索引属于汇集索引，索引文件和数据文件在一起

    （叶子节点蕴含了残缺的数据记录，查找一次，ibd 数据索引文件，效率更高）

  • innodb 的二级索引属于非汇集索引，索引文件和数据文件离开

    （如果查问的数据都在二级索引则呈现索引笼罩，否则须要进行回表的操作）

发问 3: 为什么倡议 InnoDB 表必须建主键，并且举荐应用整型的自增主键？

  • 当咱们没有建设主键，则会依据咱们的惟一列去建设主键索引。

    如果都不满足，则会默认帮咱们增加一个暗藏列作为主键。在理论开发中，咱们应该本人去建设主键，这样就不须要 mysql 帮咱们去增加暗藏列。

  • 其次应用整形进行比拟大小更快更高效，如果应用 uuid 字符串比拟大小，还须要进行转码在比拟，且字符串占用的空间更大，字符串是无序性的，容易导致在曾经满的页进行插入，导致的树的决裂，均衡，向上合并，导致高度变高，须要工夫老本去进行一个树的均衡保护。

发问 4: innodb 索引页的外部的行记录数据是如何组织的以及页与页之间如何查找的？

innodb 索引页的外部的行记录数据是如何组织的：

  1. innodb 默认的行格局为 Dynamic，每一条行记录的格局蕴含了记录头的信息，记录头信息蕴含了 n_ownd(以后领有的记录数)，next_record（指向下一跳记录的绝对地位）。
  2. 在一个索引页中蕴含了 Page Directort（页面目录），User Records（用户记录），Infimum+Supremum（最小记录和最大记录）
  3. 在行记录中，会对行记录进行一个分组，依照主键的大小进行分组。依据页目录的每个槽位，进行标记记录最小最大记录，以及以后记录组的最大记录一一对应。
  4. 通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最大的那条记录。
  5. 通过记录的 next_record 属性遍历该槽所在的组中的各个记录。

页与页之间如何查找的：

  1. 索引页的形成蕴含了 File Header（文件头头部）记录了高低索引的前后指针。
  2. 索引页之间通过上一个页、下一个页建设一个双向链表把许许多多的页就串联起来。
  3. 不需需这些页在物理上真正间断，只是在逻辑上的间断。

对于此次的索引解说到此结束啦，下集咱们来讲讲如何优化索引。

本文由 mdnice 多平台公布

正文完
后端
发表至： 后端
2023-03-02
 0
关于后端:JDK和CGLIB动态代理实现AOP控制事务
关于后端:锁屏面试题百日百刷Spark篇十七
关于后端:662-二叉树最大宽度-简单-DFS-运用题
关于后端:159234

站内搜索

-「」