关于mysql:小面试官教你-MySQL引擎索引和算法

MySQL 引擎、索引和算法

弄懂了 MySQL 的根本 CURD 操作之后，下一个必须把握的常识就是 MySQL 的索引。

我在面试中，常常喜爱针对 MySQL 的常识由浅入深地问上来，理解候选人对 MySQL 常识的理解到了哪一个层级。上一篇文章中的那些常识太根底了，我是不会拿来问的。因而我会问的第一个问题必然是 MySQL 的索引。

对于 MySQL 的索引，我大抵会问上面几个问题：

1. 你晓得 InnoDB 索引所应用的算法是什么吗？
2. 为什么 InnoDB 要应用 B+ 树而不是其余的数据结构呢？
3. 在 InnoDB 中，是不是必须要有主键？如果建表的时候不指定主键会怎么？
4. InnoDB 的主键和索引有什么区别？

要答复这两个问题，咱们须要理解上面几个常识：引擎、索引、树

MySQL 索引的背景常识

MySQL 的引擎

MySQL 在设计之初，就容许嵌入不同的引擎。数据库的外围算法实际上是由引擎来实现的。晚期 MySQL 数据库有以下三个支流引擎：

1. MyISAM: 这是 MySQL 5.5 之前的默认引擎。因为其不反对事务处理，因而在新的零碎中基本上没什么人用了。
2. InnoDB: 这是 MySQL 5.6 以及之后的默认引擎。如果你不晓得应该选什么引擎的话，选它根本没错。
3. Memory: 这是一个非凡的引擎，该引擎存取的数据，全副放在内存中，不会落入磁盘。因而当数据库宕机或重启后，数据就会失落。自从 Redis 衰亡之后，memory 引擎也式微了。

因为新零碎中简直都选用了 InnoDB 引擎，因而下文中如无特地阐明，则指的均为 InnoDB 引擎下的软件原理和行为。

存储系统中的“页”

依照参考资料 1 InnoDB 引擎的要害个性包含以下内容：

1. 插入缓冲（Insert Buffer）
2. 两次写（Double Write）
3. 自适应哈希索引（Adapitve Hash Index）
4. 异步 IO（Async IO）
5. 刷新临接页（Flush Neighbor Page）

能够看到五个个性中，有四个个性是和存储间接相干的。学过计算机组成原理的话就会晓得，计算机存储，依据其与 CPU 的间隔由近到远有以下几个：

1. 寄存器
2. 缓存
3. 内存
4. 硬盘

其中寄存器对于程序员来说个别是不须要关注的；缓存无奈间接在程序中影响和操作。对于绝大部分的计算机程序所操作的存储为内存和硬盘。操作系统读取内存和硬盘的时候，基本上以“页”为单位进行操作的。

为什么须要以“页”为单位操作呢？咱们先看内存：内存其实是齐全能够随机读取的，也就是说 CPU 如果想要读取哪一个地址上的数据，那么一条指令就能够取到。然而应用程序上存取的不是理论内存，而是虚拟内存。而操作系统映射虚拟内存，只能以页为单位进行映射。因而，即使你操作的是内存，还是请盲目尽量对齐页。

重点则是硬盘。硬盘包含两种类型，一种是磁盘，也就是以磁性元件来存储数据的介质；另一种是所谓的 SSD，也就是固态硬盘。对于磁盘的读取原理和过程，我之前写过两篇文章《高性能磁盘 I/O 开发学习笔记 — 硬件原理篇》和《高性能磁盘 I/O 开发学习笔记 — 软件伎俩篇》。简略而言，因为硬件原理的限度，硬盘的读写有以下两个特点：

1. 慢: 磁盘须要转能力转到对应的地位；SSD 好很多，但也比不上内存，毕竟要从长长的总线加载到内存中呢
2. 块: 在软件中应用的 page，在硬件届常常是能够对应到 block。磁盘和 SSD 的数据批改都是以 block 为单位的

索引的原理

MySQL 定位的是大量数据的数据存储。每一个表中存储的数据指标是百万行起跳；数据数据结构较为简单，索引效率高的话，千万也没有问题。理论应用中，也有上亿的场景。这就像一个图书馆，咱们须要对每一本书进行标记和索引，这样在查找书目（数据）时，才可能高效地查问到所须要的数据。

索引的原理，实质上就是解决疾速查找和疾速批改的目标。其次则是解决十分纠结的硬盘写入流程，整个过程中还须要各种避免解体和宕机——毕竟 MySQL 的数据一致性要求是很高的。

作为 MySQL，常常须要关注的数据结构有以下几个：哈希表、B- 树、B+ 树。

哈希表

哈希（hash）算法置信大家都理解了，本文就不赘述。哈希算法的工夫复杂度为 O(1)。在 MySQL 中，前文提到的三个次要引擎只有 Memory 引擎在索引中应用了哈希算法。那为什么其余引擎不是用这个算法呢？因为其余引擎须要思考落地硬盘的问题啊。
哈希的算法尽管简略，然而哈希表在理论利用中须要思考表的扩容和缩容的问题。当哈希表须要扩容 / 缩容的时候，整个表中的所有元素都可能须要重新排列。Memory 引擎是不落磁盘的，不 care。但即使是 Memory，也不适宜存储大量数据。实际上在事实应用中，Memory 的应用场景曾经一直被压缩，大部分曾经被 Redis 所取代了。

B 树

B 树的原理其实相对而言比较简单，它就是一棵树。B 树相比起最根本的树结构来说，比拟特地的就是树的决裂和合并。次要就是在数据库的内容减少和缩小的时候所产生。具体的过程读者能够查阅网上相干的材料，十分多。
B 树的特点是：

• 每一个节点能够多路分叉，不是二叉树。查问效率上比起二叉树而言必定是较弱的。
• 在其每一个节点上都会存储数据

不是 MySQL 的 MongoDB 应用的就是 B 树。那么这里的问题是：为什么采纳 B 树，而不是搜寻效率更高的红黑树呢？（面试考点留神！）

1. 首先，B 树每一个节点是有肯定长度的，在引擎的设计中，会充分利用这一个性，联合前文所提到的“页”，将同一个节点放在同一页中，大大提高硬盘的存取效率
2. 其次，首先，红黑树在插入的过程中，常常会呈现节点的旋转，旋转次数多了之后，可能导致左近的节点扩散散布在硬盘的多个页中。那么在数据落地的时候，就会大大降低效率，并且进步失败的危险

须要留神的是，B 树有时候也被称为 B - 树，然而有些文章中 B 树指的又不是 B - 树，而是二叉树（Binary Tree）。读者在辨认这些用词的时候，要联合上下文辨别。

B+ 树

B+ 树是本文的重点，因为 InnoDB 应用的树结构就是 B + 树。一个 B + 树的示意结构图如下：

看起来和 B 树是很像的，然而实际上有两个十分要害的差别：

1. B 树的数据不仅存在叶子结点中，分支节点也存储。然而 B + 树的数据仅仅存储在叶子结点中，分支节点仅保留索引。如果要查问到数据，那么必须查到叶子结点能力查到。
2. B 树的各个节点之间除了父子关系之外，不会有其余的关系。然而 B + 树的叶子节点之间，还有双向链表相互连接。这一点的益处是，对于设计遍历操作，或者是 offset – limit 的操作，可能大大地进步搜寻效率

InnoDB 索引的分类

前文提到，InnoDB 所应用的算法是 B + 树；B+ 树上的非叶子结点存储的只是数据结构的索引，用于定位子结点用的，而不是“数据库索引”。

那么问题来了：InnoDB B+ 树的叶子结点保留的是什么呢？这就引出了第一个分类：

按存储内容辨别

Clustered Index，中文翻译不一，有“聚簇索引”、“汇集索引”、“聚类索引”等。聚簇索引指的是在叶子结点上，存储的数据就是残缺的 MySQL 的一行数据。

那么在 B + 树的外部，用什么来索引叶子结点呢？答案是主键（main key）。在理论利用中，很大一部分的表在创立的时候都会把第一列定义为 int 或者 bigint 类型，并且指定为 auto increment 类型并设定为主键。这是一个十分通用而且十分保险的做法。咱们分割一下前文 B+ 树的个性就能够发现，如果针对这个自增 ID 间接进行查问、或者是以自增 ID 为条件进行大于、小于等范畴操作，都十分高效。

那么如果在建表的时候不明确指定自增 ID 的话，会怎么呢？B+ 树生效？
对于 MyISAM 引擎来说，主键不是必须的，如果不指定主键，那就没有主键。然而在 InnoDB 中主键是必要的，如果不指定主键的话，那么 InnoDB 会隐含地增加一个 24 位宽的整型 ID 作为主键。但这会导致这个整型 ID 不可见，导致相干的一些操作比方 last inserted id 变得没有意义。因而在实际操作中咱们还是须要显式地指定主键。

对于 InnoDB 来说，聚簇索引能够等同于就是主键的索引。

Secondary Index，中文翻译也不一，有“非聚簇索引”、“辅助索引”、“二级索引”等。在非聚簇索引的叶子结点上，存储的是对应的那一行 MySQL 数据的主键。

如果通过非聚簇索引，也就是除了主键以外的字段查找到了条目之后，此时 InnoDB 仅仅拿到了两个数据：一个是以后节点的索引列的值；另一个是主键。如果客户端还申请了其余数据的话，那么 InnoDB 须要再到以后表的聚簇索引中进行查阅。这个动作称为“回表”查问。

按组成逻辑辨别

依照组成逻辑辨别的话，InnoDB 索引能够分为：

• 主键索引: 这就是前文提到的聚簇索引
• 单列索引: 除了主键之外的非聚簇索引的最简略的模式
• 联结索引: 顾名思义，就是多列的索引
• 惟一索引: 这是单列索引和联结索引的特例，不同的就是在整个表中仅在合乎单列或者多列条件所指定的同一个 / 一组值的数据行，仅容许存在一条

在这里须要特地阐明的是联结索引。笔者之前始终认为联结索引就是索引了一个字段之后，在失去的后果中再对下一个字段进行索引。但起初查阅材料之后才晓得其实并不是。

当创立一个联结索引时，索引中的每一个字段的值，都会在索引的数据结构中呈现。这里我感觉这篇文章讲得曾经十分精确和简要了，读者能够间接参阅。

笼罩索引

“笼罩索引”并不是一种索引的类别，而是一种查问状况。前文提到过，在大部分依照索引进行的查问时，还须要进行回表查问从而失去客户端所须要的其余字段。然而前文也提到，如果你查问的字段，以后的索引曾经齐全笼罩了，那么这个时候 InnoDB 不会再进行多余的回表查问，而是在非聚簇索引查问中就间接把字段返回了。这个景象就称为“笼罩索引”（covering index）。

空间索引

InnoDB 在 5.7.4 labs 版本中开始反对对空间索引的反对。简略而言，咱们平时的索引就是一个纬度的，比方一个数字 x。而空间索引则是对一个空间坐标系的索引，比方 (x, y) 或者是 (x, y, z)。

InnoDB 的索引采纳 R 树，读者感兴趣的话能够参阅相干材料进一步学习。在大部分的利用场景中，如果不波及天文数据的话，空间索引咱们用得还是比拟少的。

答复面试题

好了，后面的面试题，咱们就能够大抵地答复进去了：

参考资料

• MySQL 技术底细 – InnoDB 存储引擎 (第 2 版)
• b 树和 b + 树的区别
• 均衡二叉树、B 树、B+ 树、B* 树 了解其中一种你就都明确了
• 联结索引在 B + 树上的构造
• 联结索引在 B + 树上的存储构造及数据查找形式
• MySQL 索引背地的数据结构及算法原理
• 我认为我对 Mysql 索引很理解，直到我遇到了阿里的面试官
• R 树 – 维基百科，自在的百科全书
• Mysql 空间索引
• 空间索引 – 各数据库空间索引应用报告
• 天文空间数据 Geometry 在 MySQL 中应用（一）

本文章采纳 常识共享署名 - 非商业性应用 - 雷同形式共享 4.0 国内许可协定 进行许可。

原作者：amc，欢送转载，但请注明出处。

原文题目：小面试官教你 MySQL——引擎、索引和算法

公布日期：2020-11-09

原文链接：https://cloud.tencent.com/developer/article/1336510，也是自己的博客