CMU15-445 数据库系统播客：B+树索引 - 结构与优化
B+ 树的核心特性
B+ 树是一种 M-way 搜索树，它通过一系列精巧的设计，实现了在对数时间复杂度 内完成查找、范围扫描、插入和删除操作。其关键特性如下：
- 高度平衡与多路设计 ：B+ 树是完美平衡的，所有叶子节点都处于相同的深度。这保证了查询性能的稳定性。同时，它是一个“多路”树，意味着每个内部节点可以拥有多个子节点（最多 M 个），这使得树的高度非常低，从而显著减少了从磁盘读取数据块（Node）的次数，这对于磁盘I/O是主要瓶颈的系统至关重要。
- 有序性与范围查询 ：B+ 树内部的所有节点中的键都保持有序存储。它的叶子节点之间通过指针串联，形成一个有序链表。这一特性使得 B+ 树不仅擅长单点查找，还极为高效地支持范围查询。当需要查找一个范围的数据时，DBMS 只需定位到范围的起始叶子节点，然后通过叶子节点间的指针顺序向后遍历即可。
- 节点功能分离
- 内部节点 ：仅存储“路由”信息，即用于导向的键（Keys）和指向下一层节点的指针（Pointers）。它们不存储具体的数据值，唯一的任务就是“指路”。
- 叶子节点 ：存储了索引的键以及对应的值。这个“值”通常有两种实现方式。
记录标识 (Record IDs) ：值是指向表中实际数据行物理位置的指针。这是 PostgreSQL 等数据库采用的方式，有时被称为“非聚簇索引”。
元组数据 (Tuple Data) ：值直接就是数据行的完整内容。MySQL 的 InnoDB 存储引擎的主键索引就是这样实现的，称为“聚簇索引”。在这种模式下，二级索引的叶子节点存储的则是主键的值，因此通过二级索引查找数据时，需要先找到主键，再通过主键索引找到完整数据，这个过程即为“回表”。
插入与删除操作
B+ 树的自平衡特性是通过其插入和删除算法实现的。
插入
- 首先，查找到应该插入新键的叶子节点 L。
- 将新条目按序插入 L。
- 如果 L 还有空间，操作完成。如果 L 已满，则需要进行 分裂 ：将 L 分裂成两个节点 L 和 L2，并将原节点中的一半条目移动到新节点 L2 中。同时，将 L2 的第一个键（即中间键）复制并提升（Copy Up）到父节点中，以作为指向 L2 的路标。
- 如果父节点也因此变满，分裂过程会向上传递，最坏情况下可能一直传递到根节点，导致树的高度增加一层。
删除
- 首先，查找到包含该键的叶子节点 L 并移除条目。
- 如果 L 在删除后所含的键数量仍然满足要求（通常是至少半满），则操作完成。
- 如果 L 的键数量低于阈值，系统会尝试从相邻的兄弟节点“借”一个键来进行 重新分配 (Redistribution) 。
- 如果兄弟节点也没有富余的键可借，则会将 L 与其兄弟节点进行 合并 (Merge) 。 合并后，父节点中指向被合并节点的键也需要被删除，这个过程同样可能向上传递。
B+ 树的设计考量
1. 节点大小 (Node Size)
节点大小是一个关键的设计决策。传统上，对于机械硬盘（HDD），节点大小倾向于设置得更大（如几 MB）。这是因为 HDD 的寻道时间很长，随机读写性能差。通过一次读取一个大的数据块，可以将这次昂贵的 I/O 成本分摊到更多的键值对上，从而提高效率。
而对于固态硬盘（SSD），其随机读写性能远超 HDD。因此，节点大小的设计有了不同的考量。虽然一次读取更大块仍然有优势，但过大的节点也存在弊端。较小的节点（如几十或几百 KB）有以下好处：
- 缓存效率更高 ：更小的节点意味着在有限的内存（Buffer Pool）中可以缓存更多的节点，从而提高缓存命中率。
- 更新成本更低 ：当一个节点需要被修改（分裂或合并）时，需要加锁并写入磁盘。节点越小，锁定的粒度越小，写入的数据量也越少，这在高并发写入场景下可以减少争用并提升性能。
- 减少内部碎片 ：对于变长键，小节点能更灵活地适应，减少节点内的空间浪费。
2. 变长键的处理
当索引的键是变长的字符串时，直接存储会使节点内布局变得复杂。最常见的处理方法是采用类似“页槽”（Slotted Page）的机制，也称为 键位图 (Key Map) 。节点内部会维护一个指针数组，每个指针指向一个键值对的实际存储位置。这种方式可以高效地管理节点内的可变空间。
3. 非唯一索引
如果索引列的值不唯一，B+ 树有两种处理方式：
- 存储重复键 ：直接在叶子节点中多次存储相同的键。
- 值列表 ：每个键只存储一次，但其对应的值是一个包含所有重复条目记录ID的链表或集合。
4. 节点内查找策略
在一个节点内部快速定位键也至关重要。常见方法包括：
- 线性扫描 ：从头到尾依次比较，简单但对有序性没有要求。
- 二分查找 ：要求节点内键有序，通过在中间点不断分割查找范围来快速定位。
- 插值查找 ：基于节点内键的分布来预测目标键可能的位置，然后从该位置开始线性扫描，也要求键有序。
B+ 树的优化技术
为了进一步提升性能和空间效率，现代 B+ 树实现中还包含了很多高级优化：
- 前缀压缩 (Prefix Compression) ：在叶子节点中，相邻的键通常有相同的前缀。通过只存储它们的共同前缀一次，然后为每个键存储其独特的后缀，可以显著节省存储空间。
- 后缀截断 (Suffix Truncation) ：内部节点的键只用于“指路”，因此不需要存储完整的键。只需存储能够区分左右子树的最短前缀即可。例如，如果要区分 "Apple" 和 "Apply"，在内部节点中可能只需要存储 "Appli" 就足够了。
- 批量加载 (Bulk Loading) ：当需要为一张已有大量数据的大表创建新索引时，逐条插入的效率很低，因为会触发大量的节点分裂和重组。最高效的方式是先将所有键进行排序，然后从底层开始自底向上地构建 B+ 树。这样可以一次性确定每层节点的布局，完全避免了分裂和合并操作，速度快得多。
- 指针旋转 (Pointer Swizzling) ：这是一个更高级的内存管理技术，可以简单理解为：当一个磁盘上的节点被读入内存时，其内部存储的磁盘地址（Disk Pointers）会被转换成内存地址（Memory Pointers）。这样，在内存中对树进行遍历时，就可以直接通过内存地址访问子节点，避免了将磁盘地址转换回内存地址的开销，从而加快速度。当节点被写回磁盘时，内存指针又会被“反向旋转”回磁盘地址。
通过这些精心设计和优化的特性，B+ 树成为了支撑现代高性能数据库不可或缺的基石。
