Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： ·带文件的组织的改进： 块 块2 块3 IBG(Inter Block Gap)块间间隙 IBG:.5~.75inch,带来的好处是什么？ 每一块是一个物理记录，包含若干个逻辑记录。 B.F(块因子)=一个物理记录包含逻辑记录的个数 带的利用率上升，如上例： 设B.F=100 1000/100 X 0.6 6 inch total IBG 1000×80/800=100inch(file)利用率=100/106=94.3% EXST
6 物料管理 EXST 6 Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： • 带文件的组织的改进： 块 1 块 2 块 3 IBG（Inter Block Gap）块间间隙 IBG：.5~.75 inch，带来的好处是什么？ 每一块是一个物理记录，包含若干个逻辑记录。 B.F（块因子） ＝ 一个物理记录包含逻辑记录的个数 带的利用率上升，如上例： 设 B.F = 100 1000 /100 × 0.6 ＝ 6 inch ( total IBG ) 1000 × 80/800 ＝ 100 inch ( file) 利用率＝ 100/106 = 94.3 %
Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： ·磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。 速度快、容量大、直接存取设备。 ·种类：固定头磁盘、活动头磁盘 固定头磁盘：每个磁道都有一个磁头（速度快) 活动头磁盘：每个盘面共用一个磁头， 增加了找道的时间，应用广泛。 ·柱面：各盘面的直径相同的磁道的总和。 ·物理位置：盘组号、若干个磁盘构成一组，系统可能有许 多组。 柱面号、 磁道号、 块（扇区号） ·盘文件的读写时间：Tlo=tseck+tia+n X twm tseck:找道时间 tia:等待时间 twm：传输时间/字符，n记录数。 EXST
7 物料管理 EXST 7 Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： • 磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。 速度快、容量大、直接存取设备。 • 种类：固定头磁盘、活动头磁盘 固定头磁盘：每个磁道都有一个磁头（速度快） 活动头磁盘：每个盘面共用一个磁头， 增加了找道的时间，应用广泛。 • 柱面：各盘面的直径相同的磁道的总和。 • 物理位置：盘组号、若干个磁盘构成一组，系统可能有许 多组。 柱面号、 磁道号、 块（扇区号） • 盘文件的读写时间：T i/o = tseck + tla + n×twm tseck ：找道时间 tla ：等待时间 twm ：传输时间/ 字符，n 记录数
Algorithms and DataStructures:EXSORT 2、外部排序的方法 1、步骤： ·生成合并段(un)：读入文件的部分记录到内存一>在内存中进行内部排序一> 将排好序的这些记录写入外存，形成合并段一>再读入该文件 的下面的记录，往复进行，直至文件中的记录全部形成合并段 为止。7、15、198、11、1316、23、315、12 ·外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文 件。 ·平衡合并分类法：被合并的初始合并段均匀分布在K条磁带上，即分布在T1、T2、 .Tk上。对这K条带进行合并，将生成的中间归并段分布在 TK+1小TK+2、.T2K上。然后，循环往复，直至最后形成一个 单一的合并段为止。 e.g:平衡2路归并，K=2.2K=4,需4条磁带。六个初始合并段均匀分布在T1、T2 上。每个合并段有1000个记录。T3、T4初始为空。合并过程如下： 初始分布：T1 R(1.1000) R(2001.2000) R(40015001 T2 R(1001.20000 R(3001.4000) R(5001.6000 T3:空 T4:空 EXST
8 物料管理 EXST 8 Algorithms and DataStructures:EXSORT 2、外部排序的方法 1、步骤： • 生成合并段（run）：读入文件的部分记录到内存 －> 在内存中进行内部排序 －> 将排好序的这些记录写入外存，形成合并段 －> 再读入该文件 的下面的记录，往复进行，直至文件中的记录全部形成合并段 为止。 • 外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文 件。 • 平衡合并分类法：被合并的初始合并段均匀分布在 K 条磁带上，即分布在 T1、T2、 . Tk 上。对这 K 条带进行合并，将生成的中间归并段分布在 TK+1、 TK+2 、. T2K 上。然后，循环往复，直至最后形成一个 单一的合并段为止。 e.g: 平衡 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：空 7、15、19 8、11、13 16、23、31 5、12
Algorithms and DataStructures:EXSORT 2、外部排序的方法 初始分布： R(1.1000) R(2001.3000) R(4001.5000} T2 R(1001.2000 R(3001.4000) R(5001.6000 T3:空 T4:空 ·第一趟归并： T:空 T2:空 T3: R(1.2000) R(4001.6000) T4: R （2001.4000) 9 EXST
9 物料管理 EXST 9 Algorithms and DataStructures:EXSORT 2、外部排序的方法 • 初始分布： R（1. 1000） R（2001.3000） R（4001. 5000） R（1001. 2000） R（3001.4000） R（5001. 6000） T1 T2 T4：空 T3 ：空 • 第一趟归并： T1 ：空 T2 ：空 T3 ： T4： R（1. 2000） R（4001.6000） R（2001. 4000）
Algorithms and DataStructures:EXSORT 2、外部排序的方法 第二趟归并： T1: R(1.4000) T2 (4001.60000 T3:空 T4:空 ·第三趟归并： T1:空 T2:空 Tg: R(1.6000) T4:空 10 EXST
10 物料管理 EXST 10 Algorithms and DataStructures:EXSORT 2、外部排序的方法 • 第二趟归并： T3 ：空 T4 ：空 T1 ： T2： R（1. 4000） R（4001. 6000） • 第三趟归并： T3 ： T4 ：空 T1 ：空 T2：空 R（1. 6000）