B 树

B 树和 B+ 树都服务于外存查找。内存中的比较次数固然重要，但磁盘或 SSD 随机访问的代价更高，因此索引结构的目标是尽量减少树高，也就是减少访问块的次数。相比二叉树，B 树的每个结点可以包含多个关键字和多个分支，让一次 I/O 带回更多判断信息。

基本性质

  • 多路（m 叉）平衡查找树，一般作为索引。文件系统，数据库系统，外部存储，自底向上生成并维持平衡。
  • B 树或者为空，或者满足：
  • 根结点要么是叶子，要么至少有两个儿子，至多有 mm 个儿子；
  • 除根结点和叶子结点外，每个结点至少有 ⌈m/2⌉\lceil m/2\rceil 个儿子，至多有 mm 个儿子；
  • 有 ss 个儿子的结点有 s−1s - 1 个关键字，这些结点的数据信息为：
  • 关键字按非降序排列，且每个关键字都大于其左边的关键字，小于其右边的关键字；
  • (n, A0, (K1, R1), A1, (K2, R2), ..., An-1, (Kn, Rn), An)，其中 Ki 为关键字，Ri 为数据在硬盘中的地址，A0 指向小于 K1 的子树，Ai 指向位于相邻关键字区间内的子树。
  • 所有的叶子（外部/查找失败）结点都出现在同一层上，即它们的深度相同，并且不带信息。

B 树要放在外存背景下理解。二叉查找树每向下一层通常意味着一次随机访问，而磁盘随机访问很慢；B 树把一个结点做得很大，让一次读盘能带回很多关键字和分支指针。这样树的分叉数 MM 很大，高度就很低，查找时访问的磁盘块数量也随之减少。

插入

  • 插入操作从根结点开始，沿着关键字的顺序向下查找，直到找到合适的叶子结点。
  • 如果叶子结点有空间，则直接插入关键字和数据地址。
  • 如果叶子结点已满，则需要分裂：
  • 将叶子结点分裂成两个结点，并将中间的关键字上升到父结点。
  • 如果父结点也满，则继续向上分裂，直到根结点。
  • 如果根结点分裂，则创建一个新的根结点，树的高度增加 1。

插入时分裂的关键是“中间关键字上升”。一个满结点插入新关键字后会超出容量，于是被拆成左右两个结点，中间关键字交给父结点作为分隔符。若父结点也因此超出容量，分裂会继续向上传播。只有根结点分裂时，整棵树高度才会增加。

删除

  • 类似于二叉查找树，采用替身的方法。
  • 替身取右子树最左边关键字或者左子树最右边关键字。
  • 删除最底层关键字有以下情况：
  • 若删除后满足 B 树定义，删除结束；
  • 若删除后小于下限：
  • 向结点的左或者右兄弟结点借一个关键字；
  • 若左右兄弟结点关键字正好为下限，则合并结点。

删除时处理的是相反问题：某个结点关键字太少，低于下限。若相邻兄弟还有富余关键字，就通过父结点进行“借”；若兄弟也刚好达到下限，就只能与兄弟和父结点中的分隔关键字合并。合并可能让父结点也低于下限，所以删除的修复过程可能继续向上传播。

总结

  • MM 叉 B 树高度大致为 O(log⁡MN)O(\log_M N)。由于每个结点至少半满，严格高度上界可按最小分支数 ⌈M/2⌉\lceil M/2\rceil 估计；
  • B 树结点可扩展（区别于二叉查找树）；
  • 结点中包含数据存储地址。

复习 B 树时可以抓住一个核心：用“结点更宽”换“树更矮”。只要结点大小与磁盘块大小匹配，一次读盘就能完成一个结点内的多次关键字比较，从而把昂贵的随机 I/O 次数压到很低。

B+ 树

  • B 树可以用于随机查找和索引文件；
  • 但是如果需要访问文件的所有记录，时间上是灾难性的；
  • B+ 树是既能提供随机查找，也能提供顺序访问的存储结构。
  • M 阶 B+ 树的特点：
  • 数据记录存储在叶子里；
  • 非叶子结点至多保存 M−1M - 1 个键来引导查找，键 ii 表示子树 i+1i+1 中键的最小值；
  • 根或者是叶子，或者是有 22 到 MM 个儿子；
  • 除根结点和叶子结点外，每个结点至少有 ⌈M/2⌉\lceil M/2\rceil 个儿子，至多有 MM 个儿子，这保证了 B 树不会退化为二叉树；
  • 所有的叶子结点都在同一层上，对于某个 LL 要有 ⌈L/2⌉\lceil L/2\rceil 到 LL 个数据项，并且通过指针相互连接，形成一个链表；

B+ 树与 B 树最大的区别是：真实数据只放在叶子结点，内部结点只做索引导航。这样内部结点能容纳更多关键字，树高更低；同时叶子结点按顺序相连，范围查询时只需要定位到第一个叶子，再沿叶子链表顺序扫描即可。这正是数据库索引偏爱 B+ 树的原因。

插入

  • 叶结点不满：直接插入并调节顺序；
  • 叶结点满：分裂叶结点，将中间关键字上升到父结点；
  • 父结点满则分裂父结点，将中间关键字上升到祖父结点；
  • 最坏情况要分裂根，这就是为什么根结点允许只有两个孩子。

B+ 树插入和 B 树相似，但要注意真实数据记录只在叶子中。叶子分裂后，父结点保存的是用于导航的分隔关键字；叶子之间的顺序链表也要同步维护，否则范围扫描会断开。

删除

  • 删除操作首先查找到要删除的项，然后删除它
  • 如果此时它所在的叶子的元素数量正好满足要求的最小值，删除该项就会使它低于最小值
  • 如果邻居不是最少的情况，就借一个过来领养；
  • 如果邻居也处于最少的情况，就把两个结点合并成一个满的结点。很不幸的是，在这种情况下父亲就失去了一个儿子。如果它引起父亲的儿子数少于了最小值，我们就要使用同样的策略了。这个过程一直向上进行过滤到根。如果在寄养的过程中，根只剩下了一个儿子，就把根删除，让它的儿子作为新的树根，这也是唯一能使 B 树变矮的情况。

L 和 M 的选择

一个数据块存放一个 B+ 树结点能使 IO 效率最高。假设一个数据块的容量 8,1928,192 字节。

  • MM 的选择：如果每个关键字要占用 3232 字节。因此在一棵 MM 阶 B+ 树中，可以有 M−1M - 1 个键，总的数据量就是 32M−3232M - 32 个字节加上 MM 个分支。而且因为每个分支其实是另一个磁盘块的块号，假设分支的大小是 44 个字节。那么分支就要占去 4M4M 个字节。则一个非叶子结点总的内存需要量是 36M−3236M - 32 字节。要求：

36M−32≤819236M - 32 \le 8192

所以 MM 的最大值是 228228，于是选择 M=228M = 228。

  • 假如每条数据记录要 256256 字节，则一个数据块中可以存储：

L=8192256=32L = \frac{8192}{256} = 32

所以 LL 就取为 3232。每个叶子有 1616 到 3232 条数据记录。

外排序

外排序用于处理“数据量大到内存一次放不下”的排序问题。此时算法瓶颈不再是 CPU 比较，而是外存读写次数。典型策略是先把能放入内存的一批数据排成有序归并段，再反复把多个归并段合并，直到得到完整有序文件。

归并排序

外排序中的归并排序与内存归并排序思想相同，都是合并有序序列；区别在于数据分布在外存上，合并时需要为每一路输入和输出安排缓冲区。归并路数越多，归并趟数越少，但每一路都要占用缓冲空间，因此路数受内存大小限制。

预处理：置换选择

将内存中能容纳的一批记录组织成尽可能长的有序初始归并段。置换选择的目标是让初始归并段平均长度大于内存容量，从而减少后续归并趟数。

置换选择可以理解为“边输出当前归并段，边读入新记录”。如果新读入的记录不小于刚刚输出的记录，它还能继续放在当前段；如果更小，就暂时冻结到下一段。这样在随机输入下，一个内存容量为 MM 的工作区往往能产生平均长度接近 2M2M 的初始段，从而减少后续归并压力。

归并：两路/多路/多阶段归并

将多个有序归并段合并成更长的有序段，直到得到完整有序文件。多路归并能减少归并趟数；多阶段归并则通过合理分配各磁带或磁盘上的归并段，减少空跑和拷贝成本。

外排序的核心目标不是减少 CPU 比较次数，而是减少磁盘 I/O 趟数。内存放不下全部数据时，只能先生成若干个内部有序的归并段，再分批合并。归并路数越多，通常需要的合并趟数越少，但每一路都需要输入缓冲区，因此路数受可用内存限制。