【MYSQL】MYSQL 的学习教程（五）之 MySQL 索引底层：B+ 树详解

1. 树

树跟数组、链表、堆栈一样，是一种数据结构。它由有限个节点，组成具有层次关系的集合。因为它看起来像一棵树，所以得其名。一颗普通的树如下:

关于树的概念：

• 结点的度：一个结点含有的子结点个数称为该结点的度
• 树的度：一棵树中，最大结点的度称为树的度；
• 父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
• 深度：对于任意结点n,n的深度为从根到n的唯一路径长，根结点的深度为0；
• 高度：对于任意结点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；

2. 树的种类

按照有序性，可以分为有序树和无序树：

• 无序树：树中任意节点的子结点之间没有顺序关系
• 有序树：树中任意节点的子结点之间有顺序关系

按照节点包含子树个数，可以分为 B 树和二叉树，二叉树可以分为以下几种：

• 二叉树：每个节点最多含有两个子树的树称为二叉树；
• 满二叉树：叶节点除外的所有节点均含有两个子树的树被称为满二叉树；

• 完全二叉树：如果一颗二叉树除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布

• 二叉查找树（为了提高查找效率）：首先它是一颗二叉树，若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值；左、右子树也分别为二叉排序树；
  • 红黑树：红黑树是一颗特殊的二叉查找树，每个节点都是黑色或者红色，根节点、叶子节点是黑色。如果一个节点是红色的，则它的子节点必须是黑色的【HashMap 在处理哈希冲突严重时，拉链过长导致查找效率降低，就引入了红黑树】

在最好的情况下，二叉排序树的查找效率比较高，是 O(logn)，其访问性能近似于折半查找；

最差时候会是 O(n)，比如插入的元素是有序的，生成的二叉排序树就是一个链表，这种情况下，需要遍历全部元素才行

• 平衡二叉树（AVL：为了保证树不至于太倾斜，尽量保证两边平衡）：是一种二叉排序树。一 棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。它有几种实现方式：红黑树、AVL树
  • AVL 树：本质上还是一棵二叉搜索树，每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1
    
  • 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。因而，红黑树是相对接近平衡的二叉树，并不是一个完美平衡二叉查找树

• 霍夫曼树：带权路径最短的二叉树

一文带你搞定【二叉树】

3. B- 树、B+ 树简介

先看几个概念：

• 阶数：一个节点最多有多少个孩子节点。（一般用字母m表示）
• 关键字：节点上的数值就是关键字
• 度：一个节点拥有的子节点的数量。

3.1 B-树 简介

B- 树（B树）是一种平衡的多叉树，它比较适用于对外查找

1. 一颗 m 阶的 B- 树，有以下特征：
2. 根结点至少有两个子女；
3. 每个非根节点所包含的关键字个数 j 满足：?m/2? - 1 <= j <= m - 1.(??表示向上取整)
4. 有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。
5. 所有的叶子结点都位于同一层
6. 每个节点既保存索引，又保存数据

3.2 B+ 树简介

B+树是B-树的变体，也是一颗多路搜索树

一棵m阶的B+树主要有这些特点：

1. 每个结点至多有m个子女;
2. 非根节点关键值个数范围：m/2 <= k <= m-1
3. 相邻叶子节点是通过指针连起来的，并且是关键字大小排序的。
4. 只有叶子节点保存数据
5. 增加了相邻接点的指向指针

B+ 树和 B- 树的主要区别如下：

1. B 树的每个节点包含键和对应的值，而 B+ 树的非叶子节点只包含键，所有的值都存储在叶子节点中（其所有叶子结点的数据组合起来就是完整的数据）
2. 由于 B+ 树的叶子节点形成了有序链表，范围查询和顺序遍历操作更加高效。在 B 树中，为了找到满足范围查询的键，需要进行额外的搜索操作
3. 在 B 树中，叶子节点存储了所有的键和对应的值，而在 B+ 树中，叶子节点只存储键和相关值的引用（或指针）。这使得B+树的叶子节点可以容纳更多的键，提高了存储空间的利用率
4. B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同，所以查询速度要比B树更稳定（B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径）
5. B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描
6. B- 树中任何一个关键字出现且只出现在一个结点中，而 B+ 树可以出现多次

3.3 B+ 树的查找

因为 B+ 树的数据都是在叶子节点上的，非叶子节点只是指针索引的作用，因此，查找过程需要搜索到叶子节点上。以这颗 B+ 树为例吧：

3.3.1 B+ 树单值查询

假设我们要查的值为32

第一次磁盘 I/O，查找磁盘块 1，即根节点（36,43），因为 32 小于36，因此访问根节点的左边第一个孩子节点

第二次磁盘 I/O, 查找磁盘块 2，即根节点的第一个孩子节点，获得区间 （28,32），遍历即可得 32

3.3.2 B+ 树范围查询

假设我们要查找区间 [32,40] 区间的值

第一步先访问根节点，发现区间的左端点 32 小于 36,则访问根节点的第一个左子树（28,32）

第二步访问节点（28,32），找到 32，于是开始遍历链表，把 [32,40] 区间值找出来，这也是 B+ 树比 B- 树高效的地方

4. B+ 树经典面试题

4.1 InnoDB一棵 B+ 树可以存放多少行数据？

这个问题的简单回答是：约 2千万 行

• 在计算机中，磁盘存储数据最小单元是扇区，一个扇区的大小是 512 B
• 文件系统中，最小单位是块，一个块大小就是 4 KB
• InnoDB存储引擎最小储存单元是页，一页大小就是 16 KB

因为 B+ 树叶子存的是数据，内部节点存的是键值 + 指针。索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而再去数据页中找到需要的数据；

假设 B+ 树的高度为 2 的话，即有一个根结点和若干个叶子结点。这棵 B+ 树的存放总记录数为 = 根结点指针数 * 单个叶子节点记录行数

• 如果一行记录的数据大小为 1KB，那么单个叶子节点（一页）可以存的记录数 = 16K / 1K = 16
• 非叶子节点内存放多少指针呢？我们假设主键 ID 为 bigint 类型，长度为 8 字节，而指针大小在 InnoD B源码中设置为 6 B，所以就是 8+6 =14 B，16K / 14B = 16 * 1024B / 14B = 1170

因此，一棵高度为 2 的 B+ 树，能存放 1170 * 16=18720 条这样的数据记录。

同理一棵高度为 3 的 B+ 树，能存放 1170 *1170 *16 =21902400，也就是说，可以存放两千万左右的记录。B+ 树高度一般为1-3层，已经满足千万级别的数据存储

4.2 为什么索引结构默认使用 B+ 树，而不是 B-Tree，Hash 哈希，二叉树，红黑树？

• Hash哈希，只适合等值查询，不适合范围查询。
• 一般二叉树，可能会特殊化为一个链表，相当于全表扫描。
• 红黑树，是一种特化的平衡二叉树，MySQL 数据量很大的时候，索引的体积也会很大，内存放不下的而从磁盘读取，树的层次太高的话，读取磁盘的次数就多了。
• B-Tree，叶子节点和非叶子节点都保存数据，相同的数据量，B+树更矮壮，也是就说，相同的数据量，B+树数据结构，查询磁盘的次数会更少