【MySQL】 B+树索引

Metadata

title: 【MySQL】 B+树索引
date: 2022-12-20 16:12
tags:
  - 行动阶段/完成
  - 主题场景/数据存储
  - 笔记空间/KnowladgeSpace/ProgramSpace/BasicsSpace
  - 细化主题/数据存储/MySQL
categories:
  - 数据存储
keywords:
  - 数据存储
description: 【MySQL】 B+树索引

概述

  1. InnoDB中的索引方案：
    • 使用页作为存储单位。
    • 目录项记录存储目录项的页，具有不同的record_type和列。
    • 用户记录存放在B+树的最底层节点。
    • 聚簇索引：主键值搜索时有效，叶子节点存储完整的用户记录。
    • 二级索引：通过非主键列搜索，需要在聚簇索引中查找完整记录。
    • 联合索引：以多个列的大小作为排序规则建立索引。
  2. InnoDB的B+树索引注意事项：
    • 根页面不移动。
    • 内节点中目录项记录的唯一性。
    • 页面最少存储2条记录。
  3. 索引的使用
  4. B+ 树索引在空间和时间上都有代价，所以没事儿别瞎建索引。
  5. B+ 树索引适用于下边这些情况：
    • 全值匹配
    • 匹配左边的列
    • 匹配范围值
    • 精确匹配某一列并范围匹配另外一列
    • 用于排序
    • 用于分组
  6. 在使用索引时需要注意下边这些事项：
    • 只为用于搜索、排序或分组的列创建索引
    • 为列的基数大的列创建索引
    • 索引列的类型尽量小
    • 可以只对字符串值的前缀建立索引
    • 只有索引列在比较表达式中单独出现才可以适用索引
    • 为了尽可能少的让聚簇索引发生页面分裂和记录移位的情况，建议让主键拥有AUTO_INCREMENT 属性。
    • 定位并删除表中的重复和冗余索引
    • 尽量使用覆盖索引进行查询，避免回表带来的性能损耗。

没有索引的查找

在一个页中的查找

  • 以主键为搜索条件
    可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
  • 以其他列作为搜索条件
    只能从最小记录开始依次遍历单链表中的每条记录

在很多页中查找

分为两个步骤

  1. 定位到记录所在的页。
  2. 从所在的页内中查找相应的记录。

由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚唠叨过的查找方式去查找指定的记录

索引

index_demo 举例

  • record_type ：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、2 表示最小记录、3 表示最大记录、1 我们还没用过，等会再说～
  • next_record ：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，为了方便大家理解，我们都会用箭头来表明下一条记录是谁。
  • 各个列的值：这里只记录在index_demo 表中的三个列，分别是c1 、c2 和c3 。
  • 其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

一个简单的索引方案

新分配的数据页编号可能并不是连续的，也就是说我们使用的这些页在存储空间里可能并不挨着

通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程我们也可以称为页分裂。

InnoDB中的索引方案

InnoDB 是使用页来作为管理存储空间的基本单位，也就是最多能保证16KB 的连续存储空间

复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录

  • 目录项记录和普通的用户记录的不同点：
  • 目录项记录的record_type 值是1，而普通用户记录的record_type 值是0。
  • 目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有InnoDB 自己添加的隐藏列。
  • 还记得我们之前在唠叨记录头信息的时候说过一个叫min_rec_mask 的属性么，只有在存储目录项记录的页中的主键值最小的目录项记录的min_rec_mask 值为1 ，其他别的记录的min_rec_mask 值都是0 。

实际用户记录其实都存放在B+树的最底层的节点上
非叶子节点存储目录项

聚簇索引

只能在搜索条件是主键值时才能发挥作用

B+ 树本身就是一个目录，或者说本身就是一个索引。它有两个特点：

  1. 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义
  • 页内的记录是按照主键的大小顺序排成一个单向链表。
  • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
  • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
  1. B+ 树的叶子节点存储的是完整的用户记录。

把具有这两种特性的B+ 树称为聚簇索引, 所有完整的用户记录都存放在这个聚簇索引的叶子节点处。

InnoDB 存储引擎会自动的为我们创建聚簇索引，
在InnoDB 存储引擎中， 聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

二级索引

这个B+ 树与上边介绍的聚簇索引有几处不同

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

如果我们现在想通过c2 列的值查找某些记录的话就可以使用我们刚刚建好的这个B+ 树了。

  1. 确定目录项记录页
  • 根据根页面，也就是页44 ，可以快速定位到目录项记录所在的页为页42 （因为2 < 4 < 9 ）。
  1. 通过目录项记录页确定用户记录真实所在的页。
  • 在页42 中可以快速定位到实际存储用户记录的页，但是由于c2 列并没有唯一性约束，所以c2 列值为4 的记录可能分布在多个数据页中，又因为2 < 4 ≤ 4 ，所以确定实际存储用户记录的页在页34 和页35 中。
  1. 在真实存储用户记录的页中定位到具体的记录。
  • 到页34 和页35 中定位到具体的记录。
  1. 但是这个B+ 树的叶子节点中的记录只存储了c2 和c1 （也就是主键）两个列，所以我们必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。

联合索引

同时以多个列的大小作为排序规则，也就是同时为多个列建立索引

  • 先把各个记录和页按照c2 列进行排序。
  • 在记录的c2 列相同的情况下，采用c3 列进行排序

  • 每条目录项记录都由c2 、c3 、页号这三个部分组成，各条记录先按照c2 列的值进行排序，如果记录的c2 列相同，则按照c3 列的值进行排序。
  • B+ 树叶子节点处的用户记录由c2 、c3 和主键c1 列组成。

以c2和c3列的大小为排序规则建立的B+树称为联合索引，本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的，，不同点如下

  • 建立联合索引只会建立如上图一样的1棵B+ 树。
  • 为c2和c3列分别建立索引会分别以c2 和c3 列的大小为排序规则建立2棵B+ 树。

InnoDB的B+树索引的注意事项

  • 根页面万年不动窝

一个B+树索引的根节点自诞生之日起，便不会再移动

  • 内节点中目录项记录的唯一性

B+ 树索引的内节点中目录项记录的内容是索引列 + 页号的搭配

为了让新插入记录能找到自己在那个页里，我们需要保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。

对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的

  • 索引列的值

  • 主键值

  • 页号

  • 一个页面最少存储2条记录

MyISAM中的索引方案简单介绍

MyISAM 的索引方案虽然也使用树形结构，但是却将索引和数据分开存储：

  • 将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件。这个文件并不划分为若干个数据页，有多少记录就往这个文件中塞多少记录就成了。我们可以通过行号而快速访问到一条记录。
  • 使用MyISAM 存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中。 MyISAM 会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 行号的组合。也就是先通过索引找到对应的行号，再通过行号去找对应的记录！ MyISAM 中建立的索引相当于全部都是二级索引！

B+树索引的使用

  • 每个索引都对应一棵B+ 树， B+ 树分为好多层，最下边一层是叶子节点，其余的是内节点。所有用户记录都存储在B+ 树的叶子节点，所有目录项记录都存储在内节点。
  • InnoDB 存储引擎会自动为主键（如果没有它会自动帮我们添加）建立聚簇索引，聚簇索引的叶子节点包含完整的用户记录。
  • 我们可以为自己感兴趣的列建立二级索引， 二级索引的叶子节点包含的用户记录由索引列 + 主键组成，所以如果想通过二级索引来查找完整的用户记录的话，需要通过回表操作，也就是在通过二级索引找到主键值之后再到聚簇索引中查找完整的用户记录。
  • B+ 树中每层节点都是按照索引列值从小到大的顺序排序而组成了双向链表，而且每个页内的记录（不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单链表。如果是联合索引的话，则页面和记录先按照联合索引前边的列排序，如果该列值相同，再按照联合索引后边的列排序。
  • 通过索引查找记录是从B+ 树的根节点开始，一层一层向下搜索。由于每个页面都按照索引列的值建立了Page Directory （页目录），所以在这些页面中的查找非常快。

索引的代价

空间上的代价

每一棵B+ 树的每一个节点都是一个数据页，一个页默认会占用16KB 的存储空间，一棵很大的B+ 树由许多数据页组成，那可是很大的一片存储空间

时间上的代价

每次对表中的数据进行增、删、改操作时，都需要去修改各个B+ 树索引

B+树索引适用的条件

从图中可以看出，这个idx_name_birthday_phone_number 索引对应的B+ 树中页面和记录的排序方式就是这样的：

  • 先按照name 列的值进行排序。
  • 如果name 列的值相同，则按照birthday 列的值进行排序。
  • 如果birthday 列的值也相同，则按照phone_number 的值进行排序。

因为只要页面和记录是排好序的，我们就可以通过二分法来快速定位查找。

全值匹配

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27' AND phone_number = '15123983239';
  • 因为B+ 树的数据页和记录先是按照name 列的值进行排序的，所以先可以很快定位name 列的值是Ashburn的记录位置。
  • 在name 列相同的记录里又是按照birthday 列的值进行排序的，所以在name 列的值是Ashburn 的记录里又可以快速定位birthday 列的值是’1990-09-27’ 的记录。
  • 如果很不幸， name 和birthday 列的值都是相同的，那记录是按照phone_number 列的值排序的，所以联合索引中的三个列都可能被用到。

WHERE 子句中的几个搜索条件的顺序对查询结果有啥影响么？

查询优化器

分析这些搜索条件并且按照可以使用的索引中列的顺序来决定先使用哪个搜索条件，后使用哪个搜索条件。

匹配左边的列

下边的语句就用不到这个B+ 树索引

SELECT * FROM person_info WHERE birthday = '1990-09-27';

B+ 树的数据页和记录先是按照name 列的值排序的，在name 列的值相同的情况下才使用birthday 列进行排序，也就是说name 列的值不同的记录中birthday 的值可能是无序的。

如果我们想使用联合索引中尽可能多的列，搜索条件中的各个列必须是联合索引中从最左边连续的列

匹配列前缀

一个排好序的字符串列其实有这样的特点：

  • 先按照字符串的第一个字符进行排序。
  • 如果第一个字符相同再按照第二个字符进行排序。
  • 如果第二个字符相同再按照第三个字符进行排序，依此类推。

匹配范围值

所有记录都是按照索引列的值从小到大的顺序排好序的

举例

SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';
  1. 找到name 值为Asa 的记录。
  2. 找到name 值为Barlow 的记录。
  3. 哦啦，由于所有记录都是由链表连起来的（记录之间用单链表，数据页之间用双链表），所以他们之间的记录都可以很容易的取出来喽～
  4. 找到这些记录的主键值，再到聚簇索引中回表查找完整的记录。

如果对多个列同时进行范围查找的话，只有对索引最左边的那个列进行范围查找的时候才能用到B+ 树索引

精确匹配某一列并范围匹配另外一列

对于同一个联合索引来说，虽然对多个列都进行范围查找时只能用到最左边那个索引列，但是如果左边的列是精确查找，则右边的列可以进行范围查找

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday > '1980-01-01' AND birthday < '2000-12-31' AND phone_number > '15100000000';

这个查询的条件可以分为3个部分：

  1. name = ‘Ashburn’ ，对name 列进行精确查找，当然可以使用B+ 树索引了。
  2. birthday > ‘1980-01-01’ AND birthday < ‘2000-12-31’ ，由于name 列是精确查找，所以通过name = ‘Ashburn’ 条件查找后得到的结果的name 值都是相同的，它们会再按照birthday 的值进行排序。所以此时对birthday 列进行范围查找是可以用到B+ 树索引的。
  3. phone_number > ‘15100000000’ ，通过birthday 的范围查找的记录的birthday 的值可能不同，所以这个条件无法再利用B+ 树索引了，只能遍历上一步查询得到的记录。

用于排序

使用联合索引进行排序注意事项

ORDER BY 的子句后边的列的顺序也必须按照索引列的顺序给出, 否则索引失效

不可以使用索引进行排序的几种情况

ASC、DESC混用

WHERE子句中出现非排序使用到的索引列

排序列包含非同一个索引的列

排序列使用了复杂的表达式

用于分组

分组列的顺序也需要和索引列的顺序一致，也可以只使用索引列中左边的列进行分组

回表的代价

在使用idx_name_birthday_phone_number 索引进行查询时大致可以分为这两个步骤

  1. 从索引idx_name_birthday_phone_number 对应的B+ 树中取出name 值在Asa ～ Barlow 之间的用户记录。
  2. 由于索引idx_name_birthday_phone_number 对应的B+ 树用户记录中只包含name 、birthday 、phone_number 、id 这4个字段，而查询列表是* ，意味着要查询表中所有字段，也就是还要包括country字段。这时需要把从上一步中获取到的每一条记录的id 字段都到聚簇索引对应的B+ 树中找到完整的用户记录，也就是我们通常所说的回表，然后把完整的用户记录返回给查询用户。

需要回表的记录越多，使用二级索引的性能就越低

覆盖索引

最好在查询列表里只包含索引列

我们很不鼓励用* 号作为查询列表，最好把我们需要查询的列依次标明。

如何挑选索引

只为用于搜索、排序或分组的列创建索引

考虑列的基数

索引列的类型尽量小

索引字符串值的前缀

只对字符串的前几个字符进行索引

只索引字符串值的前缀的策略是我们非常鼓励的，尤其是在字符串类型能存储的字符比较多的时候。

让索引列在比较表达式中单独出现

主键插入顺序

冗余和重复索引