跳至主要內容

索引

Weiser大约 16 分钟

索引

B树和B+树

我们平时看到 B+树 还有 B-树，不免就会将 B-树 读成 "B减树" ，但 B-树 其 - 横线只是连接符，所以 B-树 就是称为 B树。

自平衡二叉树虽然查找的时间复杂度在O(logn)，前面也说过它本身是一个二叉树，每个节点只能有2个子节点，那么随着数据量增大的时候，节点个数越多，树高度也会增高（也就是树的深度越深），增加磁盘I/O次数，影响查询效率。

那么你如果从树形结构的二叉树这一路的进阶过程中可以看到，二叉树每一次为了解决一个新的问题都会创造出新的 bug （或者创造一个又个的痛点）。

看到这就不难猜到，B树的出现可以解决树高度的问题。之所以是B树，而并不是名称中"xxx二叉树"，就是它不再限制一个父节点中只能有两个子节点，而是允许 M 个子节点（M > 2）。不仅如此，B树的一个节点可以存储多个元素，相比较于前面的那些二叉树数据结构又将整体的树高度降低了。

B 树的节点可以包含有多个字节点，所以 B树是一棵多叉树，它的每一个节点包含的最多子节点数量的称为B树的阶。如下图是一颗3阶的B树。

image.png
image.png

上图中每一个节点称为页，在mysql中数据读取的基本单位是页，而页就是我们上面所说的磁盘块。磁盘块中的p节点是指向子节点的指针。指针在树结构中都有，在前面的二叉树中也都是有的。

那我们来看一下上图所示，当一颗3阶的B树查找 90 这个的元素时的流程是怎么样的？

先从根节点出发，也就是 磁盘块1，判断 90 在17 ~ 35之间，通过磁盘块1中的指针 p3 找到磁盘块4。还是按照原来的步骤，在磁盘块4中的65 ~ 87之间相比较，最后磁盘4的指针p3找到磁盘块11。也就找到有匹配90的键值。

可以发现一颗3阶的B树在查找叶子节点时，由于树高度只有 3，所以查找过程最多只需要3次的磁盘I/O操作。

数据量不大时可能不太真切。但当数据量大时，节点也会随着增多；此时如果还是前面的自平衡二叉树的场景下，由于二叉树只能最多2个叶子节点的约束，也只能纵向去的去扩展子节点，树的高度会很高，意味着需要更多的操作磁盘I/O次数。而B树则可以通过横向扩展节点从而降低树的高度，所以效率自然要比二叉树效率更高。（直白说就是变矮胖了）

看到这，相信你也知道如果B树这么适合，也就没有接下来B+树的什么事了。

接着，那为什么不用B树，而用了B+树呢？

你看啊，B树其实已经满足了我们最前面所要满足的条件，减少磁盘I/O操作，同时支持按区间查找。但注意，虽然B树支持按区间查找，但并不高效。例如上面的例子中，B树能高效的通过等值查询 90 这个值，但不方便查询出一个期间内3 ~ 10区间内所有数的结果。因为当B树做范围查询时需要使用中序遍历，那么父节点和子节点也就需要不断的来回切换涉及了多个节点会给磁盘I/O带来很多负担。

B+树

B+树从 + 的符号可以看出是B树的升级版，MySQL 中innoDB引擎中的索引底层数据结构采用的正是 B+树。

B+树相比于B树，做了这样的升级：B+树中的非叶子节点都不存储数据，而是只作为索引。由叶子节点存放整棵树的所有数据。而叶子节点之间构成一个从小到大有序的链表互相指向相邻的叶子节点，也就是叶子节点之间形成了有序的双向链表。如下图B+树的结构。

image.png
image.png

（B+树是不是有点像前面的跳表，数据底层是数据，上层都是按底层区间构成的索引层，只不过它不像跳表是纵向扩展，而是横向扩展的“跳表”。这么做的好处即减少磁盘的IO操作又提高了范围查找的效率。）

接着再来看B+树的插入和删除，B+树做了大量冗余节点，从上面可以发现父节点的所有元素都会在子节点中出现，这样当删除一个节点时，可以直接从叶子节点中删除，这样效率更快。

B树相比于B+树，B树没有冗余节点，删除节点时会发生复杂的树变形，而B+树有冗余节点，不会涉及到复杂的树变形。而且B+树的插入也是如此，最多只涉及树的一条分支路径。B+树也不用更多复杂算法，可以类似黑红树的旋转去自动平衡。

唯一索引和普通索引

普通索引(INDEX)：最基本的索引，没有任何限制

唯一索引(UNIQUE)：与"普通索引"类似，不同的就是：索引列的值必须唯一，但允许有空值。

主键索引(PRIMARY)：它 是一种特殊的唯一索引，不允许有空值。

全文索引(FULLTEXT )：可用于 MyISAM 表，mysql5.6之后也可用于innodb表， 用于在一篇文章中，检索文本信息的, 针对较大的数据，生成全文索引很耗时和空间。

联合（组合）索引：为了更多的提高mysql效率可建立组合索引，遵循”最左前缀“原则。

聚集索引和非聚集索引

这个表的建表语句是：

mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。

img
img

从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。

主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。

非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

根据上面的索引结构说明，我们来讨论一个问题：基于主键索引和普通索引的查询有什么区别？

  • 如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；
  • 如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

最左前缀

img
img

可以看到，索引项是按照索引定义里面出现的字段顺序排序的。

当你的逻辑需求是查到所有名字是“张三”的人时，可以快速定位到 ID4，然后向后遍历得到所有需要的结果。

如果你要查的是所有名字第一个字是“张”的人，你的 SQL 语句的条件是where name like ‘张 %’。这时，你也能够用上这个索引，查找到第一个符合条件的记录是 ID3，然后向后遍历，直到不满足条件为止。

可以看到，不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个 最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

基于上面对最左前缀索引的说明，我们来讨论一个问题：在建立联合索引的时候，如何安排索引内的字段顺序？

这里我们的评估标准是，索引的复用能力。因为可以支持最左前缀，所以当已经有了 (a,b) 这个联合索引后，一般就不需要单独在 a 上建立索引了。因此，第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

所以现在你知道了，这段开头的问题里，我们要为高频请求创建 (身份证号，姓名）这个联合索引，并用这个索引支持“根据身份证号查询地址”的需求。

那么，如果既有联合查询，又有基于 a、b 各自的查询呢？查询条件里面只有 b 的语句，是无法使用 (a,b) 这个联合索引的，这时候你不得不维护另外一个索引，也就是说你需要同时维护 (a,b)、(b) 这两个索引。

这时候，我们要考虑的原则就是空间了。比如上面这个市民表的情况，name 字段是比 age 字段大的 ，那我就建议你创建一个（name,age) 的联合索引和一个 (age) 的单字段索引。

回表和覆盖索引

回表

在下面这个表 T 中，如果我执行 select * from T where k between 3 and 5，需要执行几次树的搜索操作，会扫描多少行？

下面是这个表的初始化语句。

mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0, 
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;
 
insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');
img
img

现在，我们一起来看看这条 SQL 查询语句的执行流程：

  1. 在 k 索引树上找到 k=3 的记录，取得 ID = 300；
  2. 再到 ID 索引树查到 ID=300 对应的 R3；
  3. 在 k 索引树取下一个值 k=5，取得 ID=500；
  4. 再回到 ID 索引树查到 ID=500 对应的 R4；
  5. 在 k 索引树取下一个值 k=6，不满足条件，循环结束。

在这个过程中，回到主键索引树搜索的过程，我们称为回表。可以看到，这个查询过程读了 k 索引树的 3 条记录（步骤 1、3 和 5），回表了两次（步骤 2 和 4）。

在这个例子中，由于查询结果所需要的数据只在主键索引上有，所以不得不回表。 那么，有没有可能经过索引优化，避免回表过程呢？

覆盖索引

如果执行的语句是 select ID from T where k between 3 and 5，这时只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引。

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

需要注意的是，在引擎内部使用覆盖索引在索引 k 上其实读了三个记录，R3~R5（对应的索引 k 上的记录项），但是对于 MySQL 的 Server 层来说，它就是找引擎拿到了两条记录，因此 MySQL 认为扫描行数是 2。

备注：关于如何查看扫描行数的问题，将会在第17 文章《如何正确地显示随机消息？》open in new window中详细讨论。

基于上面覆盖索引的说明，我们来讨论一个问题：在一个市民信息表上，是否有必要将身份证号和名字建立联合索引？

假设这个市民表的定义是这样的：

CREATE TABLE `tuser` (
  `id` int(11) NOT NULL,
  `id_card` varchar(32) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `ismale` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `id_card` (`id_card`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB

我们知道，身份证号是市民的唯一标识。也就是说，如果有根据身份证号查询市民信息的需求，我们只要在身份证号字段上建立索引就够了。而再建立一个（身份证号、姓名）的联合索引，是不是浪费空间？

**如果现在有一个高频请求，要根据市民的身份证号查询他的姓名，这个联合索引就有意义了。*它可以在这个高频请求上*用到覆盖索引，不再需要回表查整行记录，减少语句的执行时间。

当然，索引字段的维护总是有代价的。因此，在建立冗余索引来支持覆盖索引时就需要权衡考虑了。 这正是业务 DBA，或者称为业务数据架构师的工作。

索引设计

我面试几乎必问：你设计索引的原则是什么？怎么避免索引失效？open in new window

针对表

查询频次高，且数据量多的表

针对字段

最好从where子句的条件中提取，如果where子句中的组合比较多，那么应当挑选最常用、过滤效果最好的列的组合。

🎡其他原则

  1. 最好用唯一索引，区分度越高，使用索引的效率越高
  2. 不是越多越好，维护也需要时间和空间代价，建议单张表索引不超过 5 个

因为 MySQL 优化器在选择如何优化查询时，会根据统一信息，对每一个可以用到的索引来进行评估，以生成出一个最好的执行计划，如果同时有很多个索引都可以用于查询，就会增加 MySQL 优化器生成执行计划的时间，同样会降低查询性能。

比如：

我们创建了三个单列索引，name，status，address

当我们where中根据status和address两个字段来查询时，数据库只会选择最优的一个索引，不会所有单列索引都使用。

最优的索引：具体是指所查询表中，辨识度最高(所占比例最少)的索引列，比如此处address中有一个辨识度很高的 '西安市'数据；
image.png
​

  1. 使用短索引,索引创建之后也是使用硬盘来存储的，因此提升索引访问的I/O效率，也可以提升总体的访问效率。假如构成索引的字段总长度比较短，那么在给定大小的存储块内可以存储更多的索引值，相应的可以有效的提升MySQL访问索引的I/O效率。
  2. 利用最左前缀，比如有N个字段，我们不一定需要创建N个索引，可以用复合索引

也就是说，我们尽量创建复合索引，而不是单列索引

创建复合索引:
	CREATE INDEX idx_name_email_status ON tb_seller(name,email,status);

就相当于
	对name 创建索引 ;
	对name , email 创建了索引 ;
	对name , email, status 创建了索引 ;
复制代码

⏰举个栗子

假设我们有这么一个表，id为主键，没有创建索引：

CREATE TABLE `tuser` (
  `id` int(11) NOT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
) ENGINE=InnoDB
复制代码

如果要在此处建立复合索引，我们要遵循什么原则呢？
​

通过调整顺序，可以少维护一个索引

  • 比如我们的业务需求里边，有如下两种查询方式：
    1. 根据name查询
    2. 根据name和age查询

如果我们建立索引（age,name），由于最左前缀原则，我们这个索引能实现的是根据age，根据age和name查询，并不能单纯根据name查询（因为跳跃了），为了实现我们的需求，我们还得再建立一个name索引；

而如果我们通过调整顺序，改成（name，age），就能实现我们的需求了，无需再维护一个name索引，这就是通过调整顺序，可以少维护一个索引。

考虑空间->短索引

  • 比如我们的业务需求里边，有以下两种查询方式：
    1. 根据name查询
    2. 根据age查询
    3. 根据name和age查询

我们有两种方案：

  1. 建立联合索引(name,age)，建立单列索引：age索引。
  2. 建立联合索引(age,name)，建立单列索引：name索引。

这两种方案都能实现我们的需求，这个时候我们就要考虑空间了，name字段是比age字段大的，显然方案1所耗费的空间是更小的，所以我们更倾向于方案1。

何时建立索引

  1. where中的查询字段
  2. 查询中与其他表关联的字段，比如外键
  3. 排序的字段
  4. 统计或分组的字段

何时不用索引

  1. 表中数据量很少
  2. 经常改动的表
  3. 频繁更新的字段
  4. 数据重复且分布均匀的表字段（比如包含了很多重复数据，那此时多叉树的二分查找，其实用处不大，可以理解为O(logn)退化了）

explain

https://juejin.cn/post/7074030240904773645open in new window

索引失效情况

  • 以%开头的 like 查询不能利用 B-Tree 索引，执行计划中 key 的值为 null 表示没有使用索引
  • 数据类型出现隐式转换的时候也不会使用索引，例如，where 'age' 10=30
  • 对索引列进行函数运算，原因同上
  • 正则表达式不会使用索引
  • 字符串和数据比较不会使用索引
  • 复合索引的情况下，假如查询条件不包含索引列最左边部分，即不满足最左原则 leftmost，是不会使用复合索引的
  • 如果 MySQL 估计使用索引比全表扫描更慢，则不使用索引
  • 用 or 分割开的条件，如果 or 前的条件中的列有索引，而后面的列中没有索引，那么涉及的索引都不会被用到
  • 使用负向查询（not ，not in， not like ，<> ,!= ,!> ,!< ） 不会使用索引
默认页脚
Copyright © 2023 Weiser