B 树在数据库

本文目录导读：

1. 核心矛盾：内存快，磁盘慢
2. B树的精髓：矮胖多路
3. B树在数据库中的具体工作方式
4. B树 vs. B+树：谁才是数据库之王？
5. 总结：为什么数据库最终选择了B+树？

这是一个非常核心且经典的问题。B树（及其变体B+树）是现代关系型数据库（如MySQL、PostgreSQL）和许多NoSQL数据库中最广泛使用的索引数据结构。

数据库之所以选择B树,是因为它完美平衡了磁盘I/O、查询速度和数据修改（插入/删除）的需求。

下面我们从最底层的逻辑出发,深入探讨B树在数据库中的应用。

核心矛盾：内存快，磁盘慢

数据库数据通常存储在磁盘上,磁盘访问（I/O）的速度比内存访问慢了几个数量级（毫秒级 vs 纳秒级）。

• 二叉搜索树（BST）：虽然查询复杂度是O(log n)，但树很高，如果有100万条数据，树高约20层，最坏情况下，查询一条数据需要从根节点访问20次磁盘，每次访问都可能花费10毫秒，总共200毫秒，非常慢。
• 哈希表：查询速度极快（O(1)），但不支持范围查询（如WHERE age > 20），也无法利用索引进行排序。

数据库需要一种数据结构,既能高效地进行单点查询和范围查询，又能大幅减少磁盘I/O次数，B树就是为了解决这个问题而生的。

B树的精髓：矮胖多路

B树的关键在于“多路” 和“矮胖”。

• 多路：传统二叉树的“路”是2（每个节点最多有两个子节点），B树的每个节点可以存储多个键值和多个子节点指针（称为“阶”或M），一个M=100的B树，每个节点可以存储最多100个键。
• 矮胖：因为每个节点能存储多个键，树的高度（层数）被极大地压缩了。

举个例子： 假设一个B树的阶是100（即每节点最多99个键）。

• 第1层（根节点）：可容纳 99 个键。
• 第2层：99 * 100 = 9900 个键。
• 第3层：9900 * 100 = 990,000 个键。
• 第4层：990,000 * 100 = 99,000,000 个键。

在大多数实际场景中，一个索引的B树高度仅为3-4层，这意味着，无论你有多少亿条数据，查找一个键最多只需要进行3-4次磁盘I/O，速度极快。

B树在数据库中的具体工作方式

节点 = 数据页（Disk Page）

数据库的存储引擎（如MySQL的InnoDB）会将磁盘空间划分为固定大小的数据页（通常是16KB），B树的每个节点正好对应一个数据页，当从磁盘加载数据时，是一次性加载整个页面。

查询过程（单点查询）

假设我们有一个students表，id是主键，我们执行SELECT * FROM students WHERE id = 103;

1. 加载根节点：从磁盘加载根节点所在的数据页到内存。
2. 内部节点搜索：在根节点内部，使用二分查找（或顺序查找）找到103应该落入的子节点范围（50-150之间）。
3. 加载子节点：根据指针，将子节点的数据页从磁盘加载到内存。
4. 重复：继续在子节点中查找，直到找到叶子节点。
5. 叶子节点：叶子节点包含了id=103对应的行的完整数据或指向该行数据的指针，读取数据。

整个过程,磁盘I/O次数等于树的高度，通常为3-4次。

范围查询（范围扫描）

这是B树优于哈希表的关键。SELECT * FROM students WHERE id > 100 AND id < 200;

1. 按单点查询方式找到第一个满足条件的键（id=101）。
2. 利用叶子节点之间的链表（InnoDB的B+树特性），顺序向后遍历，直到遇到超出范围的键（id=200）。

这个过程非常高效,因为它利用了磁盘顺序读取的优势。

插入与删除（维护平衡）

插入或删除数据时,B树可能会变得“不平衡”，为了保证性能稳定，B树有一套分裂和合并机制。

• 分裂：当向一个已满的节点插入新键时，该节点会分裂成两个节点，并将中位数键提升到父节点，这个过程可能会向上传播，甚至使树的高度增加。
• 合并：删除键导致节点太稀疏（键太少）时，可能会与相邻兄弟节点合并。

代价：插入/删除可能引起多次磁盘写操作（因为要修改多个节点），但总体上依然是O(log n) 级别的复杂度。

B树 vs. B+树：谁才是数据库之王？

一个重要的事实： 大多数现代关系型数据库（如MySQL的InnoDB引擎）实际使用的是B+树，而不是经典的B树。

为什么B+树更适合数据库？

1. 更大的扇出（更矮的树）：内部节点不存数据，可以容纳更多的键和子节点指针，假设16KB的页面，存储100个B+树索引键（约80字节/键）绰绰有余，而存储B树数据则可能只能存3-5行，扇出越大，树越矮，I/O越少。
2. 更稳定的查询性能：在B树中，数据可能出现在任何节点，查询时间从一个常量到树高不等，在B+树中，所有数据都在叶子节点，因此任何查询访问的I/O次数都等于树的高度，完全稳定。
3. 范围查询的绝对优势：叶子节点之间的链表将数据串联起来，使得“全表扫描”和“范围扫描”变成顺序读取磁盘，速度极快，这在B树中很难实现。

为什么数据库最终选择了B+树？

1. 极致的磁盘I/O优化：通过使用“数据页”作为节点，将树的高度控制在3-4层，任何查询最多只需几次磁盘读取。
2. 支持高效的范围查询和排序：这是SQL语言最常用的操作之一，B+树的叶子节点链表完美实现了这一点。
3. 稳定的性能：无论查询主键的哪个值，代价都相同。
4. 自平衡：插入和删除操作会自动维护树的结构平衡，确保性能不会退化。
5. 写优化：虽然写操作会涉及分裂/合并，但依然是对数级的，且磁盘顺序写（日志先行）的配合使其在实际中非常高效。

一句话概括： 数据库面临的瓶颈是磁盘I/O，B（+）树通过“多路”结构压缩了树的高度，让每一次磁盘I/O都能访问到尽可能多的数据，从而用最少的I/O次数完成查询，并同时完美支持了SQL语言最核心的范围查询能力。