Algorithms and DataStructures:EXSORT 目录 第11章外部排序 1、外存信息的存取 2、外部排序的方法 3、多路平衡归并的实现 4、置换-选择排序 5、最佳归并树 EXST
1 物料管理 EXST 1 Algorithms and DataStructures:EXSORT 1、外存信息的存取 2、外部排序的方法 3、多路平衡归并的实现 4、置换-选择排序 5、最佳归并树 目录 第 11 章 外部排序
Algorithms and DataStructures:EXSORT 1、外存信息的存取 1、外部排序： 内部排序：信息一次可全部调入内存，信息在内存中的处理时间是主要的时间耗费。 外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘、CD-ROM上。特点 为内存运行时间短，内、外存进行交换需要时间长。减少O时间成为主 要矛盾。 2、基本术语： ·记录(Record):数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记 录。原因起源于是在历史上研究管理应用和计算机科学的两部分人 员的习惯。 ·域（场）：记录中的每个数据项，称之为域(Field)。 ·文件：记录的集合。 ·关键字：唯一标识记录的域，称之为关键字。 ·有序文件：文件根据关键字的大小。排成递增或递减的序列。 3、常用外存： ·磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度幔。 2 EXST
2 物料管理 EXST 2 Algorithms and DataStructures:EXSORT 1、外存信息的存取 1、外部排序： 内部排序：信息一次可全部调入内存，信息在内存中的处理时间是主要的时间耗费。 外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘、CD-ROM 上。特点 为内存运行时间短，内、外存进行交换需要时间长。减少 I/O 时间成为主 要矛盾。 • 记录（Record）：数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记 录。原因起源于是在历史上研究管理应用和计算机科学的两部分人 员的习惯。 • 域（场）：记录中的每个数据项，称之为域（Field） 。 • 文件：记录的集合。 • 关键字：唯一标识记录的域，称之为关键字。 • 有序文件：文件根据关键字的大小。排成递增或递减的序列。 2、基本术语： 3、常用外存： • 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度幔
Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： ·磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度慢。 ·带信息的表示： 一种磁化方向、代表1 ↓另一种磁化方向，代表0 N 01001001 10101111 EXST
3 物料管理 EXST 3 Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： • 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度慢。 • 带信息的表示： 一种磁化方向、代表1 另一种磁化方向，代表0 01001001 10101111
Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： ·磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度慢（尤其是查找末端记录时）。 磁带机走向 原 出头 入头 接收盘 ·带文件的组织： 记录1 记录2 记录3 IRG(Inter Record Gap)记录间隙 EXST
4 物料管理 EXST 4 Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： • 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度慢（尤其是查找末端记录时）。 . . 磁带机走向 读 出 头 写 入 原 头 始 盘 接 收 盘 • 带文件的组织： 记录 1 记录 2 记录 3 IRG（Inter Record Gap）记录间隙
Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： 读写头 ·带文件的组织： 记录1 记录2 记录3 可靠读写区 IRG(Inter Record Gap)记录间隙 IRG:.5~.75inch,带来的问题是什么？ 带的利用率下降，如： 密度800 byte per inch的带。设每个记录有80byte ,共1000个记录。如果，RG=.6inch;带的利用率？ 1000×(80/800)=100inch(filel) 1000 X 0.6 600 inch total IRG) 利用率=17=14%必须改进带的利用率！ ·带文件的读写时间：To=ta+nXtw ta延迟时间：读写头到达相应的物理块的起始位置的时间。 tw读/写一个字符的时间；n记录数。 EXST
5 物料管理 EXST 5 Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： • 带文件的组织： 记录 1 记录 2 记录 3 IRG（Inter Record Gap）记录间隙 v t 可靠读写区 IRG：.5~.75 inch，带来的问题是什么？ 带的利用率下降，如： 密度 800 byte per inch 的带。设每个记录有 80 byte ，共 1000 个记录。如果， IRG＝ .6 inch ; 带的利用率？ 1000 × (80/800) ＝ 100 inch ( filel ) 1000 × 0.6 ＝ 600 inch ( total IRG) 利用率＝ 1/7= 14 % 必须改进带的利用率 ! • 带文件的读写时间：T i/o = ta + n×tw ta 延迟时间：读写头到达相应的物理块的起始位置的时间。 tw 读/写一个字符的时间； n 记录数。 读写头