01数据结构讲义09第12章文件组织

1、1 物料管理物料管理File1Algorithms and DataStructures:files1、基本概念、基本概念2、顺序文件、顺序文件3、索引文件、索引文件4、ISAM文件和文件和VSAM文件文件5、直接存取文件、直接存取文件6、多关键字文件、多关键字文件目录目录第第 12 章章 文文 件件2 物料管理物料管理File2Algorithms and DataStructures:files1、基本概念、基本概念1、常用外存：、常用外存： 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存

2、取设备。查找费时、速度慢（尤其是查找末便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末 端记录时）。端记录时）。.读读出出头头写写入入头头原原始始盘盘接接收收盘盘IBG（Inter Block Gap）块间块间间隙间隙块块 1块块 3块块 2带文件的读写带文件的读写时间：时间：T i/o = ta + n tw ta ：延迟时间：延迟时间 tw：传输时间：传输时间/ 字符字符 n 字符字符数。数。3 物料管理物料管理File3Algorithms and DataStructures:files1、基本概念、基本概念 磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）

3、、旋转主轴构成。磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。 速度快、容量大、直接存取设备。速度快、容量大、直接存取设备。 种类：固定头磁盘、活动头磁盘种类：固定头磁盘、活动头磁盘 固定头磁盘：每个磁道都有一个磁头（速度快）固定头磁盘：每个磁道都有一个磁头（速度快） 活动头磁盘：每个盘面共用一个磁头，活动头磁盘：每个盘面共用一个磁头， 增加了找道的时间，应用广泛。增加了找道的时间，应用广泛。 柱面：各盘面的直径相同的磁道的总和。柱面：各盘面的直径相同的磁道的总和。 物理位置：盘组号、物理位置：盘组号、 柱面号、柱面号、 磁道号、磁道号、 块（扇区号）块（扇区号） 盘

4、文件的读写时间：盘文件的读写时间：T i/o = tseck + tla + ntwm tseck ：找道时间：找道时间tla ：等待时间：等待时间twm ：传输时间：传输时间/ 字符，字符，n 字符数。字符数。4 物料管理物料管理File4Algorithms and DataStructures:files1、基本概念、基本概念 数据域（数据场）：记录中的每个数据项，称之为域或场（数据域（数据场）：记录中的每个数据项，称之为域或场（Field） 关键字：唯一标识记录的域，称之为关键字。辅助关键字，称之为次关键字。关键字：唯一标识记录的域，称之为关键字。辅助关键字，称之为次关键字。 记录（记

5、录（Record）：）：若干相关的若干相关的数据项的集合。如果存之于外存，则叫做记录。数据项的集合。如果存之于外存，则叫做记录。 文件：记录的集合。文件：记录的集合。 记录的物理结构和逻辑结构：记录的物理结构和逻辑结构： 逻辑结构：记录在用户或程序员面前呈现的形式。逻辑结构：记录在用户或程序员面前呈现的形式。 物理结构：记录在在物理存储器上的存储方式，是数据的物理表示和组织。物理结构：记录在在物理存储器上的存储方式，是数据的物理表示和组织。 物理记录和逻辑记录：物理记录和逻辑记录： 物理记录：计算机用一条物理记录：计算机用一条 I/O 指令进行读写外存的基本单位。通常，对一定指令进行读写外存的

6、基本单位。通常，对一定 的设备和操作系统，大小是固定不变的。的设备和操作系统，大小是固定不变的。 逻辑记录：程序员加以定义，用户要求使用的。逻辑记录：程序员加以定义，用户要求使用的。 关系：关系： 物理记录物理记录 - 逻辑记录逻辑记录2、基本术语：、基本术语：5 物料管理物料管理File5Algorithms and DataStructures:files1、基本概念、基本概念记录记录B记录记录C记录记录D记录记录A记录记录A记录记录B记录记录C6 物料管理物料管理File6Algorithms and DataStructures:files1、基本概念、基本概念 检索：检索： 顺序存取

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

8、文件、顺序文件n顺序文件的特点：顺序文件的特点：在顺序文件中，所有逻辑记录在存储介质中的实际顺序与它们在顺序文件中，所有逻辑记录在存储介质中的实际顺序与它们进入存储器的顺序一致。进入存储器的顺序一致。顺序文件的主要优点是顺序存取速度块，适宜于顺序存取和成顺序文件的主要优点是顺序存取速度块，适宜于顺序存取和成批处理。批处理。顺序文件的缺点是不利于修改。顺序文件的缺点是不利于修改。顺序文件特别适应于磁带存储器，也适应于磁盘存储。顺序文件特别适应于磁带存储器，也适应于磁盘存储。提示：顺序文件是指按记录写入文件的先后顺序存放、提示：顺序文件是指按记录写入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文

9、件。顺序文件可分为顺其逻辑顺序和物理顺序一致的文件。顺序文件可分为顺序有序文件和顺序无序文件两种。序有序文件和顺序无序文件两种。8 物料管理物料管理File8Algorithms and DataStructures:files2、顺序文件、顺序文件 顺序存取是指按记录的逻辑(或物理)顺序实现逐个存取，若要查询第i个记录则必须先检索前 i1 个记录；插入新的记录只能加在文件的末尾；更新某个记录必须对整个文件进行复制。顺序文件的修改操作是按批处理的方式进行的。批处理的工作原理如下进行：称待修改的原始文件为主文件，文件中记录按关键码有序；所有的修改请求依请求的先后次序生成一个事务文件，在进行批处理

10、之前首先对事务文件进行排序，然后和主文件归并得到一个新的主文件，如右图所示。9 物料管理物料管理File9Algorithms and DataStructures:files3、索引文件和多关键字文件、索引文件和多关键字文件n 一、索引文件n索引文件：是索引方法与链接方法相结合的一种组织方式，它包括数据文件和索引表n数据文件：记录结构为n索引表：按关键字范围建立的分段索引，结点结构为n ，其中关键字是该范围内最大关键字的值，指针是最小关键字的始地址数据 指针关键字 指针10 物料管理物料管理File10Algorithms and DataStructures:files3、索引文件和多关键

11、字文件、索引文件和多关键字文件 职职 工号工号姓姓 名名职职 务务性性 别别工工 资资指指 针针10029王王 平平讲讲 师师男男50510410105李李 林林教教 授授女女87010610202魏魏 黎黎讲讲 师师男男49710110338徐徐 萍萍助助 教教女女38110510431李李 新新教教 授授男男119010910543孙孙 玉玉讲讲 师师男男51310710617郭郭 燕燕讲讲 师师女女52210810746朱朱 文文助助 教教女女39710823张张 萌萌教教 授授男男93010010935常常 平平讲讲 师师女女505103以这个数据文件为例以这个数据文件为例11 物料管

12、理物料管理File11Algorithms and DataStructures:files3、索引文件和多关键字文件、索引文件和多关键字文件 索引表是对该数据文件按索引表是对该数据文件按0019，2039，4059建立的分段索建立的分段索引引02关键字指针1939591021081050517 2329313538 4346 12 物料管理物料管理File12Algorithms and DataStructures:files3、索引文件和多关键字文件、索引文件和多关键字文件n在索引链接文件中查找关键字为k的记录方法：n 在索引表中确定待查记录所在的索引段。n 顺着该段的链查找待查记录。n

13、例如查找的主关键字为3102关键字指针1939591021081050517 2329313538 4346 1931 柱面索引柱面索引 磁道索引磁道索引 磁道的第一个记录磁道的第一个记录 柱面柱面 C1磁道索引磁道索引 1 道道2 道道3 道道19和和20道存溢道存溢出记录出记录 2、3 磁道的磁道索引项磁道的磁道索引项50 T2 1 R60 R70 R80 R85 R9090 T3 1 插入：插入： R14、R21、R43、R47、R50进入进入 2 磁道；磁道；R60、R70、R80、R85、R90进入进入3磁道磁道R14 R21 R43 R47 R5018 道道 注意：基本区：采用顺序

14、结构。注意：基本区：采用顺序结构。 溢出区：采用链接结构。溢出区：采用链接结构。26 物料管理物料管理File26Algorithms and DataStructures:files4、 ISAM文件和文件和VSAM文件文件 查找：主索引查找：主索引 柱面索引柱面索引 磁道索引磁道索引 磁道的第一个记录磁道的第一个记录 柱面柱面 C1磁道索引磁道索引 1 道道2 道道3 道道19和和20道存溢道存溢出记录出记录 2、3 磁道的磁道索引项磁道的磁道索引项47 T2 1 50 T19 1 R60 R70 R80 R85 R9090 T3 1 插入：插入： R30 进入进入 2 磁道之后。磁道之后

15、。R14 R21 R30 R43 R47R50 27 物料管理物料管理File27Algorithms and DataStructures:files4、 ISAM文件和文件和VSAM文件文件 查找：主索引查找：主索引 柱面索引柱面索引 磁道索引磁道索引 磁道的第一个记录磁道的第一个记录 柱面柱面 C1磁道索引磁道索引 1 道道2 道道3 道道19和和20道存溢道存溢出记录出记录 2、3 磁道的磁道索引项磁道的磁道索引项47 T2 1 50 T19 1 R60 R65 R70 R80 R85 85 T3 1 90 T19 2 插入：插入： R65 进入进入 3 磁道之后。磁道之后。R14 R

16、21 R30 R43 R47R50 R90 28 物料管理物料管理File28Algorithms and DataStructures:files4、 ISAM文件和文件和VSAM文件文件 查找：主索引查找：主索引 柱面索引柱面索引 磁道索引磁道索引 磁道的第一个记录磁道的第一个记录 柱面柱面 C1磁道索引磁道索引 1 道道2 道道3 道道19和和20道存溢道存溢出记录出记录 2、3 磁道的磁道索引项磁道的磁道索引项47 T2 1 50 T19 3 R60 R65 R70 R80 R85 85 T3 1 90 T19 2 插入：插入： R48 进入进入 2 磁道之后。因磁道之后。因 48 4

17、7 , 只能进入本道溢出区。若同时插入多个记录进入只能进入本道溢出区。若同时插入多个记录进入 溢出区，注意排成递减序进入溢出区。溢出区，注意排成递减序进入溢出区。R14 R21 R30 R43 R47R50 R90 R4829 物料管理物料管理File29Algorithms and DataStructures:files4、 ISAM文件和文件和VSAM文件文件柱面柱面 C1磁道索引磁道索引 1 道道2 道道3 道道19和和20道存溢道存溢出记录出记录 2、3 磁道的磁道索引项磁道的磁道索引项47 T2 1 50 T19 3 R60 R65 R70 R80 R85 85 T3 1 90 T

18、19 2 删除：删除： 给被删除记录作一标记。优点：不必移动记录变更指针。缺点：周期性整理给被删除记录作一标记。优点：不必移动记录变更指针。缺点：周期性整理 ISAM 文文 件。如删除件。如删除 R21。R14 R21 R30 R43 R47R50 R90 R4830 物料管理物料管理File30Algorithms and DataStructures:files 定义：定义： m 阶阶 B+ 树满足或空，或：树满足或空，或：A、根结点要么是叶子，要么至少有两个儿子根结点要么是叶子，要么至少有两个儿子B、除根结点和叶子结点之外，每个结点的儿子个数为除根结点和叶子结点之外，每个结点的儿子个数为

19、: m/2 = s - 控制区间控制区间36 物料管理物料管理File36Algorithms and DataStructures:files4、 ISAM文件和文件和VSAM文件文件 为什么称之为为什么称之为 VSAM 文件文件：虚拟存储，同机器、设备无关。：虚拟存储，同机器、设备无关。分页格式化磁盘组分页格式化磁盘组页面号页面号指针指针外部页面映射表外部页面映射表123 分页：把内外存按同样的大小进行分页。使文件技术不依赖于具体的外部设备。更换分页：把内外存按同样的大小进行分页。使文件技术不依赖于具体的外部设备。更换外设时，不必改变整个程序，只需改变外部页面映射表中的相对地址到绝对地址的

20、计算外设时，不必改变整个程序，只需改变外部页面映射表中的相对地址到绝对地址的计算程序即可。程序即可。 控制区间控制区间 若干页面。控制面若干页面。控制面 若干控制区间。外存是内存的延伸，虚拟若干控制区间。外存是内存的延伸，虚拟 存储器。存储器。VSAM 可脱离具体的外存组织文件，所以称之为可脱离具体的外存组织文件，所以称之为 VSAM 文件。文件。37 物料管理物料管理File37Algorithms and DataStructures:files5、直接存取文件、直接存取文件(散列文件散列文件) 散列文件又称直接存取文件，其特点是，由记录的关键码“直接”得到记录在外存（磁盘）上的映象地址。

21、类似于构造一个哈希表，根据文件中关键码的特点设计一种“哈希函数”和“处理冲突的方法”，然后将记录散列到外存储设备上，故称“散列文件”。散列文件由若干个“桶”组成，根据设定的哈希函数将记录“映象”到某个桶号。处理冲突通常采用链地址法，即每个桶可以包括一个或几个页块，页块之间以指针相链。每个页块中的记录个数则由逻辑记录和物理记录的大小决定。38 物料管理物料管理File38Algorithms and DataStructures:files5、直接存取文件、直接存取文件(散列文件散列文件)例如：假设有18个记录，它们的关键码分别为： 278, 109, 063, 930, 589, 182, 505, 269, 008, 083, 164, 215, 330,