厦门大学：《数据结构》课程教学课件（PPT讲稿）第十二章 文件

Algorithms and DataStructures:files 目录 第12章文件 1、基本概念 2、顺序文件 3、索引文件 4、ISAM文件和VSAM文件 5、直接存取文件 6、多关键字文件 File

1 物料管理 File 1 Algorithms and DataStructures:files 1、基本概念 2、顺序文件 3、索引文件 4、ISAM文件和VSAM文件 5、直接存取文件 6、多关键字文件 目录 第 12 章 文 件

Algorithms and DataStructures:files 1、基本概念 1、常用外存： ·磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末 端记录时)。 带文件的读写 时间：To= 原 读出头 入头 接 ta+n X tw ta:延迟时间 盘 tw:传输时间I字符 n字符数。 块1 块2 块3 lBG(Inter Block Gap)块间间隙 File

2 物料管理 File 2 Algorithms and DataStructures:files 1、基本概念 1、常用外存： • 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末 端记录时）。 . . 读 出 头 写 入 原 头 始 盘 接 收 盘 IBG（Inter Block Gap）块间间隙 块 1 块 2 块 3 带文件的读写 时间：T i/o = ta + n × tw ta ：延迟时间 tw：传输时间/ 字符 n 字符数

Algorithms and DataStructures:files 1、基本概念 ·磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。 速度快、容量大、直接存取设备。 种类：固定头磁盘、活动头磁盘 固定头磁盘：每个磁道都有一个磁头（速度快） 活动头磁盘：每个盘面共用一个磁头， 增加了找道的时间，应用广泛。 柱面：各盘面的直径相同的磁道的总和。 物理位置：盘组号、 柱面号、 磁道号、 块（扇区号） 盘文件的读写时间：Tilo=tseck+tia+nX twm tseck:找道时间 ta:等待时间 twm:传输时间/字符，n字符数。 File

3 物料管理 File 3 Algorithms and DataStructures:files 1、基本概念 • 磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。 速度快、容量大、直接存取设备。 种类：固定头磁盘、活动头磁盘 固定头磁盘：每个磁道都有一个磁头（速度快） 活动头磁盘：每个盘面共用一个磁头， 增加了找道的时间，应用广泛。 柱面：各盘面的直径相同的磁道的总和。 物理位置：盘组号、 柱面号、 磁道号、 块（扇区号） 盘文件的读写时间：T i/o = tseck + tla + n×twm tseck ：找道时间 tla ：等待时间 twm ：传输时间/ 字符，n 字符数

Algorithms and DataStructures:files 1、基本概念 2、基本术语： ·数据域（数据场）：记录中的每个数据项，称之为域或场(Field) ·关键字：唯一标识记录的域，称之为关键字。辅助关键字，称之为次关键字。 ·记录(Record)：若干相关的数据项的集合。如果存之于外存，则叫做记录。 ·文件：记录的集合。 ·记录的物理结构和逻辑结构： 逻辑结构：记录在用户或程序员面前呈现的形式。 物理结构：记录在在物理存储器上的存储方式，是数据的物理表示和组织。 ·物理记录和逻辑记录： 物理记录：计算机用一条VO指令进行读写外存的基本单位。通常，对一定 的设备和操作系统，大小是固定不变的。 逻辑记录：程序员加以定义，用户要求使用的。 关系：物理记录><<逻辑记录 File

4 物料管理 File 4 Algorithms and DataStructures:files 1、基本概念 • 数据域（数据场）：记录中的每个数据项，称之为域或场（Field） • 关键字：唯一标识记录的域，称之为关键字。辅助关键字，称之为次关键字。 • 记录（Record）：若干相关的数据项的集合。如果存之于外存，则叫做记录。 • 文件：记录的集合。 • 记录的物理结构和逻辑结构： 逻辑结构：记录在用户或程序员面前呈现的形式。 物理结构：记录在在物理存储器上的存储方式，是数据的物理表示和组织。 • 物理记录和逻辑记录： 物理记录：计算机用一条 I/O 指令进行读写外存的基本单位。通常，对一定 的设备和操作系统，大小是固定不变的。 逻辑记录：程序员加以定义，用户要求使用的。 关系： 物理记录 >>-<< 逻辑记录 2、基本术语：

Algorithms and DataStructures:files 1、基本概念 记录A 记录B 记录 记录C 记录D 话录以 记录c File

5 物料管理 File 5 Algorithms and DataStructures:files 1、基本概念 记录B 记录C 记录D 记录A 记录A 记录B 记录C

Algorithms and DataStructures:files 1、基本概念 3、检索和修改 ·检索： 顺序存取：存取下一个逻辑记录 直接存取：存取第1个逻辑记录 按关键字值存取相应的记录： 简单询问：查单个记录 区域询问：查多个记录 函数询问：满足某种条件的记录 布尔询问：满足布尔运算组合的询问 ·修改：插入、修改、更新 ·更新方式：实时、批量两种方式 6 File

6 物料管理 File 6 Algorithms and DataStructures:files 1、基本概念 • 检索： 顺序存取：存取下一个逻辑记录 直接存取：存取第 i 个逻辑记录 按关键字值存取相应的记录： 简单询问：查单个记录 区域询问：查多个记录 函数询问：满足某种条件的记录 布尔询问：满足布尔运算组合的询问 • 修改：插入、修改、更新 • 更新方式：实时、批量两种方式 3、检索和修改

Algorithms and DataStructures:files 4、1SAM文件和VSAM文件 1、lSAM(Indexed Sequential Access Method)文件 磁道索引 柱面 文件的组织方式： C1 R14R21R45R47R50 50 164 : 330 000.0“。e0 R164 164 溢出区 磁道索引 柱面 620 215 C2 R189 R215 1100 810 R330 330 溢出区 3843 磁道索引 柱面 4150 ◆0◆●ee0◆e年 R3843 Cn 主索引（柱面 组索引) 4150 4150 。0.0。 R4150 柱面索引 溢出区 磁道索引 File

7 物料管理 File 7 Algorithms and DataStructures:files 4、 ISAM文件和VSAM文件 1、ISAM（Indexed Sequential Access Method ） 文件 •文件的组织方式： 磁道索引 R14 R21R45 R47 R50 R164 磁道索引 R189 R215 R330 磁道索引 R3843 R4150 溢出区 溢出区 溢出区 215 50 3843 164 330 4150 164 330 810 4150 620 1100 4150 柱面 C1 柱面 C2 柱面 Cn 主索引（柱面 组索引） 柱面索引 磁道索引

Algorithms and DataStructures:files 4、1SAM文件和VSAM文件 1、ISAM(Indexed Sequential Access Method)文件 ·柱面的安排： 柱面C1 磁道索引项结构 1道 磁道索引 关键字指针 关键字 指针 2 道 基本索引项 溢出索引项 至 基本索引项 18 关键字：本道的最大关 道 键字值 存 指针：本道第一个记 数 录的地址 据 溢出索引项 关键字： 本道的溢出记 录的最大关键 19和20 字值 道存溢 出记录 指 针：本道的溢出记 录的第一个溢 溢出区的设置：1、集中都存在一个公共溢出区内（用多个柱面） 出记录的她址 2、分散每个柱面都有溢出区3、柱面溢出区+公共溢出区 File

8 物料管理 File 8 Algorithms and DataStructures:files 4、 ISAM文件和VSAM文件 1、ISAM（Indexed Sequential Access Method ） 文件 • 柱面的安排： 柱面 C1 1 道 磁道索引 2 道 至 18 道 存 数 据 19和20 道存溢 出记录 关键字 指针 关键字 指针 基本索引项 溢出索引项 磁道索引项结构 基本索引项 关键字：本道的最大关 键字值 指 针：本道第一个记 录的地址 溢出索引项 关键字：本道的溢出记 录的最大关键 字值 指 针：本道的溢出记 录的第一个溢 溢出区的设置：1、集中都存在一个公共溢出区内(用多个柱面) 出记录的地址 2、分散每个柱面都有溢出区 3、柱面溢出区+公共溢出区

Algorithms and DataStructures:files 4、ISAM文件和VSAM文件 ·查找：主索引一>柱面索引一>磁道索引一>磁道的第一个记录. ·插入：R14、R21、R43、R47、R50进入2磁道；R60、R70、R80、R85、R90进入3磁道 柱面C1 2、3磁道的磁道索引项 1道 磁道索引 50 T21 2道 R14 R21 R43 R47 R50 90 T31 3道 R60 R70 R80 R85 R90 19和20 道存溢 9 出记录 File

9 物料管理 File 9 Algorithms and DataStructures:files 4、 ISAM文件和VSAM文件 • 查找：主索引 －> 柱面索引 －> 磁道索引 －> 磁道的第一个记录 . 柱面 C1 1 道 磁道索引 2 道 3 道 19和20 道存溢 出记录 2、3 磁道的磁道索引项 50 T2’ 1 R60 R70 R80 R85 R90 90 T3’ 1 • 插入： R14、R21、R43、R47、R50进入 2 磁道；R60、R70、R80、R85、R90进入3磁道 R14 R21 R43 R47 R50

Algorithms and DataStructures:files 4、ISAM文件和VSAM文件 ·查找：主索引一>柱面索引一>磁道索引一>磁道的第一个记录. ·插入：R30进入2磁道之后。 柱面C1 2、3磁道的磁道索引项 1道 磁道索引 47 T21 50 T191 2道 R14 R21 R30 R43 R47 90 T31 3道 R60 R70 R80 R85 R90 19和20 R50 道存溢 10 出记录 File

10 物料管理 File 10 Algorithms and DataStructures:files 4、 ISAM文件和VSAM文件 • 查找：主索引 －> 柱面索引 －> 磁道索引 －> 磁道的第一个记录 . 柱面 C1 1 道 磁道索引 2 道 3 道 19和20 道存溢 出记录 2、3 磁道的磁道索引项 47 T2’ 1 50 T19’ 1 R60 R70 R80 R85 R90 90 T3’ 1 • 插入： R30 进入 2 磁道之后。 R14 R21 R30 R43 R47 R50 ∧