​第十三击 | 25个数据库索引题也就这样

大家好，我是蓝蓝。

在上一篇中，总结了20个左右高频数据库基础题，不知道大家复习如何了，没有复习的小伙伴可以先去看看，今天总结了25索引相关的题目。

第十击 | 数据库理论20题

1 什么是索引

索引在数据库中的作用类似于目录在书籍中的作用，用来提高查找信息的速度。使用索引查找数据，无需对整表进行扫描，可以快速找到所需数据。

索引的目的在于提高查询效率，可以类比字典，如果要查 “LanTian” 这个单词，我们肯定需要定位到 L字母，然后从下往下找到 a 字母，再找到剩下的 Tian 。如果没有索引，那么你可能需要把所有单词看一遍才能找到你想要的，如果我想找到 L 开头的单词呢？或者LA开头的单词呢？是不是觉得如果没有索引，这个事情根本无法完成？

除了词典，生活中随处可见索引的例子，如火车站的车次表、图书的目录等。它们的原理都是一样的，通过不断的缩小想要获得数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是我们总是通过同一种查找方式来锁定数据。

数据库也是一样，但显然要复杂许多，因为不仅面临着等值查询，还有范围查询(>、<、between、in)、模糊查询 (like) 、并集查询 (or) 等等。数据库应该选择怎么样的方式来应对所有的问题呢？

我们回想字典的例子，能不能把数据分成段，然后分段查询呢？最简单的如果1000 条数据，1 到 100 分成第一段，101 到 200 分成第二段，201 到 300 分成第三段……这样查第 250 条数据，只要找第三段就可以了，一下子去除了 90% 的无效数据。但如果是 1 千万的记录呢，分成几段比较好？稍有算法基础的同学会想到搜索树，其平均复杂度是 logN，具有不错的查询性能。但这里我们忽略了一个关键的问题，复杂度模型是基于每次相同的操作成本来考虑的，数据库实现比较复杂，数据保存在磁盘上，而为了提高性能，每次又可以把部分数据读入内存来计算，因为我们知道访问磁盘的成本大概是访问内存的十万倍左右，所以简单的搜索树难以满足复杂的应用场景。

2 什么时候用索引，什么时候不用索引

索引是一门艺术，索引之所以能提升查询速度，在于它在插入时对数据进行了排序（显而易见，它的缺点是影响插入或者更新的性能）。

一般来说，在数据表中的数据行数比较少的时候，比如不到 1000 行的情况，是不用加索引，另外，如果数据重复读比较高比如高于 10% 也是不用增加索引。举个例子，如果表中是性别字段，我们就不需要在这性别这个字段加索引，为什么呢？如果有 100 万 行数据，查找其中的 50w 行数据，一旦创建了索引，你需要先访问 50 万次索引，然后再访问 50w 次数据表，这样假期的开销比不适用索引还要大了。

为了验证这个问题，我们一起做个实验，SQL 我放在后台了，回复“sql”即可领取去实验。

分别有两个数据表，一个是 lanlan_with_index，一个是 lanlan_without_index 两个表，其中给 lanlan_with_index 表 name 属性增加索引，而表 lanlan_without_index 不加索引。

想要根据姓名查询表 lanlan_without_index (时间为 0.013)

同样的，根据姓名查询表 lanlan_with_index (时间为 0.021)

从结果就可以发现，创建 name 字段索引居然比没有创建索引时效率更低，所以数据量小的时候也是可以不建索引的。

大家也可以拿 sql 去试试，不同机器性能不一样，可以多尝试尝试。

刚才说过，如果字段取值比较少，比如性别字段，是不是就不需要创建索引呢？答案是不一定的

做一个实验 性别字段创建索引后的效果是如何的

性别无外乎男女，当然了，你说也有不男不女啥的，也没关系，这里就两种情况，男生用 1 表示，女生用 0 表示，而且这个数据表中有 2w条数据，不过只有一条数据性别是男生。

现在我想要筛选出这个男生

select * from user_gender where user_gender = 1

运行时间为 0.034

我们创建索引后再执行，发现时间居然缩短到 0.02。

综上可以总结两点，索引是用来帮助我们快速定位数据，如果定位的数据太多，那就失去了它的使用价值(比如上方的性别字段)，当然，我们还要考虑数值的分布情况哦。

3 索引的优缺点

索引的优点

• 索引可以减少服务器需要扫描的数据量，从而大大提高查询效率

• 通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

• 唯一索引能保证表中数据的唯一性

索引的缺点

• 时间方面：创建索引和维护索引要耗费时间，具体地，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，会降低增/改/删的执行效率；

• 空间方面：索引需要占物理空间。

• 不恰当的使用索引会造成服务器重复扫描数据，造成查询浪费。

4 创建/删除索引的三种方式

第一种方式：在执行 CREATE TABLE 时创建索引

CREATE TABLE user_index2 (
    id INT auto_increment PRIMARY KEY,
    first_name VARCHAR (16),
    last_name VARCHAR (16),
    id_card VARCHAR (18),
    information text,
    KEY name (first_name, last_name),
    FULLTEXT KEY (information),
    UNIQUE KEY (id_card)
);

第二种方式：使用 ALTER TABLE 命令去增加索引

ALTER TABLE table_name ADD INDEX index_name (column_list);

ALTER TABLE 用来创建普通索引、UNIQUE 索引或 PRIMARY KEY 索引。

其中 table_name 是要增加索引的表名，column_list 指出对哪些列进行索引，多列时各列之间用逗号分隔。

索引名 index_name 可自己命名，缺省时，MySQL 将根据第一个索引列赋一个名称。另外，ALTER TABLE 允许在单个语句中更改多个表，因此可以在同时创建多个索引。

第三种方式：使用 REATE INDEX 命令创建

CREATE INDEX index_name ON table_name (column_list);

CREATE INDEX 可对表增加普通索引或 UNIQUE 索引。（但是，不能创建PRIMARY KEY索引）

删除索引

根据索引名删除普通索引、唯一索引、全文索引：alter table 表名 drop KEY 索引名

alter table user_index drop KEY name;
alter table user_index drop KEY id_card;
alter table user_index drop KEY information;

删除主键索引：alter table 表名 drop primary key（因为主键只有一个）。这里值得注意的是，如果主键自增长，那么不能直接执行此操作（自增长依赖于主键索引）：

需要取消自增长再行删除：

alter table user_index
-- 重新定义字段
MODIFY id int,
drop PRIMARY KEY

但通常不会删除主键，因为设计主键一定与业务逻辑无关。

5 哪些情况最好加索引？

运用好索引使用原则，让其效率最大化。创建索引也是有一定的规律可循

• 字段的数值有唯一性的限制

索引本身可以起到约束的作用，比如唯一索引、主键索引都是可以起到唯一性约束的，因此在我们的数据表中，如果某个字段是唯一性的，就可以直接创建唯一性索引，或者主键索引。

• 频繁作为 WHERE 查询条件的字段，尤其在数据表大的情况下

在数据量大的情况下，某个字段在 SQL 查询的 WHERE 条件中经常被使用到，那么就需要给这个字段创建索引了。创建普通索引就可以大幅提升数据查询的效率。

• 需要经常 GROUP BY 和 ORDER BY 的列

索引就是让数据按照某种顺序进行存储或检索，因此当我们使用 GROUP BY 对数据进行分组查询，或者使用 ORDER BY 对数据进行排序的时候，就需要对分组或者排序的字段进行索引。

• UPDATE、DELETE 的 WHERE 条件列，一般也需要创建索引

对数据按照某个条件进行查询后再进行 UPDATE 或 DELETE 的操作，如果对
WHERE 字段创建了索引，就能大幅提升效率。

原理是因为我们需要先根据 WHERE 条件列检索出来这条记录，然后再对它进行更新或删除。如果进行更新的时候，更新的字段是非索引字段，提升的效率会更明显，这是因为非索引字段更新不需要对索引进行维护。不过在实际工作中，我们也需要注意平衡，如果索引太多了，在更新数据的时候，如果涉及到索引更新，就会造成负担。

• DISTINCT 字段需要创建索引

6 哪些情况不需要创建索引

第一种情况是，WHERE 条件（包括 GROUP BY、ORDER BY）里用不到的字段不需要创建索引，索引的价值是快速定位，如果起不到定位的字段通常是不需要创建索引的

第二种情况是，如果表记录太少，比如少于 1000 个，那么是不需要创建索引的。我之前讲过一个 SQL 查询的例子，表记录太少，是否创建索引对查询效率的影响并不大

第三种情况是，字段中如果有大量重复数据，也不用创建索引，比如性别字段。不过我们也需要根据实际情况来做判断，这一点我在之前的文章里已经进行了说明，这里不再赘述。

最后一种情况是，频繁更新的字段不一定要创建索引。因为更新数据的时候，也需要更新索引，如果索引太多，在更新索引的时候也会造成负担，从而影响效率。

7 说说你知道哪些索引

既然知道了索引的作用，有优点，优缺点，那你说说有哪几种索引，这几种索引有什么区别呢

如果从功能逻辑划分，那么有 4 种索引，分别为普通索引、唯一索引、主键索引及全文索引。

• 什么是普通索引

最基础的索引，无任何约束，目的很单纯，仅仅为了提高查询效率。

• 什么是唯一索引

对于唯一索引，相比于普通索引增加了唯一性约束，一张表中可以有多个唯一索引。

• 什么是主键索引

在唯一索引的基础上又加了不为空的约束，即 NOT NULL + UNIQUE，一张表中最多只有一个主键索引。

• 什么是全文索引

很少使用全文索引，如果要用可能会借助其他的更加专业的搜索引擎如 ES。

如果按照物理实现方式来划分，分为 2 种，分别为聚集索引和非聚集索引，下面继续看聚集索引和非聚集索引

8 聚集索引和非聚集索引的区别

两者的根本区别在于表记录的排列顺序和与索引的排列顺序是否一致。

• 聚集索引

假设以 InnoDB 聚集索引来说，叶子节点中存储的就是行数据，行数据在物理储器中的真实地址就是按照主键索引树形成的顺序进行排列的以查询效率快，只要找到第一个索引值记录，其余就连续性的记录在物理也一样连续存放。

缺点也很明显，聚集索引对应的缺点就是修改慢，因为为了保证表中记录的物理和索引顺序一致，在记录插入的时候，会对数据页重新排序（因为在真实物理存储器的存储顺序只能有一种，而插入新数据必然会导致主键索引树的变化，主键索引树的顺序发生了改变，叶子节点中存储的行数据也要随之进行改变，就会发生大量的数据移动操作，所以效率会慢）。因为在物理内存中的顺序只能有一种，所以聚集索引在一个表中只能有一个。

• 非聚集索引

  非聚集索引制定了表中记录的逻辑顺序，但是记录的物理和索引不一定一致（在逻辑上数据是按顺序排存放的，但是物理上在真实的存储器中是散列存放的），两种索引都采用B+树结构，非聚集索引的叶子层并不和实际数据页相重叠，而采用叶子层包含一个指向表中的记录在数据页中的指针方式。非聚集索引层次多，不会造成数据重排。所以如果表的读操作远远多于写操作，那么就可以使用非聚集索引。

两者小结

聚集索引就类似新华字典中的拼音排序索引，都是按顺序进行，例如找到字典中的“爱”，就里面顺序执行找到“癌”。而非聚集索引则类似于笔画排序，索引顺序和物理顺序并不是按顺序存放的。总的来说，聚集索引的叶节点就是数据节点。而非聚簇索引的叶节点仍然是索引节点，只不过有一个指针指向对应的数据块

9 聚集索引与非聚集索引的区别

• 一个表中只能拥有一个聚集索引，而非聚集索引一个表可以存在多个。

• 聚集索引，索引中键值的逻辑顺序决定了表中相应行的物理顺序；非聚集索引，索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同。

• 索引是通过二叉树的数据结构来描述的，我们可以这么理解聚簇索引：索引的叶节点就是数据节点。而非聚簇索引的叶节点仍然是索引节点，只不过有一个指针指向对应的数据块。

• 聚集索引：物理存储按照索引排序；非聚集索引：物理存储不按照索引排序；

何时使用聚集索引或非聚集索引？

10 覆盖索引、回表等这些，了解过吗？

• 覆盖索引：查询列要被所建的索引覆盖，不必从数据表中读取，换句话说查询列要被所使用的索引覆盖。

• 回表：二级索引无法直接查询所有列的数据，所以通过二级索引查询到聚簇索引后，再查询到想要的数据，这种通过二级索引查询出来的过程，就叫做回表。

11 索引失效的情况有哪些？

创建了索引后我们还应该检查索引是否生效。

• 如果索引进行了表达式计算，则会失效

• 如果对索引使用函数，也会造成失效

• 在 WHERE 子句中，如果在 OR 前的条件列进行了索引，而在 OR 后的条件列没有进行索引，那么索引会失效。

• 当我们使用 LIKE 进行模糊查询的时候，后面不能是 %

• 索引列与 NULL 或者 NOT NULL 进行判断的时候也会失效。

• 我们在使用联合索引的时候要注意最左原则

最左原则也就是需要从左到右的使用索引中的字段，一条 SQL 语句可以只使用联合索引的一部分，但是需要从最左侧开始，否则就会失效。我在讲联合索引的时候举过索引失效的例
子。

12 索引的使用场景有哪些？

• 对于中大型表建立索引非常有效，对于非常小的表，一般全部表扫描速度更快些。

• 对于超大型的表，建立和维护索引的代价也会变高，这时可以考虑分区技术。

• 如何表的增删改非常多，而查询需求非常少的话，那就没有必要建立索引了，因为维护索引也是需要代价的。

• 一般不会出现再where条件中的字段就没有必要建立索引了。

• 多个字段经常被查询的话可以考虑联合索引。

• 字段多且字段值没有重复的时候考虑唯一索引。

• 字段多且有重复的时候考虑普通索引。

13 如何对索引进行优化？

对索引的优化其实最关键的就是要符合索引的设计原则和应用场景，将不符合要求的索引优化成符合索引设计原则和应用场景的索引。

除了索引的设计原则和应用场景那几点外，还可以从以下两方面考虑。

• 在进行查询时，索引列不能是表达式的一部分，也不能是函数的参数，因为这样无法使用索引。例如 select * from table_name where a + 1 = 2

• 将区分度最高的索引放在前面

• 尽量少使用select*

索引的使用场景、索引的设计原则和如何对索引进行优化可以看成一个问题。

14 使用索引查询一定能提高查询的性能吗？为什么

数据库服务器通常有两种存储介质，分别为硬盘和内存。其中内存属于临时存储，贵而小，如果出现断电或发生其他故障会造成数据丢失。而硬盘相当于永久存储，这也是为什么会将数据保存在硬盘上。

索引的价值在于我们能较快的在海量数据中找到想要的数据，如果数据量少自然不用创建索引。

如果某个字段数据重复度比较大，也是不用在此字段创建索引。比如当前有 50w 个人，不是男生就是女生，你此时对性别创建索引，那么在查询的时候，就会先访问索引然后再访问50w次数据表，这样加起来比不使用索引的代价还要更大。

创建索引代价哪些呢

通常，通过索引查询数据比全表扫描要快。但是我们也必须注意到它的代价。

• 索引需要空间来存储，也需要定期维护， 每当有记录在表中增减或索引列被修改时，索引本身也会被修改。这意味着每条记录的 INSERT，DELETE，UPDATE将为此多付出 4，5  次的磁盘 I/O。因为索引需要额外的存储空间和处理，那些不必要的索引反而会使查询反应时间变慢。使用索引查询不一定能提高查询性能，索引范围查询 (INDEX RANGE SCAN) 适用于两种情况:

• 基于一个范围的检索，一般查询返回结果集小于表中记录数的30%

• 基于非唯一性索引的检索

15 怎么查看MySQL语句有没有用到索引？

通过 explain，如以下例子：

EXPLAIN select * from user_gender where user_gender = 1;

• id：在⼀个⼤的查询语句中每个 SELECT 关键字都对应⼀个唯⼀的 id ，如 explain select * from s1 where id = (select id from s1 where name = 'egon1');第一个 select 的 id 是1，第二个 select 的 id 是 2。有时候会出现两个 select，但是 id 却都是1，这是因为优化器把子查询变成了连接查询 。

• select_type：select 关键字对应的那个查询的类型，如 SIMPLE，PRIMARY，SUBQUERY，DEPENDENT，SNION 。

• table：每个查询对应的表名 。

• type：type
  字段比较重要, 它提供了判断查询是否高效的重要依据依据. 通过 type
  字段, 我们判断此次查询是 全表扫描
  还是 索引扫描
  等。如const(主键索引或者唯一二级索引进行等值匹配的情况下)，ref(普通的⼆级索引列与常量进⾏等值匹配)，index(扫描全表索引的覆盖索引) 。

  通常来说, 不同的 type 类型的性能关系如下:
  ALL < index < range ~ index_merge < ref < eq_ref < const < system

ALL
  类型因为是全表扫描, 因此在相同的查询条件下, 它是速度最慢的.
  而 index
  类型的查询虽然不是全表扫描, 但是它扫描了所有的索引, 因此比 ALL 类型的稍快.

• possible_key：查询中可能用到的索引(可以把用不到的删掉，降低优化器的优化时间) 。

• key：此字段是 MySQL 在当前查询时所真正使用到的索引。

• filtered：查询器预测满足下一次查询条件的百分比 。

• rows 也是一个重要的字段. MySQL 查询优化器根据统计信息, 估算 SQL 要查找到结果集需要扫描读取的数据行数.
  这个值非常直观显示 SQL 的效率好坏, 原则上 rows 越少越好。

• extra：表示额外信息，如Using where，Start temporary，End temporary，Using temporary等。

16 百万级别或以上的数据如何删除

关于索引：由于索引需要额外的维护成本，因为索引文件是单独存在的文件，所以当我们对数据的增加，修改，删除，都会产生额外的对索引文件的操作，这些操作需要消耗额外的 IO，会降低增/改/删的执行效率。所以，在我们删除数据库百万级别数据的时候，查询 MySQL 官方手册得知删除数据的速度和创建的索引数量是成正比的。

• 所以我们想要删除百万数据的时候可以先删除索引（此时大概耗时三分多钟）

• 然后删除其中无用数据（此过程需要不到两分钟）

• 删除完成后重新创建索引(此时数据较少了)创建索引也非常快，约十分钟左右。

• 与之前的直接删除绝对是要快速很多，更别说万一删除中断,一切删除会回滚。那更是坑了。

17 非聚簇索引一定会回表查询吗

不一定，这涉及到查询语句所要求的字段是否全部命中了索引，如果全部命中了索引，那么就不必再进行回表查询。

举个简单的例子，假设我们在员工表的年龄上建立了索引，那么当进行select age from employee where age < 20的查询时，在索引的叶子节点上，已经包含了age 信息，不会再次进行回表查询。

18 为什么使用 B+ 树作为索引

数据库中支持很多种不同的索引，比如哈希索引，全文索引和 B+ 树索引，这里着重说说 B+ 树索引，在了解 B+ 树索引之前，需要先了解磁盘和内存的读写特点。

磁盘和内存的数据读写效率

内存的访问速度很快，价格比较高，所以通常计算机内存空间相对比较少。磁盘属于机械器件，当磁盘访问数据的时候，需要等磁盘盘片旋转到磁头下才能读取相应的数据，即使磁盘旋转速度很快，和内存的随机访问相比，性能差距仍然非常大。不过，如果是顺序访问大批量的数据，那么磁盘的性能和内存即可在同一数量级了。

为什么在顺序访问的时候，磁盘的性能和内存就可在同一数量级

如果我们将一个有序数组存放在磁盘中，它会存储在多个块中，既然是有序，如果要查找，我们首先想到的就是二分查找，所以先找到中间的块，将这个块从磁盘中取出放入内存，然后在内存中进行二分查找，如果下依次要找的元素在其他块中，我们需要再将相应的块从磁盘读入内存直到查询结束，其实这样的检索非常的慢，因为磁盘相对于内存而言访问速度实在太慢了。

我们应该想一切办法来减少访问磁盘的次数

19 如何减少磁盘访问的次数

假设现在老大让我做一个查询用户信息的功能，阿这简单啊。直接把这些用户信息(姓名，身份证，手机号)存放内存，好家伙，内存那么金贵，你这么干是不想干活了？

好嘛，那我就想办法将用户信息放磁盘，索引放内存，看似确实不错的方案啊。

我们直接生成一个有序数组，数组中每个元素存放两个值，一个是用户 ID，一个是此用户在磁盘上的位置，由于此时数据中间比较小就可以直接放入内存，这样的方法有个专业名称叫线性索引。

采用有序数组方式进行查找，很明显的优点在于等值查询和范围查询，用二分法可以O(log(N))的时间复杂度找到对应的速度。

不过缺点也很明显，有序数据只适用于静态存储引擎，当出现大量插入更新的时候，就需要移动大量的元素，导致效率低下。

所以出现了其他的数据结构-二叉搜索树，上述的结点就变为这样子

如果此时的索引数据非常的大，内存也加载不了，怎么处理？

那我管他的三七二十一，把索引数据也放在磁盘，那需要将哪些结点存入磁盘呢，又该如何去取出来？

B+ 树闪亮登场

说了这么多才引入这个问题的重点部分，正是因为 B+ 树给出了将树形索引的所有结点都存在磁盘上的高效检索方案，摆脱了内存空间的限制，从而也是面试中最高频的数据库问题之一。

操作系统对磁盘数据的访问都是以块为单位从磁盘中读出，如果此时节点的数据很小，可是磁盘仍然会将整个块取出来，这岂不是浪费了空间，效率就很低。

在 B+ 树中，一个关键的设计就在于将一个节点的大小刚好等于一个块的大小，节点中存储的不是一个元素而是一个装了 m 个元素的有序数组，这样就充分运用了空间，效率最大化。

对于 B+ 树而言，还有另外一个惊喜。它将所有节点分为内部节点和叶子节点，内部节点存储 key 和维持树形结构的指针，不存放 key 对应的数据，这样内部节点就可以存放更多的索引数据。而叶子节点仅仅存放 key 和对应的数据，不存储维持树形结构的指针

最后，B+  树还将同一层的所有节点串起来为有序双链表，综上，B+ 树不仅有良好的范围查找能力，也有灵活的调整能力。

因此，B+ 树是一棵完全平衡的 m 阶多叉树。所谓的 m 阶，指的是每个节点最多有 m 个
子节点，并且每个节点里都存了一个紧凑的可包含 m 个元素的数组。

20 B+ 树如何检索呢

1M=1024K=1048576bit

8bit(位)=1Byte(字节) 
1024Byte(字节)=1KB 
1024KB=1MB 
1024MB=1GB 
1024GB=1TB 

• 第一步确认寻找的查询值，位于数组哪两个相邻元素之间

• 将第一个元素对应指针读出，获取下一个 block 的位置

• 循环直到读到叶子节点

首先需要知道，现在的固态硬盘每秒能执行至少 10000 次 IO，所以查询一条数据，即使全部在磁盘上，也就需要 0.003~0.004s。加上 B+ 树很矮，排序的时候只需要比较 3~4 次就能定位数据插入的位置，这样效率就很高。

B+ 树索引由根节点，中间节点及叶子节点组成，其中叶子节点存放所有排序后的数据。当然也存在一种比较特殊的情况，比如高度为 1 的B+ 树索引：

此时就一个页，即是根节点也是叶子节点。我们将第一列一串数字当作是 B+ 树索引排序的列，你可以理解它是表 User 中的列 id，类型为 8 字节的 BIGINT，所以列 userId 就是索引键（key），类似下表

CREATE TABLE User (
  id BIGINT AUTO_INCREMENT PRIMARY KEY,
  name VARCHAR(128) NOT NULL,
  sex CHAR(6) NOT NULL,
  registerDate DATETIME NOT NULL,
  ...
)

这样一来，B+ 树从高度为1的树开始，随着数据的插入，高度也自然慢慢增加。你要牢记：索引是对记录进行排序， 高度为 1 的 B+ 树索引中，存放的记录都已经排序好了，若要在一个叶子节点内再进行查询，只进行二叉查找，就能快速定位数据。

可随着插入 B+ 树索引的记录变多，1个页（16K）无法存放这么多数据，所以会发生 B+ 树的分裂，B+ 树的高度变为 2，当 B+ 树的高度大于等于 2 时，根节点和中间节点存放的是索引键对，由（索引键、指针）组成。

索引键就是排序的列，而指针是指向下一层的地址，在 MySQL 的 InnoDB 存储引擎中占用 6 个字节。下图显示了 B+ 树高度为 2 时，B+ 树索引的样子：

可以看到，在上面的B+树索引中，若要查询索引键值为 5 的记录，则首先查找根节点，查到键值对（20，地址），这表示小于 20 的记录在地址指向的下一层叶子节点中。接着根据下一层地址就可以找到最左边的叶子节点，在叶子节点中根据二叉查找就能找到索引键值为 5 的记录。

21 一个高度为 2 的 B+ 树索引，理论上最多能存放多少行记录呢?

在计算机中，磁盘磁盘存储数据最小单元是扇区，一个扇区的大小是512字节。

文件系统中，最小单位是块，一个块大小就是4k;

InnoDB存储引擎最小储存单元是页，一页大小就是16k。

因为B+树叶子存的是数据，内部节点存的是键值+指针。索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而再去数据页中找到需要的数据;

在 MySQL InnoDB 存储引擎中，一个页的大小为 16K，在上面的表 User 中，键值 userId 是 BIGINT 类型，则：

根节点能最多存放以下多个键值对 = 16K / 键值对大小(8+6) ≈ 1100

再假设表 User 中，每条记录的大小为 500 字节，则

叶子节点能存放的最多记录为 = 16K / 每条记录大小 ≈ 32

综上所述，树高度为 2 的 B+ 树索引，最多能存放的记录数为：

总记录数 = 1100 * 32 =  35,200

也就是说，35200 条记录排序后，生成的 B+ 树索引高度为 2。在 35200 条记录中根据索引键查询一条记录只需要查询 2 个页，一个根叶，一个叶子节点，就能定位到记录所在的页。

高度为 3 的 B+ 树索引本质上与高度 2 的索引一致，如下图所示，不再赘述：

同理，树高度为 3 的 B+ 树索引，最多能存放的记录数为：

总记录数 = 1100（根节点） * 1100（中间节点） * 32 =  38,720,000

不知道此时的你吃惊不，实际上只需要高度为 3 的 B+ 树索就能存放 3800W 条记录。也就是说，可以存放两千万左右的记录。B+树高度一般为1-3层，已经满足千万级别的数据存储。,在 3800W 条记录中定位一条记录，只需要查询 3 个页。那么 B+ 树索引的优势是否逐步体现出来了呢？

不过在真实的环境中，不是每个页的利用率都很高，存在碎片问题是常事，此时假设每个也的使用率为 60 %

从上图可以清楚的看见，即使是 50 亿的数据，根据索引键值查询记录，只需要 4 次 I/O，大概仅需 0.004 秒。如果这些查询的页已经被缓存在内存缓冲池中，查询性能会更快。

讲到这儿，你应该了解了 B+ 树索引的组织形式，以及为什么在上亿的数据中可以通过B+树索引快速定位查询的记录。B+的高光时刻我们已经见证，那达到这样美好的情况自然是有一定代价的，就是我们前面说的插入性能问题。

优化 B+ 树索引的插入性能

B+ 树在插入时就对要对数据进行排序，但排序的开销其实并没有你想象得那么大，因为排序是 CPU 操作（当前一个时钟周期 CPU 能处理上亿指令）。

真正的开销在于 B+ 树索引的维护，保证数据排序，这里存在两种不同数据类型的插入情况。

数据顺序（或逆序）插入：B+ 树索引的维护代价非常小，叶子节点都是从左往右进行插入，比较典型的是自增 ID 的插入、时间的插入（若在自增 ID 上创建索引，时间列上创建索引，则 B+ 树插入通常是比较快的）。

数据无序插入：B+ 树为了维护排序，需要对页进行分裂、旋转等开销较大的操作，另外，即便对于固态硬盘，随机写的性能也不如顺序写，所以磁盘性能也会收到较大影响。比较典型的是用户昵称，每个用户注册时，昵称是随意取的，若在昵称上创建索引，插入是无序的，索引维护需要的开销会比较大。

你不可能要求所有插入的数据都是有序的，因为索引的本身就是用于数据的排序，插入数据都已经是排序的，那么你就不需要 B+ 树索引进行数据查询了。

所以对于 B+ 树索引，在 MySQL 数据库设计中，仅要求主键的索引设计为顺序，比如使用自增，或使用函数 UUID_TO_BIN 排序的 UUID，而不用无序值做主键。

所以，我再次强调：在表结构设计时，主键的设计一定要尽可能地使用顺序值，这样才能保证在海量并发业务场景下的性能。

以上就是索引查询和插入的知识，接下来我们就分析怎么在 MySQL 数据库中查看 B+ 树索引。

22 什么是 Hash索引及底层原理

对于 Hash，大家应该不陌生了，也叫做散列函数，它可以帮助我们大幅度的提升检索数据的效率。很简单的例子，我们去酒店入住，登记完后，想要查找某个人，给前台姐姐报名字，就可以很快查找到对应的信息，如果有同名，这就是hash冲突，后序再说冲突的解决办法。

Hash算法中，相同的输入永远是相同的输出，假设我们要比较两个文件是否一样，不可能叫上一大帮人来核对，当然一大堆人也没法进行核对，这个时候我们可以通过 Hash 函数来计算机文件内容，如果相同，则可以得出两个文件相同。

使用 Python代码

上面不是说了 Hash 的检索效率嘛，我们还是用简单的代码做个实验。

第一个实验是在数组中添加 20000 个元素，然后分别对 20000 个元素检索，左后统计检索的时间

import time
# 插入数据
result = []
for i in range(10000):
    result.append(i)
# 检索数据
time_start=time.time()
for i in range(10000):
    temp = result.index(i)
    time_end=time.time()
print('检索时间', time_end-time_start)

检索时间：1.3433332秒

实验2：采用 Hash 表的形式存储数据，即在 Python 中采用字典方式添加 20000 个元
素，然后检索这 20000 个数据，最后再统计一下时间。代码如下：

import time
# 插入数据
result = {}
for i in range(1000000):
    result[i] = i
# 检索数据
time_start=time.time()
for i in range(20000 ):
    temp = result[i]
    time_end=time.time()
print('检索时间：',time_end-time_start)

检索时间：0.2222543秒

可以发现，采用 Hash 的方式快了确实不少，这是因为 Hash 只需要一步就可以找到相应的值，算法复杂度为 O(1) ，而数组的复杂度为 O(n)。

Mysql中的Hash

采用 Hash进行检索的效率非常高，基本上一次检索就可以找到数据，而对于 B+ 树需要多次的查找，多次的查找过程中就需要多次 IO 操作，从效率而言 Hash 确实比 B+ 树更快，但是我们知道，它不支持范围的查找。键值 key 通过 Hash 映射找到桶 bucket。在这里桶（bucket）指的是一个能存储一条或多条记录的存储单位。一个桶的结构包含了一个内存指针数组，桶中的每行数据都会指向下一行，形成链表结构，当遇到 Hash 冲突时，会在桶中进行键值的查找。那么什么是 Hash 冲突呢？如果桶的空间小于输入的空间，不同的输入可能会映射到同一个桶中，这时就会产生 Hash冲突，如果 Hash 冲突的量很大，就会影响读取的性能。

23 Hash 索引与 B+ 树索引的区别

1. Hash 索引不能进行范围查询，而 B+ 树可以。这是因为 Hash 索引指向的数据是无序的，而 B+ 树的叶子节点是个有序的链表。

2. Hash 索引不支持联合索引的最左侧原则（即联合索引的部分索引无法使用），而 B+ 树可以。对于联合索引来说，Hash 索引在计算 Hash 值的时候是将索引键合并后再一起计算 Hash 值，所以不会针对每个索引单独计算 Hash 值。因此如果用到联合索引的一个或者几个索引时，联合索引无法被利用。

3. Hash 索引不支持 ORDER BY 排序，因为 Hash 索引指向的数据是无序的，因此无法起到排序优化的作用，而 B+ 树索引数据是有序的，可以起到对该字段 ORDER BY 排序优化的作用。同理，我们也无法用 Hash 索引进行模糊查询，而 B+ 树使用 LIKE 进行模糊查询的时候，LIKE 后面前模糊查询（比如 % 开头）的话就可以起到优化作用。

对于等值查询来说，通常 Hash 索引的效率更高，不过也存在一种情况，就是索引列的重复值如果很多，效率就会降低。这是因为遇到 Hash 冲突时，需要遍历桶中的行指针来进行比较，找到查询的关键字，非常耗时。所以，Hash 索引通常不会用到重复值多的列上，比如列为性别、年龄的情况等。

数据库索引的原理，为什么要用B+树，为什么不用二叉树？

可以从几个维度去看这个问题，查询是否够快，效率是否稳定，存储数据多少，以及查找磁盘次数，为什么不是二叉树，为什么不是平衡二叉树，为什么不是B树，而偏偏是B+树呢？

为什么不是一般二叉树？

如果二叉树特殊化为一个链表，相当于全表扫描。平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。

为什么不是平衡二叉树呢？

我们知道，在内存比在磁盘的数据，查询效率快得多。如果树这种数据结构作为索引，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块，但是平衡二叉树可是每个节点只存储一个键值和数据的，如果是B树，可以存储更多的节点数据，树的高度也会降低，因此读取磁盘的次数就降下来啦，查询效率就快啦。

那为什么不是B树而是B+树呢？

1）B+ 树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不仅存储键值，也会存储数据。innodb中页的默认大小是 16 KB，如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数有会再次减少，数据查询的效率也会更快。

2）B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的，链表连着的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。

24 创建高性能索引

索引是提高 MySQL 查询性能的一个重要途径，但过多的索引可能会导致过高的磁盘使用率以及过高的内存占用，从而影响应用程序的整体性能。应当尽量避免事后才想起添加索引，因为事后可能需要监控大量的 SQL 才能定位到问题所在，而且添加索引的时间肯定是远大于初始添加索引所需要的时间，可见索引的添加也是非常有技术含量的。

接下来将向你展示一系列创建高性能索引的策略，以及每条策略其背后的工作原理。但在此之前，先了解与索引相关的一些算法和数据结构，将有助于更好的理解后文的内容。

25 MySQL数据库什么情况下设置了索引但无法使用？

1.如果条件中有or，即使其中有条件带索引也不会使用(这也是为什么尽量少用or的原因)

注意：要想使用or，又想让索引生效，只能将or条件中的每个列都加上索引

2.对于多列索引，不是使用的第一部分，则不会使用索引

3.like查询是以%开头

4.如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引

5.如果mysql估计使用全表扫描要比使用索引快,则不使用索引

查看索引的使用情况：

show status like ‘Handler_read%’

总结

当初复习的内容差不多就到这了，没想到就下班+周末的总结，写了差不多 8 天的时间，内容比较粗糙，如果有不对之处也麻烦大家指出，有点收获也麻烦大家点赞，点在看，谢谢。如需要本文 PDF，后台回复“数据库面试第二期”，我是蓝蓝，我们下期再见！