尼恩说在前面

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

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

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

本文目录

- 尼恩说在前面

- 为什么要有索引？

 - 什么是MySQL索引？

 - MySQL索引 4的作用：

- MySQL索引 的类型

 - MySQL 索引的创建与使用

 - MySQL 索引的优缺点

- MySQL索引 底层结构

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

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

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

- 主要 数据结构的 特性对比

- 1：二叉树（Binary Tree）

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

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

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

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

- 4：红黑树（Red-Black Tree）

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

- 5：B 树（B-Tree）

 - B树的问题

- 6：B + 树（B+ Tree）

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

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

- 为啥  inno db 不用 B 树（B-Tree）的结构呢？

- MyISAM、InnoDB 两种存储引擎的区别：

- 尼恩架构团队的塔尖 sql 面试题

为什么要有索引？

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

什么是MySQL索引？

MySQL索引 4的作用：

MySQL索引 的类型

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

MySQL 索引的创建与使用

CREATE INDEX index_name ON table_name (column_name);

CREATE INDEX idx_username ON t_user (username);

MySQL 索引的优缺点

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

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

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

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

MySQL索引 底层结构

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

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

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

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

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

主要 数据结构的 特性对比

1：二叉树（Binary Tree）

      5
     / \
    3   8
   / \   \
  2   4   10

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

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

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 树）

      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

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

• 磁盘 I/O 操作频繁
  红黑树每个节点只有两个子节点，这导致存储相同数量的数据时，红黑树的节点数量相对较多。
  在数据库应用中，数据通常存储在磁盘上，而磁盘 I/O 是性能瓶颈之一。
  由于红黑树的节点比较分散，在查找或遍历过程中，可能需要更多次的磁盘 I/O 操作。
  相比之下，像 B - Tree 这样的索引结构，一个节点可以存储多个键值和指针，能够在一次磁盘 I/O 操作中加载更多的信息，从而有效减少磁盘 I/O 的次数。
• 存储成本较高
  红黑树为了维护自身的性质，需要额外存储每个节点的颜色信息（通常每个节点需要 1 位来表示颜色）。
  对于大规模的数据存储，这些额外的存储开销累积起来可能会比较可观。
  例如，在一个拥有大量索引数据的 MySQL 表中，这些额外用于存储颜色信息的空间可能会占据一定的磁盘空间，增加存储成本。
• 更新操作复杂且成本高
  在红黑树中，插入和删除节点后，需要进行一系列复杂的调整操作，如颜色变换和旋转操作（左旋、右旋）来维持红黑树的性质。
  在高并发的数据库环境下，频繁的更新操作会导致大量的调整操作，这会增加系统的负担。
  每次更新操作可能需要对多个节点进行读写操作和复杂的结构调整，这比一些其他索引结构（如 B - Tree）在更新时消耗更多的时间和资源。

5：B 树（B-Tree）

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

B 树（B-Tree）特点：

B树的问题

尼恩特别说明：

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

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

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

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

6：B + 树（B+ Tree）

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

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

• 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 索引后，查找某一时间段内发布的文章就可以利用这种顺序遍历的特性，快速定位到所有符合条件的文章记录。

为啥 inno db 不用 B 树（B-Tree）的结构呢？

MyISAM、InnoDB 两种存储引擎的区别：

尼恩架构团队的塔尖 sql 面试题

• sql查询语句的执行流程：

• 索引下推 ?

• 索引失效

• MVCC

• binlog、redolog、undo log

• mysql 事务

空窗8月：中厂大龄34岁，被裁8月收一大厂offer， 年薪65W，转架构后逆天改命!

空窗2年：42岁被裁2年，天快塌了，急救1个月，拿到开发经理offer，起死回生

空窗半年：35岁被裁6个月， 职业绝望，转架构急救上岸，DDD和3高项目太重要了

空窗1.5年：失业15个月，学习40天拿offer， 绝境翻盘，如何实现？