标签：存储面试 Tree 索引 MySQL 磁盘节点

文章很长，且持续更新，建议收藏起来，慢慢读！疯狂创客圈总目录博客园版 为您奉上珍贵的学习资源：

免费赠送 :《尼恩Java面试宝典》 持续更新+ 史上最全 + 面试必备 2000页+ 面试必备 + 大厂必备 +涨薪必备
免费赠送 :《尼恩技术圣经+高并发系列PDF》 ，帮你实现技术自由，完成职业升级，薪酬猛涨！加尼恩免费领
免费赠送经典图书:《Java高并发核心编程（卷1）加强版》 面试必备 + 大厂必备 +涨薪必备加尼恩免费领
免费赠送经典图书:《Java高并发核心编程（卷2）加强版》 面试必备 + 大厂必备 +涨薪必备加尼恩免费领
免费赠送经典图书:《Java高并发核心编程（卷3）加强版》 面试必备 + 大厂必备 +涨薪必备加尼恩免费领

免费赠送资源宝库： Java 必备百度网盘资源大合集价值>10000元加尼恩领取

阿里面试：为什么要索引？什么是MySQL索引？底层结构是什么？

尼恩特别说明：尼恩的文章，都会在《技术自由圈》公号发布，并且维护最新版本。如果发现图片不可见，请去《技术自由圈》公号查找

尼恩说在前面

在40岁老架构师尼恩的读者交流群(50+)中，最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团、蚂蚁、得物的面试资格，遇到很多很重要的相关面试题：

为什么要有索引？什么是MySQL索引？

MySQL索引底层数据结构是什么？

最近有小伙伴面试阿里，都问到了相关的面试题。 小伙伴没有系统的去梳理和总结，所以支支吾吾的说了几句，面试官不满意，面试挂了。

所以，尼恩给大家做一下系统化、体系化的梳理，使得大家内力猛增，可以充分展示一下大家雄厚的 “技术肌肉”，让面试官爱到 “不能自已、口水直流”，然后实现”offer直提”。

当然，这道面试题，以及参考答案，也会收入咱们的《尼恩Java面试宝典PDF》V175版本，供后面的小伙伴参考，提升大家的 3高架构、设计、开发水平。

《尼恩架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》的PDF，请到文末公号【技术自由圈】获取

为什么要有索引？

索引是一种特殊的数据结构，它就像一本字典的目录，用于帮助MySQL高效地获取数据。

尼恩给大家打个比方：我们翻字典找一个单词的时候，一般都是先翻目录，找到对应的 page 页码，再找到对应的字词。这样我们找到一个字词的时间是1分钟。

我们翻字典找一个单词的时候，没有目录，那么麻烦了：

假如没有目录，我们翻字典得从第一页开始，一页一页扫描，全字典扫描。
假如没有目录，如果是从第一开始翻到第500页找到了，起码也要500分钟。
假如没有目录，如果运气不好，甚至要翻到1000页才找到，需要1000分钟。这种情况下，性能就差了 500倍-1000倍。
从这个例子可见：目录是如此的重要。

mysql 的索引，和书的目录的作用是一样的。

如果 mysql 没有索引，我们查找数据就得全表扫描。

什么是全表扫描？就是从第一个记录开始，一个一个字段、一行一行记录的匹配，一直找到我们需要的数据为止。

所以，没有索引， mysql 的性能会是多么的差。

什么是MySQL索引？

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。

索引可以看作是数据库表中某一列或多列值的排序列表，通过这个列表，数据库系统可以快速找到符合条件的记录，而不需要逐行扫描整个表。

MySQL索引 4的作用：

MySQL 索引的四个作用如下：

1：显著提升查询速度

索引可以显著提高查询速度，尤其是在数据量较大的情况下。

若没有索引，MySQL 在查询时不得不对整个表进行逐行读取，直至找到目标行。

但有了索引后，MySQL 能够直接定位到数据文件中的目标位置，从而有效避免了全表扫描这种耗时的操作。

2. 降低磁盘 I/O 次数

索引能够减少为获取表中某条记录而进行磁盘 I/O 的次数。

借助索引，MySQL 可以迅速定位到数据文件中的相应位置，无需对整个数据集进行读取，这极大地减轻了磁盘 I/O 的负担。

3. 优化排序与分组操作

索引有助于服务器避免进行排序和使用临时表的情况，进而提高查询效率。

在处理排序和分组相关的查询时，索引可以发挥其独特的优势，优化查询执行过程。

4. 提升复杂查询的性能

索引能够对复杂的查询操作提供支持，比如在进行表连接操作，或者查找最大值、最小值等操作时，索引的存在使得这些复杂查询能够更高效地执行。

MySQL索引的类型

MySQL支持多种类型的索引，包括：

主键索引：唯一标识表中的每一行记录。
唯一索引：确保索引列中的所有值都是唯一的。
普通索引：最基本的索引类型，没有唯一性限制。
全文索引：用于全文搜索的索引。
空间数据索引：用于处理空间数据的索引。

MySQL 索引的创建与使用

在MySQL中，可以通过以下语句创建索引：

CREATE INDEX index_name ON table_name (column_name);

例如，创建一个名为 idx_username 的索引在t_user表的username列上：

CREATE INDEX idx_username ON t_user (username);

MySQL 索引的优缺点

MySQL 索引的优点主要有：

1 提高查询效率

在数据量较大的表中，索引能够显著加快查询速度。例如，有一个拥有数百万条用户记录表，如果经常需要根据用户的姓名来查找用户信息，在姓名列上建立索引后，可以通过索引快速定位到包含目标姓名的记录位置，而不是逐行扫描整个表。就像在图书馆找一本书，有了索引（目录）可以快速定位到书籍所在的书架和位置，而不是在整个图书馆的书架中逐一查找。
对于复杂的查询，如多表连接查询，索引也能发挥重要作用。假设我们有一个电商数据库，其中包含 “用户表”“订单表” 和 “商品表”，当查询某个用户购买的特定商品的订单信息时，通过在关联列（如用户 ID、商品 ID 和订单 ID）上建立索引，可以大大加快查询的速度，提高系统的响应性能。

2 优化排序和分组操作

索引可以帮助数据库在执行排序（ORDER BY）和分组（GROUP BY）操作时提高效率。

如果对排序或分组的列建立了索引，数据库可以利用索引的顺序性来避免额外的排序步骤。

例如，在一个员工绩效数据表中，若经常按照绩效得分进行排序，在绩效得分列上建立索引后，数据库在执行排序操作时可以直接使用索引的顺序，减少了排序的时间和资源消耗。

3 减少磁盘 I/O 操作

索引能够引导数据库系统直接定位到需要的数据页，减少了读取无关数据页的磁盘 I/O 操作。

因为磁盘 I/O 是数据库操作中比较耗时的部分，减少磁盘 I/O 次数可以有效提高数据库的整体性能。

以一个存储大量日志信息的表为例，通过在时间戳列上建立索引，当查询特定时间段的日志时，数据库可以通过索引快速定位到对应的日志数据页，而不需要读取整个日志表的数据，从而节省了磁盘 I/O 资源。

MySQL 索引的缺点主要有：

1 增加存储成本

索引本身需要占用一定的存储空间。对于大型数据库表，索引文件可能会变得非常庞大。

例如，一个包含大量文本字段的数据库表，若在多个列上建立索引，索引文件的大小可能会与数据表本身的大小相当，甚至超过数据表的大小。

这就需要额外的磁盘空间来存储索引数据，增加了存储成本。

2 降低写入性能

在对数据表进行插入（INSERT）、更新（UPDATE）和删除（DELETE）操作时，数据库需要同时维护索引的正确性。

例如，每次插入一条新记录时，数据库需要在索引结构中找到合适的位置插入新的索引值；
在更新记录时，如果索引列的值发生了变化，还需要更新索引；
删除记录时，也需要相应地从索引中删除对应的索引项。

这些额外的操作会增加写入操作的时间和资源消耗，从而降低写入性能。

特别是在高并发的写入场景下，频繁地维护索引可能会导致性能瓶颈。

3 可能导致索引失效

索引并不是在所有情况下都能被有效利用。

如果查询条件不符合索引的使用规则，或者数据库的统计信息不准确等情况，可能会导致索引失效。

例如，在查询中使用了函数（如WHERE YEAR(date_column) = 2024）对索引列进行操作，或者在索引列上进行了隐式的数据类型转换，都可能导致索引无法被正确使用，此时数据库会进行全表扫描，反而降低了查询效率。

尼恩提示：索引失效也是面试的重点，下面的面试题，好多小伙伴在面试大厂的时候遇到了：

美团面试：mysql 索引失效？怎么解决？（重点知识，建议收藏，读10遍+）

MySQL索引底层结构

回顾一下咱们的面试题：为什么要有索引？什么是MySQL索引？

针对这个问题，前面内容所介绍的，其实还是 myql 索引的表层知识，回答到这里，可以得到 60分。

如果要得到 100分，甚至120分呢？该当如何？

尼恩告诉大家，这就要对 myql 索引底层知识进行介绍。

myql 索引的底层知识，主要涉及到的是底层的存储结构。

MySQL索引底层结构的2 大核心要求？

尼恩前面讲到：在 MySQL 数据库中，索引通过在数据库表的列上创建有序的数据结构，使得数据库系统能够快速定位到所需的数据，而不需要扫描整个表。索引是帮助数据库系统高效地获取数据的数据结构。

索引由数据库表中的一列或多列组合而成，其内容通常是排好序的一个数据结构。

那么，MySQL 底层的存储结构，应该是那种呢？

首先，来看看 MySQL索引底层结构的2大核心要求：

为什么磁盘 I/O 高性能是核心要求 ?

在数据库系统中，磁盘 I/O 操作通常是性能瓶颈所在。

MySQL 作为一个广泛使用的关系型数据库，需要频繁地从磁盘读取数据和写入数据。

机械硬盘的读写速度，大致如下, 随机读写只有 1 M/s , 顺序读写 100M/s

固态硬盘的读写速度，大致如下, 随机读写只有50 M/s , 顺序读写 200M/s

内存的读写速度，和磁盘读写速度的对比, 最快的情况下，固态硬盘只有内存的100分之一，固态硬盘更差。

当执行查询操作时，比如查找满足某个条件的记录，如果没有高效的磁盘 I/O 机制，数据库可能需要花费大量时间等待数据从磁盘传输到内存中。

例如，对于一个包含大量用户订单信息的数据库，每次查询订单详情都要等待磁盘 I/O 完成，会导致查询响应时间过长，影响用户体验。

为什么范围查找也是核心要求 ?

范围查找是数据库查询中非常常见的操作类型。

例如，在一个销售记录数据库中，可能需要查询某个时间段内的销售数据（如WHERE sales_date BETWEEN '2024-01-01' AND '2024-02-01'），
或者需要查询价格在某个区间内的商品（如WHERE price BETWEEN 100 AND 200）。
总之，对与结构化数据表来说，范围查找操作对于数据分析、报表生成等任务至关重要。

如果索引底层结构不能很好地支持范围查找，那么在处理这类查询时，数据库可能不得不进行全表扫描，这将极大地降低查询效率。

主要数据结构的特性对比

那么，有哪些数据结构，既能满足（1）磁盘 I/O 高性能，又能满足（2）范围查找呢？

咱们一个一个来梳理。

1：二叉树（Binary Tree）

二叉树（Binary Tree）特点：每个节点最多有两个子节点，分别称为左子节点和右子节点。

示例图示：

二叉树是每个节点最多有两个子树的树结构，分为左子树和右子树。

它具有递归的定义，即二叉树的子树本身也是二叉树。

应用场景：二叉树在很多算法和数据处理中都有应用，如表达式解析、决策树等。

2：二叉搜索树（Binary Search Tree，BST）

在二叉树中，节点的排列顺序通常是基于一定的规则，如左子节点的值小于父节点的值，右子节点的值大于父节点的值二叉搜索树的规则。

特点：在二叉树的基础上，满足左子树上所有节点的值均小于它的根节点的值，右子树上所有节点的值均大于它的根节点的值，且左右子树也分别为二叉搜索树。

示例图示：

      8
     / \
    3   10
   / \     \
  2   6     14
     / \    /
    5   7  12

BST中节点的排列顺序通常是基于一定的规则，如左子节点的值小于父节点的值，右子节点的值大于父节点的值（二叉搜索树的规则）。

应用场景：用于高效的查找、插入和删除操作。

BST 不适合作为 MySQL 索引结构的原因

磁盘 I/O 开销大

前面讲到，在数据库中，数据通常存储在磁盘上，频繁的磁盘 I/O 操作是性能瓶颈之一。

二叉树的节点颗粒太小，存储比较分散，当树的高度较高时，查找一个节点可能需要多次磁盘 I/O 操作。

例如，对于一个深度为的二叉树，在最坏情况下，查找一个节点可能需要进行次磁盘 I/O。

如果表中的数据量较大，二叉树的高度会相应增加，导致磁盘 I/O 开销过大，严重影响查询效率。
范围查询效率低

与 B - Tree 等适合索引的结构相比，二叉树在范围查询方面表现不佳。

B - Tree 结构能够利用节点的有序性，通过顺序遍历叶子节点来高效地进行范围查询。

而二叉树在进行范围查询时，由于其结构特点，可能需要多次回溯和遍历不同的子树分支，无法像 B - Tree 那样有效地利用顺序性来快速定位和获取范围内的所有记录。
难以保持平衡

在数据频繁插入和删除的情况下，二叉树很容易失去平衡。一旦失去平衡，其性能会大幅下降。

例如，在一个高并发的数据库环境中，频繁地插入和删除索引对应的记录，二叉树可能会出现一边子树深度远大于另一边的情况，使得查找操作不再具有的时间复杂度，导致查询速度变慢。

例如，在一个简单的二叉搜索树中，插入节点的顺序会影响树的形状。如果按照升序插入节点，可能会导致树的高度很高，形成类似链表的结构，这会使查找操作的时间复杂度退化为o（n）（n 是节点数），而理想的平衡二叉搜索树查找操作时间复杂度是o（logn）。

3：平衡二叉搜索树（AVL 树）

特点：是一种自平衡的二叉搜索树，它在插入和删除节点时通过自动调整树的结构来保持树的高度平衡，左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

示例图示：

      9
     / \
    4   17
   / \    \
  3   6    22
 / \    \    \
2   5    7    20

应用场景：适用于需要频繁进行查找、插入和删除操作且对时间复杂度要求较高的场景，如操作系统中的进程调度等。

AVL 树不适合作为 MySQL 索引结构的原因

磁盘 I/O 操作较多

AVL 树的每个节点只包含两个子节点，这使得树的节点数量相对较多，在存储到磁盘上时会比较分散。在查询过程中，可能需要频繁地进行磁盘 I/O 操作来读取不同的节点。

例如，与 B - Tree 索引相比，B - Tree 的一个节点可以包含多个键值和对应的指针，能够在一次磁盘 I/O 操作中加载更多的信息，减少磁盘 I/O 的总次数。而 AVL 树在这方面的性能相对较弱。
更新操作开销较大

当插入或删除节点时，AVL 树需要进行平衡调整操作，如旋转操作。这些操作涉及到多个节点的修改和重新连接，在数据库环境中，特别是在高并发的情况下，会增加额外的开销。每次更新操作可能需要对多个节点进行读写操作，并且要考虑磁盘 I/O 和内存操作的成本，相比一些更适合数据库索引的结构（如 B - Tree），更新操作的复杂性和开销都较大。

4：红黑树（Red-Black Tree）

结构特点
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶子节点（NIL 节点，空节点）是黑色。
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点。
示例图示（节点旁括号内为颜色标识）：

      (B)15
     /    \
   (R)10   (B)20
  /   \    /   \
(B)8  (B)12 (R)18 (B)25

应用场景：广泛应用于多种编程语言的库中，如 Java 的 TreeMap 和 TreeSet、C++ 的 STL 中的 set 和 map 等，用于实现高效的有序数据存储和检索，在操作系统的进程调度、虚拟内存管理等方面也有应用。

红黑树不适合作为 MySQL 索引结构的原因

磁盘 I/O 操作频繁

红黑树每个节点只有两个子节点，这导致存储相同数量的数据时，红黑树的节点数量相对较多。

在数据库应用中，数据通常存储在磁盘上，而磁盘 I/O 是性能瓶颈之一。

由于红黑树的节点比较分散，在查找或遍历过程中，可能需要更多次的磁盘 I/O 操作。

相比之下，像 B - Tree 这样的索引结构，一个节点可以存储多个键值和指针，能够在一次磁盘 I/O 操作中加载更多的信息，从而有效减少磁盘 I/O 的次数。
存储成本较高

红黑树为了维护自身的性质，需要额外存储每个节点的颜色信息（通常每个节点需要 1 位来表示颜色）。

对于大规模的数据存储，这些额外的存储开销累积起来可能会比较可观。

例如，在一个拥有大量索引数据的 MySQL 表中，这些额外用于存储颜色信息的空间可能会占据一定的磁盘空间，增加存储成本。
更新操作复杂且成本高

在红黑树中，插入和删除节点后，需要进行一系列复杂的调整操作，如颜色变换和旋转操作（左旋、右旋）来维持红黑树的性质。

在高并发的数据库环境下，频繁的更新操作会导致大量的调整操作，这会增加系统的负担。

每次更新操作可能需要对多个节点进行读写操作和复杂的结构调整，这比一些其他索引结构（如 B - Tree）在更新时消耗更多的时间和资源。

5：B 树（B-Tree）

什么是 B-Tree？

多路平衡查找树（每个节点最多 m(m>=2) 个孩子，称为 m 阶或者度）
叶节点具有相同的深度
节点的数据 key 从左到右是递增的

B 树（B-Tree）特点：

每个节点都存储key和data，所有节点组成这棵树，并且叶子节点指针为null。

B树的问题

问题1： B树不支持范围查询的快速查找

如果我们查询一个范围的数据，查找到范围一个边界时，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，即便找到范围的另一个边界，查询效率会降低。

问题2： 每一个节点的data存储的是行记录，树高度较大， IO次数较多

如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。

这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。

B 树（B-Tree）应用场景：

常用于文件系统和数据库系统中，如数据库索引的存储结构，能够有效减少磁盘 I/O 操作，提高数据查询效率。

MyISAM 使用B 树（B-Tree）树作为索引结构，叶子节点的data域存放的是数据记录的地址.

尼恩特别说明：

MyISAM的索引和数据分开存储。

MyISAM 使用B 树（B-Tree）作为索引，标准的B树非叶子节点之前是用于存储 Data 的，但是现在MyISAM 索引中的非叶子节点的 data 没有了。

也就是 MyISAM 索引中的 B 树（B-Tree）高度较小的原因。

MyISAM存储引擎的表, 会把索引信息另外存储到称为索引文件的另一个文件中。

在物理磁盘上，MyISAM选择将索引存储在.MYI文件中，而将真实的数据存储在.MYD文件中。

MyIsAM会单独为表的主键创建一个索引，只不过在索引的叶子节点上，存储的不是数据，而是主键值+数据记录地址的组合。

由于 MyISAM的索引文件仅仅保存记录的地址，所以，在MyISAM中，主键索引与二级索引在结构上没什么区别，只是主键索引要求key是唯一的，而二级索引的key可以重复.

为啥 inno db 不用 B 树（B-Tree）的结构呢？稍后给大家说明。

6：B + 树（B+ Tree）

B + 树（B+ Tree）结构特点

B + 树是 B 树的一种变形，它的非叶子节点不存储实际数据记录，只存储关键字的索引，非叶子节点相当于一个多级索引。
B + 树所有数据记录，都存储在叶子节点上，并且叶子节点之间通过指针连接成一个有序链表。
B + 树（B+ Tree）结构特点与 B 树类似，如节点可以有多个子节点，所有叶子节点在同一层等。

示例图示：

应用场景：在数据库索引中应用极为广泛，例如 MySQL 的 InnoDB 存储引擎就使用 B + 树来实现索引，能够更好地支持范围查询和顺序遍历，同时保持高效的插入、删除和查找性能，减少磁盘 I/O 操作

B+ Tree 索引结构与高性能磁盘 I/O 的关系

B+ Tree 索引（以 InnoDB 为例）

B+ Tree 是一种平衡多路查找树，它的结构特点有助于实现高性能磁盘 I/O。

B+ Tree的节点存储了多个索引键值和对应的指针，这些节点在磁盘上以页（Page）为单位进行存储。

通常一个页的大小是固定的（如 InnoDB 默认页大小为 16KB）。
当查询数据时，数据库首先将根节点所在的页加载到内存中。

由于 B - Tree 的高度相对较低（一般为 3 - 4 层，即使对于非常大的数据量），通过比较索引键值，能够快速定位到下一层节点所在的页，然后将其加载到内存。

这种分层的结构减少了磁盘 I/O 的次数。

例如，对于一个存储了千万级记录的表，通过 B - Tree 索引，可能只需要 3 - 4 次磁盘 I/O 就能定位到目标记录所在的页，相比逐行扫描整个表，大大减少了磁盘 I/O 的开销。

B - Tree 索引对范围查找的支持

非叶子节点是一种多级的有序索引，可以快速定位到范围查找的第一个节点：

B - Tree 索引是一种平衡多路查找树，其节点中的键值是有序排列的。这种有序性使得 B - Tree 索引非常适合支持范围查找。以一个员工表为例，假设在员工年龄列上建立了 B - Tree 索引。当执行查询WHERE age BETWEEN 30 AND 40时，数据库可以从根节点开始，通过比较节点中的年龄键值，快速定位到包含年龄为 30 的记录所在的分支。
叶子节点之间通过指针连接成一个有序链表，可以快速获得范围内的所有记录

由于 B - Tree 索引的顺序性，一旦找到范围的起始位置，就可以沿着叶子节点的链表顺序遍历，获取范围内的所有记录。在这个过程中，不需要重新从根节点开始搜索每一个记录，大大提高了范围查找的效率。例如，在一个存储大量文章的数据库中，对文章发布日期建立 B - Tree 索引后，查找某一时间段内发布的文章就可以利用这种顺序遍历的特性，快速定位到所有符合条件的文章记录。