Q: 我看你简历上写了 MySQL,对 MySQL InnoDB 引擎的索引了解吗?

A: 使用索引可以加快查询速度,其实就是将无序的数据变成有序,有序之后就能加快检索速度了。在 InnoDB 引擎中,索引的底层数据结构是 B+树。

Q: 那为什么不使用红黑树或者B树呢?

A: MySQL 的数据是存储在硬盘上的,在查询数据时,一般是不能一次性把全部数据都加载到内存中的。红黑树是二叉搜索树的一种变种,一个 Node 节点只能存储一个 Key 和一个 Value 值。B树和 B+ 树和红黑树有所不同,他们都是多路搜索树。相较于二叉搜索树,多路搜索树一个 Node 节点可以存储的信息会更多,多路搜索树的高度会比二叉搜索树更低。了解了他们之间的区别之后,其实就很容易发现,在数据不能一次性加载到内存的场景下,数据需要被检索出来。选择 B 树或者 B+ 树的理由就很充分了,Node 节点存储更多信息,树的高度更低,因此检索速度也就更快。

B+ 树相对于 B 树而言,它又有两个特性:

  • B+ 树非叶子节点不存储数据,在相同的数据量下,B+树更加矮壮。数据够存储在叶子结点上,非叶子节点可以存储更多的索引值,所以整棵树就更加矮壮。
  • B+ 树叶子结点之间组成一个链表,方便于遍历查询,遍历操作在 MySQL 中比较常见。

我们在 MySQL InnoDB 引擎下,每创建一个索引,相当于生成了一棵 B+ 树。如果该索引是聚簇索引,那么当前 B+ 树的叶子结点存储着主键和当前行的数据。如果该索引是非聚簇索引,那么当前 B+ 树的叶子结点存储着主键和当前索引列值。

比如写了一句 SQL:

select * from user where id >= 10;

那么只要定位到 id 为 10 的记录,然后再叶子结点之间通过遍历链表(叶子结点组成的链表),即可找到往后的记录了。

由于 B 树是会在非叶子节点中存储数据,要遍历的时候可能就得跨层检索了,相对会麻烦很多。基于树的层级一级业务使用场景的特性,所以 MySQL 选了 B+ 树作为索引的底层数据结构。

对于哈希结构,其实 InnoDB 引擎是自适应哈希索引的,也即 hash 索引的创建由 InnoDB 存储引擎自动优化创建,我们无法干预。

Q: 那我了解了,顺便想问下,你知道什么叫做回表吗?

A: 所谓的回表其实就是,当我们使用非聚簇索引查询数据时,检索出来的数据可能包含其他列。但此时所走的索引树的叶子结点中只能查到主键 ID 以及当前列值,所以需要根据主键 ID 再去聚簇索引中查询一遍,得到 SQL 所需的列值。

举个例子,我这边给订单号 ID 建立索引,但我的 SQL 如下:

select orderId, orderName from orderdetail where orderId = 123

SQL 走订单 ID 索引,但在订单 ID 的索引树的叶子节点中只有 orderId 和 Id,并没有 orderName。此时我们想要检索出 orderName,MySQL 引擎就会拿着 Id 再去回表查出 orderName 返回给我们,这种操作就叫做回表。

如何避免回表,可以使用覆盖索引。所谓覆盖索引,就是你所想要查询的字段刚好索引树的叶子节点中都存在。比如我创建一个 orderId 和 orderName 的联合索引,此时刚好我需要查询 orderId 和 orderName 字段信息,这些数据都存储在索引树的叶子节点中,所以此时就不需要再回表了。

Q: 既然你也提到了联合索引,我想问你了解最左匹配原则吗?

A: 先匹配最左边的,索引只能用于查找 key 是否存在(相等),遇到范围查询(> 、<、between、like 左匹配)等就不能进一步匹配了,后续就会退化为线性查找,这就是最左匹配原则。

Q: 我还想问下你们主键是怎么生成的?

A: 主键就自增的

Q: 假设不用 MySQL 自增的主键,你觉得会有什么问题?


A: 首先主键需要保证唯一性以及所占空间尽可能小。另外,由于索引的特性是有序,如果生成类似 uuid 这样的主键,那么插入的性能是比自增主键要差很多的。因为生成的 uuid 具有无序性,在插入的时候可能需要移动磁盘块。比如块内的空间在当前时刻已经满了,但新生成的 uuid 需要插入到这块满的内存块中,那么就需要移动磁盘块中的数据了。

Last modification:June 20th, 2021 at 03:00 pm
如果觉得我的文章对你有用,请随意赞赏