04 | 深入浅出索引（上）

索引的出现其实就是为了提高数据查询的效率，就像书的目录一样

索引的常见模型

哈希表、有序数组和搜索树

哈希表

User2 和 User4 根据身份证号算出来的值都是 N，但没关系，后面还跟了一个链表。

需要注意的是，图中四个 ID_card_n hash 出来的值并不是递增的，这样做的好处是增加新的 User 时速度会很快，只需要往后追加。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的，需要全部扫描一遍。

所以，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。

有序数组

有序数组在等值查询和范围查询场景中的性能就都非常优秀

数组就是按照身份证号递增的顺序保存的。这时候如果你要查 ID_card_n2 对应的名字，用二分法就可以快速得到，这个时间复杂度是 O(log(N))

同样可以通过二分找到大于范围和小于范围的两个值

更新数据的时候必须得挪动后面所有的记录，成本太高

有序数组索引只适用于静态存储引擎

二叉树

二叉搜索树：一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；二叉搜索树的左、右子树也分别为二叉搜索树。

平衡二叉树：平衡二叉树是在二叉搜索树的基础上引入的，指的是结点的左子树和右子树的深度差不超过 1.

多叉树：每个结点可以有多个子结点，子节点的大小从左到右依次递增。

二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))

当然为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))

一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块

Q：为什么树高20就是20个数据块？

A：每个叶子结点就是一个块，每个块包含两个数据（？），块之间通过链式方式链接。树高20的话，就要遍历20个块。因为是二叉树结构，每次指针查找很大概率是触发随机磁盘读（比如很难刚好碰上一个节点和他的左右儿子刚好相邻）

数据库中的所有数据都存储于数据块中，而叶子节点块只是数据块的一种，因为它位于索引b*tree结构中的最末端（root(根)–>branch(分枝)–>leaf(叶子)），所以，就称为叶子节点块（leaf node block）

《个人理解》参照下面的B+树，一个叶子块中可以存放多条索引和数据

为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N 叉”树。这里，“N 叉”树中的“N”取决于数据块的大小。

Q：B+树是一颗N叉树，N是由什么决定的？能否调整？
A:

1. 通过修改page的大小来间接调整N的大小。一个节点上的所有数据都在一个page中，页越大，每页存放的索引就越多，N就越大。数据页调整后，如果数据页太小层数会太深，数据页太大，加载到内存的时间和单个数据页查询时间会提高，需要达到平衡才行。

2. 修改索引的大小。每个索引包括固定字节数的Point指针和索引字段内容，索引字段越小，每页能存的索引就越多，N就越大。

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

InnoDB 的索引模型

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。

InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。

假设，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。

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)，两棵树的示例示意图如下。

索引类型分为主键索引和非主键索引

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

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

Q：基于主键索引和普通索引的查询有什么区别？

A：

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

索引维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。

以上面这个图为例，

如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。

如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。

而更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。

当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。

Q：如果插入的数据是在主键树叶子结点的中间，后面的所有页如果都是满的状态，是不是会造成后面的每一页都会去进行页分裂操作，直到最后一个页申请新页移过去最后一个值?

A: 不会不会，只会分裂它要写入的那个页面。每个页面之间是用指针串的，改指针就好了，不需要“后面的全部挪动

ps:数据块和数据页的含义应该是一致的

自增主键

自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的： NOT NULL PRIMARY KEY AUTO_INCREMENT。

好处：（存，查，插）

• 插入新记录的时候可以不指定 ID 的值，系统会获取当前 ID 最大值加 1 作为下一条记录的 ID 值。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
• 自增字段为整形或长整型，每个非主键索引的叶子节点上都是主键的值，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
• 业务逻辑字段不容易保证索引树结点有序插入，这样写入成本较高。

Q:有没有什么场景适合用业务字段直接做主键的呢？

A:典型的 KV 场景

1. 只有一个索引；

2. 该索引必须是唯一索引

这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。

自增ID用完了怎么办？

https://www.modb.pro/db/131380

表的自增 id 达到上限后，再申请时它的值就不会改变，进而导致继续插入数据时报主键冲突的错误

索引重建

重建普通索引时，直接先删除索引，再重新创建即可。

alter table T drop index k; 
alter table T add index(k);

主键索引不能通过上面的语句去重建，因为删除主键索引后，innodb会如下处理:

• 如果存在非空且字段类型为数值的唯一索引（INT and NOT NULL and UNIQUE INDEX）， 会将第一个满足条件的索引作为主键索引, _rowid为对应主键，值与唯一索引相同。(可通过select _rowid from table查询)。
• 如果找不到合适的索引，那么 InnoDB 会自动生成一个不可见的名为 ROW_ID 的列名为 GEN_CLUST_INDEX 的主键索引，该列是一个 6 字节的自增数值，随着插入而自增。

所以删除主键索引的结果其实是修改了主键字段，而普通索引的叶子节点存的是主键的值，所以，一旦修改了主键字段，普通索引也会有影响，叶子节点的值将被修改成新的主键字段。

当主键索引需要重建时，更好的做法是直接使用alter table t engine=innodb重建表。

05 | 深入浅出索引（下）

Q ：执行 select * from T where k between 3 and 5，需要执行几次树的搜索操作，会扫描多少行？

A：

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，不满足条件，循环结束。

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

覆盖索引

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

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

在高频请求考虑建立联合索引（例如：（身份证号、姓名）），就是用到了覆盖索引，不再需要回表查整行记录，减少语句的执行时间。

最左前缀原则

「联合索引的多个字段中，只有当查询条件为联合索引的第一个字段时，查询才能使用该索引。」

这个最左前缀可以是联合索引的最左 N 个字段

「索引可以根据字段值最左若干个字符进行模糊查询。」

分析（name，age）这个联合索引，可以看到，索引项是按照索引定义里面出现的字段顺序排序的。当你的逻辑需求是查到所有名字是“张三”的人时，可以快速定位到 ID4，然后向后遍历得到所有需要的结果。如果你要查的是所有名字第一个字是“张”的人，你的 SQL 语句的条件是”where name like ‘张 %’“。这时，你也能够用上这个索引，查找到第一个符合条件的记录是 ID3，然后向后遍历，直到不满足条件为止。

现在，假设我们有一下三种查询情景：

• 查出用户名的第一个字是 “张” 开头的人的密码。即查询条件子句为 “where username like ” 张 %””
• 查处用户名中含有 “张” 字的人的密码。即查询条件子句为 “where username like “% 张 %””
• 查出用户名以 “张” 字结尾的人的密码。即查询条件子句为 “where username like “% 张 “”

以上三种情况下，只有第 1 种能够使用（username,password）联合索引来加快查询速度。

Q：表id为主键，username为普通索引，问select id, username from user_table where username like "%张%" 能否使用到 (username) 索引？

A：答案是可以的，因为查询的所有字段 (id, username) 在二级索引（username）中都存在，二级索引树比主键索引树小很多，所以会直接遍历二级索引。值得注意的是，这里是遍历整个索引树，而不是在索引树中快速定位数据。

前缀索引

Q：需要根据 email 字段查找用户信息的需求，当然我们可以直接给 email 字段创建一个索引，但我们仔细想想，有必要为整个 email 字段创建索引吗？

A：其实没必要的，因为邮箱地址是有一个格式的，都是 “xxxx@xxx.com”, 所以其实 email 字段的后面几位区分度不高。这时为整个 email 字段创建索引很浪费空间，我们可以创建前缀索引，将字段的前几个字符作为索引即可。

mysql 中使用 ADD KEY (column_name (prefix_length)) 为字段创建前缀索引。

前缀索引设计的好坏在于选择合适的前缀索引长度。如果选择太长，会造成索引空间的浪费；如果选择太短，会导致索引树大量重复的 key，索引效果不理想

问题：

• 使用前缀索引可能会增加记录扫描次数与回表次数，影响性能
• 使用前缀索引就用不上覆盖索引对查询性能的优化了

前缀索引的区分度不够高怎么办

一个很常见的解决手段就是 Hash。

对这个超长字段 a 进行 hash(假设命名为 a_hash) 存入数据库，然后对这个 hash 值建立索引，由于 hash 值同样可能存在冲突，也就是说两个不同的 a 通过 Hash 函数得到的结果可能是相同的，所以我们在查询语句的 where 部分还需要进行一次精确判断

索引下推

对于 user_table 表，我们现在有（username,age）联合索引 如果现在有一个需求，查出名称中以 “张” 开头且年龄小于等于 10 的用户信息，语句 C 如下：

“select * from user_table where username like ” 张 %” and age > 10″.

语句 C 会根据（username,age）联合索引查询所有满足名称以 “张” 开头的索引，然后直接再筛选出年龄小于等于 10 的索引，之后再回表查询全行数据

第二种方式需要回表查询的全行数据比较少，这就是 mysql 的索引下推，在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

https://copyfuture.com/blogs-details/20211116185246587T#_157

https://mp.weixin.qq.com/s?__biz=MzI4MTc0NDg2OQ==&mid=2247483854&idx=1&sn=13a28d8754b2718d8e6a044492897b99