【数据库】B树、B+树、索引

本系列包含：

• 【数据库】MySQL 的存储引擎
• 【数据库】B 树、B+ 树、索引
• 【数据库】从事务到锁机制
• 【数据库】MySQL 中的锁机制

---

二叉树是二分树，多分树是二叉树的推广。多分树主要适用于静态的索引数据文件，在插入和删除的时候需要把插入位置之后的每个记录都要向后移动，从而导致增加新的索引项和索引页块，需要对外存上的页块进行大量的调整。因此对于经常需要插入和删除的动态索引顺序文件，使用多分树并不合适，需要采用动态索引结构，即 B 树和 B+ 树。

1.B 树

1.1 为什么要引入 B 树

在大规模数据存储的时候，红黑树（一种自平衡二叉查找树）往往出现由于树的深度过大而造成磁盘 IO 读写过于频繁，进而导致效率低下的情况。

为什么会出现这样的情况，我们知道，要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘 IO 代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘 IO 频繁读写。根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构尽量减少树的高度。

换句话说，B 树的出现是为了弥补不同的存储级别之间的访问速度上的巨大差异，实现高效的 I/O。平衡二叉树的查找效率是非常高的，并可以通过降低树的深度来提高查找的效率。但是当数据量非常大，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘 I/O 读写过于频繁，进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B 树是解决这个问题的很好的结构。

根据 B 树节点值有序的特点，每一次只需要将单一节点读入内存，用二分法查找关键值，找到的话返回，没有找到的话则确定区间，将下一个节点从磁盘读入内存继续进行查找即可。这样的设计较好的减小了内外存的数据交互次数，也就较好的减小了时间成本，这就是 B 树存在的意义。

B 树是一种自平衡树，是 AVL 树的一般化，它维护有序数据并允许以对数时间进行搜索，顺序访问，插入和删除。与 AVL 树不同的是，B 树非常适合读取和写入相对较大的数据块（如光盘）的存储系统。它通常用于数据库和文件系统。

1.2 B 树的定义

一颗 $m$ 阶的 $B$ 树满足如下条件：

• 每个节点最多只有 $m$ 个子节点。
• 除根节点外，每个非叶子节点具有至少有 $m/2$（向下取整）个子节点。
• 非叶子节点的根节点至少有两个子节点。
• 有 $k$ 颗子树的非叶节点有 $k-1$ 个键，键按照递增顺序排列。
• 叶节点都在同一层中。

关于B树的几个概念：

• B 树的阶：B 树中一个节点的子节点数目的最大值，用 $m$ 表示。
• 根结点：根节点拥有的子节点数量的上限和内部节点相同，如果根节点不是树中唯一节点的话，至少有两个子节点（不然就变成单支了）。
• 内部结点：内部节点是除叶子节点和根节点之外的所有节点，拥有父节点和子节点。
• 叶子结点：最后一层都为叶子节点。

1.3 B 树的相关操作

B 树的相关操作包括：查找、插入、删除。此处仅简单解释查找的做法。

B 树的查找包含两个基本操作：

• 在B树中找结点；
• 在结点内找关键字。

在B树上找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找。查找到叶结点时（对应指针为空指针），则说明树中没有对应的关键字，查找失败。

由于 B 树常存储在磁盘上，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，所以 B 树中的大部分操作所需的磁盘存取次数与 B 树的高度成正比。

1.4 磁盘 IO 与 B 树

计算机存储设备一般分为两种：内存储器（main memory）和外存储器（external memory）。

内存储器为内存，内存存取速度快，但容量小，价格昂贵，而且不能长期保存数据（在不通电情况下数据会消失）。

外存储器即为磁盘读取，磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分。

• 寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在 5ms 以下；
• 旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘 7200 转，表示每分钟能转 7200 次，也就是说 1 秒钟能转 120 次，旋转延迟就是 1/120/2 = 4.17ms；
• 传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。

那么访问一次磁盘的时间，即一次磁盘 IO 的时间约等于 5+4.17 = 9ms 左右，听起来还挺不错的，但要知道一台 500MIPS 的机器每秒可以执行 5 亿条指令，因为指令依靠的是电的性质，换句话说执行一次 IO 的时间可以执行 40 万条指令，数据库动辄十万百万乃至千万级数据，每次 9 毫秒的时间，显然是个灾难。

考虑到磁盘 IO 是非常高昂的操作，计算机操作系统做了一些优化，当一次 IO 时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为 局部预读性原理 告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次 IO 读取的数据我们称之为一页（page）。具体一页有多大数据跟操作系统有关，一般为 4k 或 8k，也就是我们读取一页内的数据时候，实际上才发生了一次 IO，这个理论对于索引的数据结构设计非常有帮助。

磁盘（ms级别）<< 内存（ns级别），100000 倍。若内存访问需要1s，则一次外存访问需要一天。为了避免 1 次外存访问，宁愿访问内存100次。所以将最常用的数据存储在最快的存储器中。

从以上数据中可以总结出一个道理，索引查询的数据主要受限于硬盘的 I/O 速度，查询 I/O 次数越少，速度越快，所以 B 树的结构才应需求而生；

B 树的每个节点的元素可以视为一次 I/O 读取，树的高度表示最多的 I/O 次数，在相同数量的总元素个数下，每个节点的元素个数越多，高度越低，查询所需的 I/O 次数越少；

假设，一次硬盘 I/O 数据为 8KB，索引用 int（4字节）类型数据建立，理论上一个节点最多可以为 $8KB/4B=2000$ 个元素（方便计算取 2K=2000），$2000\ast 2000\ast 2000=8000000000$，80 亿条的数据只需 3 次 I/O（理论值），可想而知，B 树做为索引的查询效率有多高；另外也可以看出同样的总元素个数，查询效率和树的高度密切相关。

2.B+ 树

2.1 B+ 树的定义

一颗 $m$ 阶的 $B+$ 树满足如下条件：

• 每个节点最多只有 $m$ 个子节点。
• 除根节点外，每个非叶子节点具有至少有 $m/2$（向下取整）个子节点。
• 非叶子节点的根节点至少有两个子节点。
• 有 $k$ 颗子树的非叶节点有 $k$ 个键，键按照递增顺序排列。
• 叶节点都在同一层中。

每个叶节点中至少包含 $m/2$（向下取整）个关键码，所有主文件记录的索引项都存放在 $B+$ 树的叶节点中。所有内部节点都看成是索引的索引。节点中仅包含它的各个子节点中最大（或最小）关键码的分界值以及指向子节点的指针。

2.2 B+ 树的相关操作

B+树的相关操作同样包括：查找、插入、删除。

在 B+ 树中检索关键码的方法与 B 树的检索方式相似，但若在内部节点中找到检索的关键码时，检索并不会结束，要继续找到 B+ 树的叶子结点为止。

2.3 B+ 树为什么比 B 树更适合做索引

（1）B+ 树的磁盘读写代价更低

B+ 树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对 B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说 IO 读写次数也就降低了。

（2）B+树查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

（3）B+树便于范围查询（最重要的原因，范围查找是数据库的常态）

B 树在提高了 IO 性能的同时并没有解决元素遍历的效率低下的问题，正是为了解决这个问题，B+ 树应用而生。B+ 树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而 B 树不支持这样的操作或者说效率太低。

补充：B 树的范围查找用的是中序遍历，而 B+ 树用的是在链表上遍历。

3.MySQL 中的索引

在 MySQL 中，MEMORY 支持 Hash 索引或 B 树索引；而 MyISAM 和 InnoDB 采用的是 B+ 树。

3.1 B+ 树结构

在 B+Tree 有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有的叶子节点（即数据节点）之间是一种链式环结构。因此可以对 B+Tree 进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。（注意理解两个指针的意思）

可能上面例子中只有 22 条数据记录，看不出 B+Tree 的优点，下面做一个推算：

• InnoDB 存储引擎中页的大小为 16KB，
• 一般表的主键类型为 INT（占用 4 个字节）或 BIGINT（占用8个字节），
• 指针类型也一般为 4 或 8 个字节，
• 也就是说一个页（B+Tree 中的一个节点）中大概存储 $16KB/(8B+8B)=1K$ 个键值（因为是估值，为方便计算，这里的 K 取值为 $10^3$）。
• 也就是说一个深度为 3 的 B+Tree 索引可以维护 $10^3\ast 10^3\ast 10^3=10^9$，即 10 亿条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree 的高度一般都在 $2-4$ 层。MySQL 的 InnoDB 存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要 $1-3$ 次磁盘 I/O 操作。

3.2 InnoDB 中的 B+ 树

InnoDB 是通过 B+Tree 结构对主键创建索引，然后叶子节点中存储记录；如果没有主键，那么会选择唯一健；如果没有唯一键，那么会生成一个 6 位的 row.d 来作为主键。

如果创建索引的键是其他字段，那么在叶子节点中存储的是该记录的主键，然后再通主键索引找到对应的记录，叫做回表。

3.3 MyISAM 中的 B+ 树

---

参考资料

1、B 树及其基本操作（查找、插入、删除）
2、B 树和 B+ 树详解
3、B+Tree 索引结构
4、树（六）：B 树与 B+ 树
5、B 树、B+ 树详解