Rookie's blog

Chapter11 外部查找与排序

外部查找与排序

外部查找

B树

设计思想

  • 提供外存中的随机查找
  • 访问磁盘的次数与查找树的高度成正比
  • 增加树的分叉，就能降低树的高度，即采用M叉查找树
  • M叉查找树的最佳高度为：logMNlog_MN
  • 在M叉查找树的基础上考虑平衡，避免退化

概念

  • B树是一棵平衡的M叉查找树，是索引存储中的索引结构M叉查找树
  • 需要保存M-1个关键值来判断到哪个分支查找

定义

一棵 m 阶 B 树或者为空，或者满足以下条件：

  • 根结点要么是叶子，至少有两个儿子，至多有m个儿子

  • 除根结点和叶子结点之外的中间结点，每个结点的儿子个数ss满足 ⌈m2⌉≤s≤m⌈\dfrac{m}{2}⌉ ≤s≤m

  • 有 s 个儿子的非叶结点具有n=s－1n = s － 1个关键字，这些结点的数据信息为

    (n,A0,(K1,R1),A1,(K2,R2),A2,………(Kn,Rn),An)(n, A_0, (K_1, R_1), A_1, (K_2, R_2), A_2, ……… (K_n, R_n), A_n)

  • 所有的叶子结点都出现在同一层上，即它们的深度相同，并且不带信息

B树的插入

  • 与二叉查找树类似，插入总是在最底层
  • 首先在m阶 B 树上进行查找操作，确定新插入的关键字key 在最底层的非叶结点的插入位置，将 key 和记录的存储地址按序插入到最底层上的某个结点。
  • 若被插入结点的关键字个数小于等于m-1, 则插入操作结束；如插入10
  • 若该结点原有的关键字个数已经等于m-1,必须分裂成两个结点。如插入39

B树的删除

  • 类似于二叉查找树的删除操作，同样采用了“替身”的方法，替身为右子树最左面的关键字或左子树最右面的关键字
  • 删除最底层的关键字，有以下几种情况：
    • 若删除关键字之后，结点的关键字的个数满足B树的结点的定义，删除结束。
    • 若删除后关键字个数小于下限：
      • 向结点的左或右兄弟结点借一个关键字过来。
      • 若该结点的左或右兄弟结点的关键字的个数正好为下限 ，则合并结点的操作

B+树

B+树是既能提供随机查找，也能提供顺序访问的存储结构。

定义

B+树是满足某些平衡条件的M叉树。M阶的B+树是具有以下性质的M叉树：

  • 所有数据记录被存贮在叶子中，所有的叶子连成一个单链表。
  • 非叶子结点至多保存M-1个键来引导查找，键i表示子树i+1中键的最小值。
  • 根或者是叶子，或者是有2到M个儿子。
  • 除根之外所有的非叶结点的儿子数为⌈M/2⌉到M之间。这保证了B树不会退化成二叉树。
  • 所有的叶子都在同一层上，并且每个叶子有⌈L/2⌉ 到L个数据项

B+树的插入

  • 叶结点不满：把新结点插入叶子，重新调整该叶子中数据的顺序
  • 叶子已经装满 ：
    • 通过分裂该叶子，形成两个半满的叶子来插入一个新的项 。更新父结点如果父亲的儿子数量已经满了，我们就继续分裂父亲。最坏情况要分裂根。这就是为什么根结点允许只有两个孩子。

B+树的删除

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

外部排序

置换选择排序

image-20240612145612248

多路归并

  • k路归并需要2k条磁带。A1到Ak和B1到Bk。归并数据在A1上
  • 过程：
    • 回绕2k根磁带
    • 归并A1到Ak条磁带上的有序片段轮流放入B1到Bk
    • 回绕所有磁带归并B1到Bk条磁带上的有序片段轮流放入A1到Ak重复上述过程，直到只剩下一个有序片段

多阶段归并

  • 按非均匀的方法分解原先的34个已排序片段。
  • 如果把21个已排序片段放在T2，13个已排序片段放在T3
    • 在T3为空以前我们能够归并13个已排序片段到T1上。然后回绕T1和T3
    • 并将具有13个已排序片段的T1和具有8个已排序片段的T2归并到T3上
    • 然后归并T1和T3
image-20240612150102703
0%