Algorithms and DataStructures:EXSORT 2、外部排序的方法 e.g:平衡3路归并，K=3.2K=6,需4条磁带。六个初始合并段均匀分布在T1、T2 、T3上。每个合并段有1000个记录。T4、T5、T6初始为空。合并过程如下： 初始分布： T: 个 (1.1000) R (3001.4000) T2i R(1001.2000 R(4001.5000) T3: R （2001.3000) R (5001.6000) T4:空 T5:空 T6:空 ·第一趟归并： T:空 T2:空 T3:空 Ta: R(1.3000) T5: R （3001.6000 T6:空 EXST
11 物料管理 EXST 11 Algorithms and DataStructures:EXSORT 2、外部排序的方法 e.g: 平衡 3 路归并， K ＝ 3。 2K = 6, 需 4条磁带。六个初始合并段均匀分布在 T1、T2 、T3上。每个合并段有 1000 个记录。T4、T5 、T6 初始为空。合并过程如下： 初始分布： R（1. 1000） R（3001.4000） R（1001. 2000） R（4001.5000） T1： T2： T4：空 T3 ： R（2001. 3000） R（5001.6000） T5：空 T6：空 • 第一趟归并： R（1. 3000） R（3001.6000） T4： T5： T1：空 T2：空 T3：空 T6：空
Algorithms and DataStructures:EXSORT 2、外部排序的方法 e.g:平衡3路归并，K=3.2K=6,需4条磁带。六个初始合并段均匀分布在T1、T2 、T3上。每个合并段有1000个记录。T4、T5、T6初始为空。合并过程如下： 。第一趟归并： T1:空 T2:空 T3:空 T4: R(1.3000) Ts: R(3001.6000 T6:空 ·第二趟归并： T: (1.6000) T2:空 T3:空 T4:空 Ts:空 T6:空 12 EXST
12 物料管理 EXST 12 Algorithms and DataStructures:EXSORT 2、外部排序的方法 e.g: 平衡 3 路归并， K ＝ 3。 2K = 6, 需 4条磁带。六个初始合并段均匀分布在 T1、T2 、T3上。每个合并段有 1000 个记录。T4、T5 、T6 初始为空。合并过程如下： • 第一趟归并： R（1. 3000） R（3001.6000） T4： T5： T1：空 T2：空 T3：空 T6：空 • 第二趟归并： T1： R（1. 6000） T2：空 T3：空 T4：空 T5：空 T6：空
Algorithms and DataStructures:EXSORT 2、外部排序的方法 ·时间分析： 归并趙数：「1ogkm] where k是路数；m是初始合并段数。在上例中： 「1og261=3而「1og6=2此外，还有一次生成所有合并段的时间。对 文件中的所有的记录全部读写一次。 每一趟归并时，对文件中的所有的记录都要全部读写一次。K大，趟数减 少，读写记录的总数将减少。但K大，需要的内存将越多。 减少初始合并段数，将使趟数减少，读写记录的总数将减少。这就要求在 内存一定且进行内部排序时，生成尽可能长的归并段，从而减少归并段的 总数。 。 输入、输出缓冲区的安排：设进行平衡2路归并，K=2.2K=4,需4条磁带。六个初 始合并段均匀分布在T1、T2。每个合并段有1000个记录。T3、T4初始为空。 R(1.1000) R(2001.2000) R(4001.5001 R（1001.2000) R(3001.4000) R(5001.6000 T3:空 T4:空 13 EXST
13 物料管理 EXST 13 Algorithms and DataStructures:EXSORT 2、外部排序的方法 • 时间分析: 归并趟数: logkm where k 是路数；m 是初始合并段数。 在上例中： log26 = 3 而 log36 = 2 此外，还有一次生成所有合并段的时间。对 文件中的所有的记录全部读写一次。 每一趟归并时，对文件中的所有的记录都要全部读写一次。K 大，趟数减 少，读写记录的总数将减少。但 K 大，需要的内存将越多。 减少初始合并段数 m, 将使趟数减少，读写记录的总数将减少。这就要求在 内存一定且进行内部排序时， 生成尽可能长的归并段，从而减少归并段的 总数。 • 输入、输出缓冲区的安排: 设进行平衡 2 路归并， K ＝ 2。 2K = 4, 需 4条磁带。六个初 始合并段均匀分布在 T1、T2 。每个合并段有 1000 个记录。T3、T4 初始为空。 R（1. 1000） R（2001.2000） R（4001. 5001） R（1001. 2000） R（3001.4000） R（5001. 6000） T1 T2 T3 ：空 T4：空
Algorithms and DataStructures:EXSORT 2、外部排序的方法 输入、输出缓冲区的安排：设进行平衡2路归并，K=2.2K=4,需4条磁带。六个初 始合并段均匀分布在T1、T2。每个合并段有1000个记录。T3、T4初始为空。设每 个物理块包含250个记录，则每个初始合并段包含4个物理块。K路合并，K个输入 输入缓冲区和一个输出缓冲区。 人 R（1.1000) R(2001.2000) R(4001.5001 T3:空 R（1001.2000 R(3001.4000) R(5001.6000 T4:空 初始合并段(R(1.1000)) K(=2)个输入缓冲区 250个记录大 T 250个记录 250个记录 250个记录 250个记录 谜<区地 250个记录大 Tz 250个记录/250个记录 250个记录 250个记录 挞人辽仲 1个输出缓冲区 IBG (Inter Block Gap) 250个记录大 T3 250个记录 即<超艳 14 EXST
14 物料管理 EXST 14 Algorithms and DataStructures:EXSORT 2、外部排序的方法 • 输入、输出缓冲区的安排: 设进行平衡 2 路归并， K ＝ 2。 2K = 4, 需 4条磁带。六个初 始合并段均匀分布在 T1、T2 。每个合并段有 1000 个记录。T3、T4 初始为空。设每 个物理块包含 250 个记录，则每个初始合并段包含 4 个物理块。K 路合并，K 个输入 输入缓冲区和一个输出缓冲区。 R（1. 1000） R（2001.2000） R（4001. 5001） R（1001. 2000） R（3001.4000） R（5001. 6000） T1 T2 T4： 空 T3 ：空 T1 250 个记录 T2 250 个记录 250 个记录 250 个记录 250 个记录 250 个记录 250 个记录 250 个记录 IBG（Inter Block Gap） 初始合并段 ( R（1. 1000）) T3 250 个记录 250 个记录大 250 个记录大 K(＝2)个输入缓冲区 250 个记录大 1个输出缓冲区
Algorithms and DataStructures:EXSORT 3、多路平衡归并的实现 1、带、盘的平衡多路归并的性质： ·时间分析：Togkm]趟 K大，趟数减少，读写记录的总数将减少。但K大，会带来什么问题呢？ ·e.g:K=2时，m个归并串。总共n个记录。 合并段1 合并段2 合并段m-1 合并段m 层数： 中间合并段 中间合并段 「1og2ml+1 归并趟数： I logzml 中间合并段 中间合并段 有序文件 15 EXST
15 物料管理 EXST 15 Algorithms and DataStructures:EXSORT 3、多路平衡归并的实现 • 时间分析: logkm 趟 K 大，趟数减少，读写记录的总数将减少。但 K 大，会带来什么问题呢？ 1、带、盘的平衡多路归并的性质： • e.g: K = 2 时, m 个归并串。总共 n 个记录。 合并段1 合并段2 合并段m-1 合并段m 中间合并段 中间合并段 中间合并段 中间合并段 有序文件 层数： log2m +1 归并趟数： log2m