Part9 外排序(2025.6.7)
1.B树
基本性质
- 多路（m叉）平衡查找树，一般作为索引。文件系统，数据库系统，外部存储，自底向上生成并维持平衡。
- B树或者为空，或者满足：
- 根结点要么是叶子，要么至少有两个儿子，至多有m个儿子；
- 除根结点和叶子结点外，每个结点至少有⌈m/2⌉个儿子，至多有m个儿子；
- 有s个儿子的结点有n = s - 1个关键字，这些结点的数据信息为：
- 关键字按非降序排列，且每个关键字都大于其左边的关键字，小于其右边的关键字；
(n, A0, (K1, R1), A1, (K2, R2), ..., An-1, (Kn, Rn), An)，其中Ki为关键字，Ri为数据在硬盘中的地址，A0为小于K1结点的地址,Ai为指向数据记录的指针。
- 关键字按非降序排列，且每个关键字都大于其左边的关键字，小于其右边的关键字；
- 所有的叶子（外部/查找失败）结点都出现在同一层上，即它们的深度相同，并且不带信息。
插入
- 插入操作从根结点开始，沿着关键字的顺序向下查找，直到找到合适的叶子结点。
- 如果叶子结点有空间，则直接插入关键字和数据地址。
- 如果叶子结点已满，则需要分裂：
- 将叶子结点分裂成两个结点，并将中间的关键字上升到父结点。
- 如果父结点也满，则继续向上分裂，直到根结点。
- 如果根结点分裂，则创建一个新的根结点，树的高度增加1。
删除
- 类似于二叉查找树，采用替身的方法。
- 替身取右子树最左边关键字或者左子树最右边关键字。
- 删除最底层关键字有以下情况：
- 若删除后满足B树定义，删除结束；
- 若删除后小于下限：
- 向结点的左或者右兄弟结点借一个关键字；
- 若左右兄弟结点关键字正好为下限，则合并结点。
总结
- M叉B树高度为log(M, N);
- B树结点可扩展（区别于二叉查找树）；
- 结点中包含数据存储地址。
2.B+树
- B树可以用于随机查找和索引文件；
- 但是如果需要访问文件的所有记录，时间上是灾难性的；
- B+树是既能提供随机查找，也能提供顺序访问的存储结构。
- M阶B+树的特点：
- 数据记录存储在叶子里；
- 非叶子结点至多保存M-1个键来引导查找，键i表示树i+1中键的最小值；
- 根或者是叶子，或者是有2到M个儿子；
- 除根结点和叶子结点外，每个结点至少有⌈M/2⌉个儿子，至多有M个儿子，这保证了B树不会退化为二叉树；
- 所有的叶子结点都在同一层上，对于某个L要有⌈L/2⌉到L个数据项，并且通过指针相互连接，形成一个链表；
插入
- 叶结点不满：直接插入并调节顺序；
- 叶结点满：分裂叶结点，将中间关键字上升到父结点；
- 父结点满则分裂父结点，将中间关键字上升到祖父结点；
- 最坏情况要分裂根，这就是为什么根结点允许只有两个孩子。
删除
- 删除操作首先查找到要删除的项，然后删除它
- 如果此时它所在的叶子的元素数量正好满足要求的最小值，删除该项就会使它低于最小值
- 如果邻居不是最少的情况，就借一个过来领养；
- 如果邻居也处于最少的情况，就把两个结点合并成一个满的结点。很不幸的是，在这种情况下父亲就失去了一个儿子。如果它引起父亲的儿子数少于了最小值，我们就要使用同样的策略了。这个过程一直向上进行过滤到根。如果在寄养的过程中，根只剩下了一个儿子，就把根删除，让它的儿子作为新的树根，这也是唯一能使B树变矮的情况。
3.L和M的选择
一个数据块存放一个B+树结点能使IO效率最高。假设一个数据块的容量8,192字节
- M的选择：如果每个关键字要占用32字节。因此在一棵M阶B+树中，可以有M-1个键，总的数据量就是32M-32个字节加上M个分支。而且因为每个分支其实是另一个磁盘块的块号，假设分支的大小是4个字节。那么分支就要占去4M个字节。则一个非叶子结点总的内存需要量是36M-32字节。要36M-32不超过8,192的M的最大值是228，于是选择 M=228。
- 假如每条数据记录要256字节，则一个数据块中可以存储32条记录，所以L就取为32。每个叶子有16到32条数据记录。