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

文章浏览时长约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=1024Byte16384Byte = 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多平台公布