1. MySQL 索引

• MySQL 的数据是持久化的，意味着数据（索引+记录）是保存到磁盘上的，因为这样即使设备断电了，数据也不会丢失。

• 设计存储的时候，不单单要从数据结构的角度出发，还要考虑磁盘 I/O 操作次数。
  • 内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的；
  • 也就是说读取同样大小的数据，磁盘中读取的速度比从内存中读取的速度要慢上万倍，甚至几十万倍；
• 磁盘读写的最小单位是扇区，扇区的大小只有 512B 大小，操作系统一次会读写多个扇区，操作系统的最小读写单位是块（Block）。
  • Linux 中的块大小为 4KB；
  • 也就是一次磁盘 I/O 操作会直接读写 8 个扇区；
• 由于数据库的索引是保存到磁盘上的，因此当我们通过索引查找某行数据的时候，就需要先从磁盘读取索引到内存，再通过索引从磁盘中找到某行数据，然后读入到内存；
  • 也就是说查询过程中会发生多次磁盘 I/O；
  • 而磁盘 I/O 次数越多，所消耗的时间也就越大；
• 索引的数据结构，要能在尽可能少的磁盘的 I/O 操作中完成查询工作；
  • 因为磁盘 I/O 操作越少，所消耗的时间也就越小。
• MySQL 支持范围查找
  • 索引的数据结构不仅要能高效地查询某一个记录，而且也要能高效地执行范围查找。

2. 二叉树

• 二叉查找树的特点是：
  • 节点左子树的所有节点、都小于这个节点；
  • 节点右子树的所有节点、都大于这个节点
  • 这样我们在查询数据时，不需要计算中间节点的位置了，只需将查找的数据与节点的数据进行比较。
• 二叉树解决了插入新节点的问题：
  • 因为二叉查找树是一个跳跃结构，不必连续排列；
  • 这样，在插入的时候，新节点可以放在任何位置，不会像线性结构那样插入一个元素，所有元素都需要向后排列。

3. 平衡二叉树

• 二叉查找树存在一个极端情况：

  • 当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)。

    

• 为了解决在极端情况下退化成链表的问题，后面就有人提出平衡二叉树（AVL 树）。

• 平衡二叉树主要是在二叉查找树的基础上，增加了一些条件约束：
  • 每个节点的左子树和右子树的高度差不能超过 1；

  • 也就是说，节点的左子树和右子树仍然为平衡二叉树，这样查询操作的时间复杂度就会一直维持在 O(logn) 。

    

4. 三叉树

• 随着插入的元素增多，平衡二叉树的高度变高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。
• 比如：

  • 下面这个平衡二叉查找树的高度为 5，那么在访问最底部的节点时，就需要磁盘 5 次 I/O 操作。

    

  • 原因是因为它们都是二叉树，也就是每个节点只能保存 2 个子节点，如果我们把二叉树改成 M 叉树（M>2）呢？

• 比如：

  • 当 M=3 时，在同样的节点个数情况下，三叉树比二叉树的树高要矮。

    

5. B 树

• 平衡二叉树不足：
  • 平衡二叉树虽然能保持查询操作的时间复杂度在O(logn)，但是因为它本质上是一个二叉树，每个节点只能有 2 个子节点；
  • 当节点个数越多的时候，树的高度也会相应变高，这样就会增加磁盘的 I/O 次数，从而影响数据查询的效率。
• B 数概念：
  • 为了解决降低树的高度的问题，后面就出来了 B 树，它不再限制一个节点就只能有 2 个子节点，而是允许 M 个子节点 (M>2)，从而降低树的高度。
  • B 树的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶，所以 B 树就是一个多叉树。
  • 假设 M = 3，那么就是一棵 3 阶的 B 树，特点就是每个节点最多有 2 个（M-1个）数据和最多有 3 个（M个）子节点，超过这些要求的话，就会分裂节点，

• 比如：下面的的动图：

  

  • 可以看到：
    • 一棵 3 阶的 B 树在查询叶子节点中的数据时，由于树的高度是 3 ，所以在查询过程中会发生 3 次磁盘 I/O 操作。
    • 而如果同样的节点数量，在平衡二叉树的场景下，树的高度就会很高，意味着磁盘 I/O 操作会更多。所以，B 树在数据查询中比平衡二叉树效率要高。

6. B+ 树

• B 数的不足：

  • B 树的每个节点都包含数据（索引+记录），而用户的记录数据的大小、很有可能远远超过了索引数据，这就需要花费更多的磁盘 I/O 操作次数来读到有用的索引数据。

  • 而且，在我们查询位于底层的某个节点（比如 A 记录）过程中，非 A 记录节点里的记录数据会从磁盘加载到内存，但是这些记录数据是没用的，我们只是想读取这些节点的索引数据来做比较查询，而非 A 记录节点里的记录数据对我们是没用的，这样不仅增多磁盘 I/O 操作次数，也占用内存资源。

  • 另外，如果使用 B 树来做范围查询的话，需要使用中序遍历，这会涉及多个节点的磁盘 I/O 问题，从而导致整体速度下降。

    

  • 这个时候，就需要使用到 B+ 树；

• B+ 树的特点：
  • B+ 树一个节点存储多个元素，可以使得树高不会太高；
  • MySQL 中一个 Innodb 页就是一个 B+ 树节点，一个 Innodb 页默认为 16kb；
  • 一般情况下，一颗两层的 B+ 树可以存 2000万 行左右的数据；
  • B+ 树叶子节点存储全部数据，叶子结点之间有指针，可以很好的支持全表扫描、范围查找等 SQL 操作；
• MySQL 默认的存储引擎 InnoDB 采用的是 B+ 作为索引的数据结构，原因有：
  • B+ 树的非叶子节点不存放实际的记录数据，仅存放索引；
    • 因此，数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+ 树的非叶子节点可以存放更多的索引；
    • 因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少。
  • B+ 树有大量的冗余节点（所有非叶子节点都是冗余索引）；
    • 这些冗余索引让 B+ 树在插入、删除的效率都更高；
    • 比如：
      • 删除根节点的时候，不会像 B 树那样会发生复杂的树的变化；
  • B+ 树叶子节点之间用链表连接了起来，有利于范围查询；
    • 而 B 树要实现范围查询，因此只能通过树的遍历来完成范围查询；
    • 这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。

7. B+ 树与 B 树差异的点

• 主要差异点：
  • B+ 树叶子节点（最底部的节点）才会存放实际数据（索引+记录），非叶子节点只会存放索引；
  • B+ 树所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；
  • B+ 树非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）值。
  • B+ 树非叶子节点中有多少个子节点，就有多少个索引；

• Previous
  MySQL 5.7 与 8.0 的对比分析
• Next
  MySQL 存储过程概念及实例