MySQL数据库——索引结构之B+树

本文先介绍数据结构中树的演化过程，之后介绍为什么MySQL数据库选择了B+树作为索引结构。

树的演化

1. 树

   • 非线性结构，每个节点有唯一的一个父结点和多个子结点（子树），为一对多的关系。

2. 二叉树

   • 每个结点最多有两颗子树，并且子树有左右之分，不能颠倒。

3. 满二叉树

   • 每一层的结点个数都达到了当层能达到的最大结点数。

4. 完全二叉树

   • 除了最下面一层之外，其余层的结点个数都达到了当层能达到的最大结点数，且最下面一层只从左至右连续存在若干结点，右边的结点全部不存在。

5. 二叉查找树 (BST)

   • 又称为二叉排序树、二叉搜索树。
   • 定义：
     1. 要么二叉査找树是一棵空树。
     2. 要么二叉查找树由根结点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，其中：
        • 左子树的所有结点值小于或等于根节点值
        • 右子树的所有结点值大于根节点值。

6. 平衡二叉树 (AVL 树)

   • 特殊的二叉查找树，左右子树都是平衡二叉树，且左右子树高度之差不超过 1。

7. B 树

   • 又名平衡多路查找树。每个节点包含多个数据及指针域，查找路径有多个分支。B-树就是 B 树（别讲什么B减树，‘-’是分隔符）。

8. B+ 树
   在 B 树基础上发展而来的平衡多路查找树，非叶子节点只存储键值和指针，所有数据存储在叶子节点，并通过链表连接。
   优化主要体现在以下几个方面：

   1. 非叶子节点不存储数据，更适合磁盘存储和 I/O 优化
      • B 树：所有节点都存储键值和数据。
      • B+ 树：非叶子节点只存储键值和指针，不存储实际数据，使得内部非叶子节点更小，单个磁盘块可容纳更多键值，减少树的高度和磁盘 I/O 次数，降低树的高度。
   2. 叶子节点存储所有数据，更便于顺序遍历，查找效率稳定
      • B 树：数据分散在各个节点，遍历需要中序遍历整棵树。 查询可能在任何节点结束，查询效率不稳定。
      • B+ 树：所有数据存储在叶子节点，并通过链表连接，范围查询、排序查询更高效，可以快速顺序遍历数据，无需回溯，所有查询最终都在叶子节点结束，查找效率稳定。

为什么其他树结构不行？

磁盘读写的特性：

1. 数据库的索引及数据存储在磁盘中，而不是内存中，磁盘 I/O 的速度远慢于内存。
2. 从磁盘读取数据时，按照磁盘块（页）读取，每次读取的最小单位是一个磁盘块。
3. 若能将更多数据放入一个磁盘块中，一次读取操作可以获取更多数据，从而减少 I/O 次数，提高查询效率。

为什么不使用二叉查找树（BST）？

• 可能出现链表形态：二叉查找树在数据不平衡时可能退化成一条链表，类似于全表扫描，查找时无法发挥二叉排序树的优势。
• 高度过高：树的高度过高时，查找效率变得不稳定，查询需要遍历较多的节点，导致性能下降。

为什么不使用平衡二叉树（AVL树）？

平衡二叉树通过自平衡解决了BST高度过高，查找效率不稳定的问题。但是：

• 节点存储限制：平衡二叉树每个节点只能存储一个键值和数据，对于海量数据，节点数量会非常多，树的高度依然可能较高。
• 效率降低：对于大量数据的存储和查找效率依然不理想，因为节点存储量有限，高度无法有效缩减。

为什么不使用B树？

B树每个节点有更多子节点，减少了树的高度，从而提高了IO性能。解决了平衡二叉树只能存储一个键值和数据的问题。但是：

• 遍历效率低：尽管B树提高了IO性能，但在查找数据时，仍然需要遍历整个树，导致遍历效率低，不同的点查询效率不一样，即查询效率不稳定。

为什么选择 B+ 树

• 二叉查找树：可能退化为链表，查找效率不稳定。
• 平衡二叉树：虽然能保证平衡，但对于海量数据，节点数仍多，高度过高。
• B树：提高了IO性能，解决了平衡二叉树的问题，但遍历效率不足，特别是对于大范围查询。

引入B+树：为了进一步提高遍历效率，B+树在B树的基础上做了优化：

1. B+ 树节点结构

• 非叶子节点仅存储键值，不存储数据，节点更紧凑。
• 数据只存储在叶子节点，叶子节点通过双向链表串联形成线性表。查询时只需要扫描叶子节点，从而大幅提高了范围查询和排序查询的效率。
• 数据库页的大小固定（如 InnoDB 默认 16KB），更高阶数的树更矮更胖，减少了磁盘 I/O 次数。

2. 优点

1. 磁盘读写代价更低：

   • 内部节点不存储数据，节点更小，单个磁盘块可容纳更多键值。
   • 减少树的高度，相同数据量下 I/O 次数更少。

2. 查询效率更加稳定：

   • 查询路径固定，从根节点到叶子节点的路径长度一致，每次查询效率相同。

3. 更便于遍历：

   • 数据全部存储在叶子节点，顺序遍历时只需扫描叶子节点即可。
   • 非叶子节点均为索引，便于范围查询和排序。

4. 更适合范围查询：

   • 叶子节点通过链表连接，直接支持高效的范围查询和排序操作。
   • 在数据库中，基于范围的查询非常频繁，而 B 树不支持或效率较低。

---

举例

磁盘页大小：默认是 16 KB，也就是16,384 字节（1 KB = 1024 字节）。
假设条件：
2. 每个键值的大小：假设每个键值的大小是 16 字节。
3. 每个节点存储的键值数量：每个磁盘页可以存储 1024 个键值。

• 如果一个节点可以存储 1000 个键值时（没有超过1024 个键值），3 层的 B+ 树可以存储约 10 亿条数据。
• 根节点常驻内存，那么查找 10 亿条数据时只需 2 次磁盘 I/O。

---

Q&A

Hash比B+树更快，为什么Mysql用B+树来存储索引呢？

首先在功能上：

• B+树可以进行BETWEEN范围查询，Hash索引不能。
• B+树支持order by排序，Hash索引不支持。
• B+树使用like 进行模糊查询的时候，like后面（比如%开头）的话可以起到优化的作用，Hash索引根本无法进行模糊查询。
• B+树支持 InnoDB、MyISAM 和 Memory，Hash索引仅支持Memory（默认情况）
• B+树支持联合索引的最左侧原则，Hash索引不支持。
• Hash索引在等值查询上比B+树效率更高。

从设计上来看：

• 从内存角度上说，数据库中的索引一般时在磁盘上，数据量大的情况可能无法一次性装入内存，B+树的设计可以允许数据分批加载。
• 从业务场景上说，等值查询那确实是hash更快，但是数据库中经常会进行排序和范围查询，B+树叶子节点通过双向链表串联形成线性表，它的查询效率比hash就快很多了，hash还需要解决冲突。

增加树的路数可以降低树的高度，那么无限增加树的路数是不是可以有最优的查找效率？

答：这样会形成一个有序数组，文件系统和数据库的索引都是存在硬盘上的，并且如果数据量大的话，不一定能一次性加载到内存中。有序数组没法一次性加载进内存，这时候B+树的多路存储威力就出来了，可以每次加载B+树的一个结点，然后一步步往下找。