关于面试:跳槽必看MySQL索引B树原理揭秘与索引优缺点分析

51次阅读

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

金三银四跳槽季，不晓得你筹备的怎么样了？

前段时间我分享了两篇文章，粉丝股东们纷纷表示 有用，有启发：，之前没看的话能够先看看：

程序员金三银四跳槽指南：工夫线 & 经典面试 16 问

这才动工没几天就收到喜报了，简历改了是真有用！

明天再给大家分享一下数据库索引的详解文章，这根本是必考的知识点。

一、索引介绍

1、索引定义

索引是存储引擎中，用于疾速找到记录的一种数据结构。索引可能帮忙存储引擎疾速获取数据，形象的说就是索引是数据的目录。

所谓的 存储引擎，艰深的来说就是如何存储数据、如何为存储的数据建设索引和如何更新、查问数据等 技术的实现办法。

MySQL存储引擎有 MyISAM、InnoDB、Memory，其中InnoDB 是在 MySQL 5.5 之后成为默认的存 储引擎。

在理论场景中，索引对于良好的性能起到十分要害的作用。或者在数据量小且负载较低时，索引的不失当应用可能对性能的影响可能不会太显著，然而当表中的数据量越来越大的时候，索引对性能的影响就愈发重要，不失当的索引会让性能急剧的降落。

2、索引的查找形式

在 MySQL 的InnoDB存储引擎中

若没有索引的状况下进行数据查问

a) 在一个数据页中查问

当表中的记录比拟少时，所有记录能够寄存到一个数据页中。当查问记录时，依据搜寻条件的不同查问分为两种状况：

  • 以 主键 为搜寻条件：在一个数据页内的记录会依据主键值的大小从小到大的程序组成一个单向链表。每个数据页都会为存储在它外面的记录生成一个页目录。通过主键查问某条记录能够 在页目录中应用二分法疾速定位到对应的槽，而后再遍历该槽对应分组的记录，即可疾速找到指定的记录。
  • 以 其余列 作为搜寻条件：对于非主键列的查找，因为没有为非主键列建设对应的目录页，即 未创立索引 。无奈用二分法疾速定位相应的槽，只能从Infimum 记录开始顺次遍历单向链表中的每条记录，而后比照每条记录是否合乎搜寻条件，即全表扫描，因而效率非常低。

b) 在多个数据页中查问

在很多状况下，表中寄存的记录是十分多的，须要查问到的数据可能散布在多个数据页中，在多个页中查找记录能够分为两个步骤：

  • 定位到记录所在的页
  • 从所在的页内查找相应的记录

在没有索引的状况下，无论是依据主键列还是其余列的值查找，都不能疾速定位到记录所在的页，因而只能从第一页沿着双向链表始终往下找，因此十分耗时。

若存在索引的状况下进行数据查问

在创立索引的状况下，每个数据页都会为存储在它外面的记录生成一个目录项，在通过索引查找某条记录时能够在页目录中应用二分法疾速定位到对应的槽，而后再遍历该槽对应分组中的记录，疾速找到指定的记录，确定记录后，即可向下寻找以后记录对应的下一个页节点，直到寻找到存在指标记录的叶子结点。

二、索引分类

1、按数据结构分类

Hash 索引

哈希表是一种以 键 - 值（key-value）存储数据的构造，输出待查找的键，即key，就能够找到其对应的值，即value。

哈希的思路很简略，把值放在数组里，用一个哈希函数把 key 换算成一个确定的地位，而后把 value 放在数组的这个地位。

不可避免地，多个 key 值通过哈希函数的换算，会呈现同一个值的状况，即哈希碰撞，解决这种状况的一种办法是，拉出一个链表。

然而，在哈希表中，数据的存储不是按程序寄存的，所以哈希索引做区间查问的速度是很慢的。

所以，哈希表这种构造 实用于只有等值查问的场景 ，比方Memcached 及其他一些 NoSQL 引擎。

有序数组

有序数组在 等值查问和范畴查问 场景中的性能就都十分优良。

在查找数据方面，有序数组能够 通过二分查找的形式 疾速找到，工夫复杂度是 O(log(N))。

同样，有序数组的索引构造 反对范畴查问 ，通过 二分法 找到须要查找的范畴的首元素，而后向后遍历，直到找到第一个不满足条件的元素为止。

如果仅仅看查问效率，有序数组就是最好的数据结构了。然而，在须要更新数据的时候就麻烦了，往两头插入一个记录就必须得移动前面所有的记录，老本太高。

所以，有序数组索引个别实用于动态存储引擎。

B+ 树（InnoDB 索引构造）

在 MySQL 5.5 之后，InnoDB成为默认的 MySQL 存储引擎，B+Tree索引类型也是 MySQL 存储引擎采纳最多的索引类型。

在 InnoDB 数据页中，各个数据页能够组成一个 双向链表，而每个数据页中的记录会依照主键值从小到大的程序组成一个单向链表。

在介绍 B+ 树 时，咱们以主键索引为例，来看看 InnoDB 是如何构建主键索引的B+ 树。其余字段所建设的索引与主键索引类似，只是将主键字段替换成指定的索引字段来构建B+ 树。

主键策略

在创立表时，InnoDB存储引擎会依据不同的场景抉择不同的列作为主键索引：

  • 如果有指定主键，默认会应用主键作为聚簇索引的索引键
  • 如果没有指定主键，则抉择第一个不蕴含 NULL 值的惟一列作为聚簇索引的索引键
  • 在下面两个都没有的状况下，InnoDB将主动生成一个 隐式自增 id列作为聚簇索引的索引键

除主键索引外，其它索引都属于 辅助索引（Secondary Index），也被称为 二级索引 或非聚簇索引 。创立的主键索引和二级索引默认应用的是B+Tree 索引。

建设 B + 树索引的条件

条件一：下一个数据页中记录的主键值必须大于上一个数据页中记录的主键值

咱们晓得，在 MySQL 中，新调配的数据页编号可能并不是间断的，即这些数据页在磁盘上并非紧挨着存储。须要通过保护上一下和下一页的编号，因而，在 InnoDB 中，每个数据页组成了一个双向链表 来保护每个数据页之间的高低关系。

为什么构建 B + 树须要满足条件一呢？

起因在于为了 进步范畴查问的效率 ，B+ 树 要求 叶子节点中的数据记录依照主键值的程序进行排列。

当进行范畴查问时，如果叶子节点中的数据记录不依照主键值的顺序排列，就会减少查找的复杂度。如果下一个数据页中记录的主键值小于上一个数据页中记录的主键值，那么在进行范畴查问时就须要在不同的叶子节点之间来回跳转，这样会减少 IO 操作次数和查问工夫。

因而，为了保障范畴查问的效率，B+ 树要求叶子节点中记录的主键值必须依照顺序排列，即下一个数据页中记录的主键值必须大于上一个数据页中记录的主键值。这样能够确保在进行范畴查问时能够顺利地依照主键值的程序进行遍历，进步查问效率，同样 MySQL 中的预加载页性能也能够缩小 IO 操作次数。

在 InnoDB 中，在对页中的记录进行增删改操作时，必须通过一些记录挪动的操作来始终保障：下一个数据页中用户的记录的主键值必须大于上一个页中用户记录的主键值 ，则这个过程也成为 页决裂操作，即在一个数据页中插入记录，而该数据页在插入之前曾经满了，则须要申请一个新的数据页，而后移动局部数据过来。

条件二：须要给所有的数据页建设一个目录页

因为每个数据页的编号可能并不间断，因而须要为这些数据页建设一个目录。

比方当咱们看一本书的时候，书的目录能够帮忙咱们疾速定位到咱们想看的内容，而目录题目对应的页号能够比作每个数据页的页号，通过书的目录咱们能够疾速定位到咱们想看的内容，同样的情理，通过为数据页建设目录，在目录中存储数据页的编号，即可通过目录疾速定位到相应的数据页。

目录页能够包含两个内容：

  • 数据页的记录中最小的主键值，用 key 示意
  • 数据页页编号，用 page_no 示意

为了不便阐明，咱们能够定义一个数据表：

CREATE TABLE `index_demo` (
`a` int NOT NULL,
`b` int DEFAULT NULL,
`c` char(1) DEFAULT NULL,
PRIMARY KEY (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci ROW_FORMAT=COMPACT;

上述表定义中，应用了 COMPACT 行格局来存储数据，COMPACT行格局的简化存储如下：

咱们假如每个数据页最多只能寄存 2 条记录（理论一个数据页十分大，能够寄存许多的记录）

当为数据页编制其对应的目录页时，如下图所示：

咱们以 页 10为例，为其编制的目录项为目录项 1，该目录项蕴含了该页的 页号 10以及该页的数据记录中 主键值最小的值 1 。当咱们把这些目录项在物理存储器中间断存储，就能够实现依据主键疾速查找某条记录的性能了。举个例子，当咱们想查问主键值为 100 的记录时，具体的查问过程如下：

  • 通过目录项，依据二分查找疾速定位到主键值为 100 的记录在目录项 3 中（因为 12 < 100 < 209），其对应的数据页页号为 9
  • 再根据上述聊到的在单个页中查问记录的形式，即可在页 9 中查问到主键值为 100 的记录。
B+ 树的构造

上述咱们聊到构建 B + 树的条件，其外围是 通过应用二分法的形式疾速定位到具体的目录项，再通过目录项疾速定位到咱们所须要的数据页。

咱们在聊到给数据页记录建设其对应的目录项时，数据页内的每条记录都会有 record_type 字段，它的各个取值代表意思如下：

  • 0：一般数据记录，即咱们插入的数据记录
  • 2：Infimum记录，在 B + 树索引中，Infimum记录位于整个索引的最右边，用于示意没有更小值的状况。
  • 3：Supermun记录，在 B + 树索引中，Supremum记录位于整个索引的最左边，用于示意没有更大值的状况。

你可能会好奇，取值有 0、2、3，那取值1 是什么意思呢？

咱们留神到，在目录项中存储两个字段，别离是最小主键值以及对应的页号，事实上，寄存目录项的页与理论存放数据的数据页并无区别 ，目录项中的两个字段（主键值以及页号）齐全能够看作是存储的理论数据，因而，目录项中记录能够称作为目录项记录，即目录页，那 InnoDB 是如何区别理论数据记录与目录页记录呢，答案就是record_type 字段的取值为 1 来示意目录页记录。

  • 0：一般数据记录，即数据页记录
  • 1: 目录项记录，即目录页记录
  • 2：Infimum记录
  • 3：Supermun记录

通过上图能够看到，咱们应用页 30 来寄存目录页记录，目录页记录与数据页记录的不同点在于：

  • 目录页记录的record_type=1，而数据页记录的record_type=0
  • 目录页记录只蕴含主键值 (索引值) 和页号，而数据页记录则能够由用户来自定义，能够蕴含很多列。

除此之外，两者并无理论的区别，在目录页中，同样能够通过二分法来疾速定位到目录页记录，再通过目录页记录向下查问到其对应的数据页。

当然，当目录页中的记录过多，一个目录页难以包容时，咱们能够再多调配一个存储目录项的页即可。当同层存在多个目录项时，咱们则能够向上再调配更高一级的目录项，即多级目录。

咱们能够察看到，这样多级的目录，不就像一颗树的数据结构了呢？其实，这就是 InnoDB 的B+ 树 构造。

B+ 树的特点

无论是寄存理论数据的数据页，还是寄存目录项记录的目录页，都能够把它们放到 B+ 树 当中，这些页称为 B+ 树 的节点。

其中，寄存咱们插入的理论数据的记录寄存在 B+ 树 的最底层节点，这些节点称为叶子节点。其余非叶子节点则用来寄存目录项记录。其中 B+ 树 最上层的节点称为根节点。

B+ 树 的叶子节点之间是用「双向链表」进行连贯，这样的益处是既能向右遍历，也能向左遍历。

2、按物理存储分类

聚簇索引（主键索引）

聚簇索引，又能够称为主键索引，在创立表时，InnoDB 会默认为主键创立一棵 B + 树的主键索引。

聚簇索引的特点 在于：

  • 应用记录的主键值大小来对记录和页进行排序。
  • 页（包含叶子节点和非叶子节点）内的记录依照主键值的大小进行排序组成单向链表。页内的记录会被划分为若干的组，每个组中主键值最大的记录在页内的偏移量会被当做该组的槽放在页目录中，以便后续能够通过二分法来查找定位到须要查找的记录。
  • 寄存理论数据的各个数据页（叶子节点）同样也依据主键大小排成双向链表。
  • 寄存目录数据的各个目录页（非叶子节点）能够分为 B + 树的多个层级，在同一层级的目录页页依据也中存储的主键值大小来排序成一个双向链表。
  • B+ 树的叶子节点寄存的是残缺的数据记录，即保留了该记录的所有列的值。

蕴含以上两个特点的 B + 树称为聚簇索引。

非聚簇索引（二级索引）

不同于聚簇索引，非聚簇索引存储的并不是残缺的数据，非聚簇索引的叶子节点寄存的是指定的索引列 + 主键值。非聚簇索引的目录页存储的记录中不再是主键 + 页号的搭配，而是指定的索引列 + 页号。

以非主键列的大小为排序规定而建设的 B + 树须要执行回表操作才能够定位到残缺的用户记录，这种 B + 树也称为二级索引或辅助索引。

同样非聚簇索引的 B + 树的叶子节点也会依照索引列排序并组成双向链表，同一层级的目录页也会依据索引列的大小来排序组成双向链表。

回表

聚簇索引和非聚簇索引的查问有什么区别？

当应用二级索引进行查问定位到符合条件的记录时，当索引中并未存储咱们须要查问的字段时（非聚簇索引值的叶子节点只存储主键值以及指定索引值，可能存在须要查问的字段并未存储在索引 B + 树中），须要依据二级索引中存储的主键值，回表到主键索引查问到对应的字段才可能返回。

依据该记录中的主键信息回到聚簇索引中查找到残缺的用户记录。通过携带主键信息到聚簇索引中从新定位残缺的用户记录的过程也成为 回表。

在查问时，回表是有代价的 ，咱们晓得，在应用二级索引进行 范畴查问 的时候，二级索引对应的主键值的大小是毫无法则的，每读取一条二级索引记录，就须要依据该二级索引记录的主键值到聚簇索引中执行回表操作，如果对应的聚簇索引记录所在的页面不在内存中，就须要将该页面从磁盘加载到内存中因为要读取很多主键值并不间断的聚簇索引记录，而这些聚簇索引记录散布在不同的数据页中，这些数据页的页号也毫无法则，因而会造成大量的随机 I /O。

须要执行回表操作的记录越多，应用二级索引进行查问的性能就越低，因而在某些查问场景下，MySQL 优化器宁愿应用全表扫描也不应用二级索引，而 抉择全表扫描，还是二级索引 + 回表，这就是查问优化器的工作了。

查问优化器会当时针对表中的记录计算一些统计数据，再利用这些统计数据或者拜访表中的大量记录来计算回表操作的记录数，如果须要执行回表操作的记录数越多，就越偏向于应用全表扫描，反之则偏向于应用二级索引 + 回表。

既然回表有肯定的代价，那 为什么还须要进行回表呢？ 在创立索引时间接就残缺的数据记录放入索引的叶子节点不就好了么？

如果残缺的数据放入到每个索引建设的 B + 树的叶子节点中的确能够防止回表，然而取而代之的是须要更多的存储空间，太占中央，相当于每建设一棵 B + 树都须要将所有的残缺数据复制一遍。

3、按字段个性分类

主键索引

主键索引，即聚簇索引，建设在主键字段上的索引，通常在创立表的时候一起创立，一张表最多只有一个主键索引，索引列的值不容许有空值。

在创立表时，创立主键索引的形式如下：

CREATE TABLE table_name (
...
PRIMARY KEY (index_column_1) USING BTREE
);

惟一索引

惟一索引建设在 UNIQUE 字段上的索引，一张表能够有多个惟一索引，索引列的值必须惟一，然而容许有空值。

在创立表时，创立惟一索引的形式如下：

CREATE TABLE table_name (
....
UNIQUE KEY(index_column_1,index_column_2,...)
);

建表后，如果要创立惟一索引，能够应用这面这条命令：

CREATE UNIQUE INDEX index_name ON table_name(index_column_1,index_column_2,...);

一般索引

一般索引就是建设在一般字段上的索引，既不要求字段为主键，也不要求字段为UNIQUE。

在创立表时，创立一般索引的形式如下：

CREATE TABLE table_name (
....
INDEX(index_column_1,index_column_2,...)
);

建表后，如果要创立一般索引，能够应用这面这条命令：

CREATE INDEX index_name ON table_name(index_column_1,index_column_2,...);

前缀索引

前缀索引是指对字符类型字段的前几个字符建设的索引，而不是在整个字段上建设的索引。前缀索引能够建设在字段类型为 char、varchar、binary、varbinary 的列上。

应用前缀索引的目标是为了缩小索引占用的存储空间，晋升查问效率。

CREATE TABLE table_name(
....
INDEX(column_name(length))
);

建表后，如果要创立前缀索引，能够应用这面这条命令：

CREATE INDEX index_name ON table_name(column_name(length));

4、按字段个数分类

单列索引

当创立索引时，指定某一个字段作为索引列，建设在单列上的索引称为单列索引，比方主键索引。

联结索引

联结索引顾名思义，即指定多个字段列来作为索引列，同时以多个列的大小作为排序规定，即同时为多个列建设索引。

例如建设联结索引(a,b)，则在创立的 B + 树中，记录的排序形式为：

  • 先将各个记录和页依照 a 列进行排序
  • 在记录的 a 列雷同的状况下，再采纳 b 列进行排序

在联结索引 (a,b) 的 B + 树中，存储的内容为：

  • 非叶子节点中，每条目录项记录都有 a 列、b 列、页号 3 个局部组成。各条记录先依照 a 列的值进行排序，如果记录的 a 列雷同，则依照 b 列的值进行排序
  • 叶子节点中，数据页记录由 a 列、b 列和主键列三局部组成；

应用联结索引时，存在最左匹配准则，即依照最左优先的形式进行索引的匹配。

举个例子：

当咱们创立 联结索引（name, age）时，如果你要查的是所有名字第一个字是 "张" 的人，你的 SQL 语句的条件是where name like '张 %'。这时这条 SQL 可能用上这个联结索引。

从上述的例子能够看出，在对 name 字段进行单列条件查问时，同样可能应用上该联结索引，即 联结索引（name, age）能够等效于 单列索引（name）。

因而，在建设联结索引的时候，如何安顿索引内的字段程序呢？

评估规范是索引的复用能力。如果通过调整程序，能够少保护一个索引，那么这个程序往往就是须要优先思考采纳的。例如上述的例子，通过 联结索引（name，age）的程序，能够让咱们少保护一个 单列索引（name）。当然age。

三、索引的优缺点

在理解了 B + 树的索引构造后，咱们晓得失当的索引应用能够为咱们带来极大的查问效率，进步性能。然而索引也并非没有毛病，理解好索引的优缺点，抉择应用索引时，须要综合思考索引的长处和毛病，能力让咱们在理论应用索引的过程中得心应手。

1、长处

  • 进步数据检索的效率，升高数据库的 I / O 老本，将随机 I / O 转变为程序 I /O，这是创立索引最次要的起因；
  • 通过创立惟一索引，能够保障数据库表中每一行数据的唯一性；
  • 因为索引中记录的存储程序，在应用分组和排序子句进行数据查问时，能够显著缩小查问中分组和排序的工夫，即帮忙服务器防止排序和长期表，升高了 CPU 的耗费。
  • 能够减速表和表之间的连贯，即对于有依赖关系的子表和父表联结查问时，能够进步多表查问的速度。

2、毛病

创立索引和保护索引要消耗工夫，并且随着数据量的减少，所消耗的工夫也会减少。

  • 索引须要占磁盘空间

每个索引在创立后，须要占肯定的物理空间存储在磁盘上，因为每建设一个索引，都要为它建设一棵 B + 树。每一棵 B + 树的每一个节点都是一个数据页。

一个数据页默认占用 16KB 的存储空间，而一棵很大的 B + 树由许多数据页组成，这将会占用很大的一片存储空间。

如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。

  • 尽管索引大大提高了查问速度，同时却会升高更新表的速度

当对表中的数据进行减少、删除和批改的时候，索引也要动静地保护，即都须要批改各个 B + 树索引，这样就升高了数据的保护速度。

增删改操作可能会对节点和记录的排序造成毁坏，所以存储引擎须要额定的工夫进行页面决裂、页面回收等操作，以保护节点和记录的排序。

  • 影响优化器执行效率

在执行查问语句前，首先要生成一个执行打算。

个别状况下，一条查问语句在执行过程中最多应用一个二级索引，在生成执行打算时须要计算应用不同索引执行查问时所需的老本，最初选取老本最低的那个索引执行查问，如果此时建了太多的索引，可能会导致老本剖析过程耗时太多，从而影响查问语句的执行性能。

四、索引应用场景

索引最大的益处是进步查问速度，然而索引使用不当则会呈现上述形容的毛病所带来的影响。因而，索引不是万能钥匙，它也是依据场景来应用的。

那么在什么状况下，咱们该应用索引呢？

1、实用索引的场景

  • 字段须要唯一性限度

当业务中某个字段须要唯一性限度时，除了在业务逻辑层面校验，最初一道防线则是通过惟一索引来限度字段惟一。

  • 常常用于 WHERE 查问条件的字段

对常常用于 WHERE 查问条件的字段建设索引，可能进步整个表的查问速度，尤其是在数据量大的状况下，创立索引就能够大幅晋升数据查问的效率。

  • 常常用于 GROUP BY 和ORDER BY的字段

对于常常用于 GROUP BY 和ORDER BY的字段，建设索引，利用索引其按索引字段值顺序存储数据的个性，缩小排序与长期表带来的损耗。

  • 对 DISTINCT 字段创立索引

有时候须要对某个字段进行去重，应用DISTINCT，那么对这个字段创立索引，也会晋升查问效率。因为当去重字段创立了索引后是依照程序递增的，所以在去重的时候会快很多。

  • 在多个字段都要创立索引的状况下，联结索引优于单值索引

2、不实用索引的场景

  • WHERE条件、GROUP BY条件、ORDER BY条件中用不到的字段

索引的价值是疾速定位，如果起不到定位的字段通常是不须要创立索引的，因为索引是会占用物理空间的。

  • 表数据太少的时候，能够思考不须要创立索引
  • 常常更新的字段不必创立索引

常常更新的字段不必创立索引，比方不要用户余额建设索引，因为索引字段频繁批改，因为要保护 B+Tree 的有序性，那么就须要频繁的重建索引，这个过程是会影响数据库性能的。

本文来自 Go 待业训练营 小韬同学的投稿。

又出问题啦

咱们又出问题啦！大厂 Offer 集锦！遥遥领先！

这些敌人赢麻了！

这是一个专一程序员升职加薪の常识星球

答疑解惑

须要「简历优化」、「就业辅导」、「职业规划」的敌人能够分割我。

加我微信：wangzhongyang1993

我的文章均首发在同名公众号：王中阳 Go，欢送大家关注

正文完
面试
发表至： 面试
2024-02-29
 0
关于面试:协程面试题聊聊Job和SupervisorJob的区别
关于面试:18年毕业历经3年到现在的快手架构师聊聊我的java后端学习之路
关于面试:字节跳动面试官你有份offer待领取
关于面试:来自小姐姐的灵魂拷问位运算是什么