第9章-文件(高级程序设计)

1、1本章主要内容本章主要内容: : 1 1、文件概述、文件概述 2 2、顺序文件、顺序文件 3 3、索引文件、索引文件 4 4、ISAMISAM文件文件 5 5、散列文件、散列文件本章重点：本章重点：文件的组织形式与检索方法。文件的组织形式与检索方法。本章难点：本章难点：ISAMISAM文件的组织与检索。文件的组织与检索。2 在现代计算机的应用领域中，数据处理是一在现代计算机的应用领域中，数据处理是一个重要方面。数据处理是对各种类型的大批量的个重要方面。数据处理是对各种类型的大批量的数据进行收集、存储、排序、检索、计算、修改、数据进行收集、存储、排序、检索、计算、修改、输出等分析和加工处理的过程

2、。例如，用计算机输出等分析和加工处理的过程。例如，用计算机进行企业管理、财务工资管理、仓库物资管理、进行企业管理、财务工资管理、仓库物资管理、情报检索、统计报表等都涉及到数据存放到外存情报检索、统计报表等都涉及到数据存放到外存储器上。有时，为了长期保存原始数据和加工处储器上。有时，为了长期保存原始数据和加工处理过的数据，也需要将这些数据以文件的形式存理过的数据，也需要将这些数据以文件的形式存放在外存上。学完本章读者应能掌握文件的概念、放在外存上。学完本章读者应能掌握文件的概念、逻辑特性、物理结构和基本操作。逻辑特性、物理结构和基本操作。9.1文件概述文件概述31、文件概念、文件概念1、常用外存

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

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

5、道号、磁道号、 块（扇区号）块（扇区号） 盘文件的读写时间盘文件的读写时间：T i/o = tseck + tla + ntwm tseck ：找道时间：找道时间tla ：等待时间：等待时间twm ：传输时间：传输时间/ 字符，字符，n 字符数。字符数。5 数据域（数据场）数据域（数据场）：记录中的每个数据项，称之为域或场（：记录中的每个数据项，称之为域或场（Field） 关键字关键字：唯一标识记录的域，称之为关键字。辅助关键字，称之为次关键字。：唯一标识记录的域，称之为关键字。辅助关键字，称之为次关键字。 记录（记录（Record）：若干相关的数据项的集合。如果存之于外存，叫做记录。：若干相

6、关的数据项的集合。如果存之于外存，叫做记录。 文件文件：记录的集合。：记录的集合。 记录的物理结构和逻辑结构记录的物理结构和逻辑结构： 逻辑结构：记录在用户或程序员面前呈现的形式。逻辑结构：记录在用户或程序员面前呈现的形式。 物理结构：记录在在物理存储器上的存储方式，是数据的物理表示和组织物理结构：记录在在物理存储器上的存储方式，是数据的物理表示和组织。 物理记录和逻辑记录物理记录和逻辑记录： 物理记录物理记录：计算机用一条：计算机用一条 I/O 指令进行读写外存的基本单位。通常，对一定指令进行读写外存的基本单位。通常，对一定 的设备和操作系统，大小是固定不变的。的设备和操作系统，大小是固定不

7、变的。 逻辑记录逻辑记录：程序员加以定义，用户要求使用的。：程序员加以定义，用户要求使用的。 2 2、基本术语：、基本术语：6记录记录B记录记录C记录记录D记录记录A记录记录A记录记录B记录记录C记录记录D7 检索：检索： 顺序存取顺序存取：存取下一个逻辑记录：存取下一个逻辑记录 直接存取直接存取：存取第：存取第 i 个逻辑记录个逻辑记录 按关键字值存取相应的记录按关键字值存取相应的记录：简单询问：查单个记录简单询问：查单个记录区域询问：查多个记录区域询问：查多个记录函数询问：满足某种条件的记录函数询问：满足某种条件的记录布尔询问：满足布尔运算组合的询问布尔询问：满足布尔运算组合的询问 修改修

8、改：插入、修改、更新：插入、修改、更新 更新方式更新方式：实时、批量两种方式：实时、批量两种方式3、检索和修改、检索和修改89.2 顺序文件顺序文件 顺序文件是物理结构最简单的文件，也是数据处理历史顺序文件是物理结构最简单的文件，也是数据处理历史上最早使用的文件结构。上最早使用的文件结构。顺序文件的各个记录按输入的先后次顺序文件的各个记录按输入的先后次序存放在外存中的连续存储区序存放在外存中的连续存储区。为了便于检索和修改文件，文。为了便于检索和修改文件，文件中的记录通常按关键字的大小次序排列，成为件中的记录通常按关键字的大小次序排列，成为按关键字排序按关键字排序的顺序文件。的顺序文件。 顺序

9、文件的基本优点是在连续存取时速度较快。例如，如顺序文件的基本优点是在连续存取时速度较快。例如，如果文件中的第果文件中的第i i个记录刚被存取过，而下一个要存取的记录就是个记录刚被存取过，而下一个要存取的记录就是第第i+1i+1个记录，则此次存取将会很快完成。磁带是比较适用于这个记录，则此次存取将会很快完成。磁带是比较适用于这种应用的外存设备。存放于磁带上的文件也只能是顺序文件，种应用的外存设备。存放于磁带上的文件也只能是顺序文件，这是由磁带的物理特性决定的。存放于磁盘上的文件，既可以这是由磁带的物理特性决定的。存放于磁盘上的文件，既可以是顺序文件，也可以是索引结构或其它结构类型的文件。是顺序文

10、件，也可以是索引结构或其它结构类型的文件。9当需要对磁带顺序文件进行检索时，一般是采用顺序扫描的当需要对磁带顺序文件进行检索时，一般是采用顺序扫描的方式来检索满足查询条件的记录。例如，若要检索第方式来检索满足查询条件的记录。例如，若要检索第i i个记录，个记录，则必须先检索前面的则必须先检索前面的i-1i-1个记录。为了提高平均检索效率，可个记录。为了提高平均检索效率，可采用批量处理技术。如果采用批量处理技术。如果将对文件的多个检索请求加以积累将对文件的多个检索请求加以积累和排序，则形成一个称为待办文件和排序，则形成一个称为待办文件（或事务文件）的文件。（或事务文件）的文件。如果将被查询的文件

11、称为主文件，则批量检索就是按照待办如果将被查询的文件称为主文件，则批量检索就是按照待办文件的要求成批地检索主文件。文件的要求成批地检索主文件。批量检索对于实时应用来说批量检索对于实时应用来说是不适宜的，因为实时查询要求响应时间快，是不适宜的，因为实时查询要求响应时间快，而在很短的时而在很短的时间间隔内，积累的批处理文件规模太小，不能表现出它的优间间隔内，积累的批处理文件规模太小，不能表现出它的优越性。越性。10在磁带顺序文件中插入记录，只能加在文件的末尾，在磁带顺序文件中插入记录，只能加在文件的末尾，不能插在不能插在两个原有记录之间两个原有记录之间。修改记录，即使在新旧记录等长的情况下，修改记

12、录，即使在新旧记录等长的情况下，将新记录写在旧记录的位置上，一般不但不可能完全重合，甚将新记录写在旧记录的位置上，一般不但不可能完全重合，甚至还会破坏邻近记录的信息。因此，修改一个磁带文件，需要至还会破坏邻近记录的信息。因此，修改一个磁带文件，需要用另一条磁带将原文件复制过来，在复制过程中进行插入、删用另一条磁带将原文件复制过来，在复制过程中进行插入、删除、修改记录的操作。除、修改记录的操作。为了提高效率，修改一个顺序文件，也为了提高效率，修改一个顺序文件，也采用成批处理技术。这种批量修改方式很适用于银行帐户结算采用成批处理技术。这种批量修改方式很适用于银行帐户结算管理系统。例如，可把一天的零

13、星支取和存入分别作为记录收管理系统。例如，可把一天的零星支取和存入分别作为记录收集在一起，构成为一个待办文件，在当天下班时再按照待办文集在一起，构成为一个待办文件，在当天下班时再按照待办文件进行批量修改主文件（头天下班修改过的主文件）的工作，件进行批量修改主文件（头天下班修改过的主文件）的工作，便得到一个新主文件。便得到一个新主文件。 119.3 索引文件索引文件 顺序文件的查询速度很慢。采用索引文件可以提高检索顺序文件的查询速度很慢。采用索引文件可以提高检索效率。实际上，在前面的章节中我们已经运用了索引技术。效率。实际上，在前面的章节中我们已经运用了索引技术。索引用来表示关键字与相应记录的存

14、储地址之间的对应索引用来表示关键字与相应记录的存储地址之间的对应关系。关系。换言之，索引指出了记录在存储器中的存储地址。换言之，索引指出了记录在存储器中的存储地址。设设记录记录R Ri i的关键字为的关键字为K Ki i，R Ri i在外存中的存储地址为在外存中的存储地址为A Ai i，则（，则（K Ki i，A Ai i）称为记录）称为记录R Ri i的索引项。的索引项。索引表（简称索引）是索引项的索引表（简称索引）是索引项的集合。集合。12如果文件中的每个记录都有一个索引项，则这样的索引称如果文件中的每个记录都有一个索引项，则这样的索引称为为稠密索引稠密索引。如果多个记录只有一个索引项，则

15、这样的索引称。如果多个记录只有一个索引项，则这样的索引称为为非稠密索引非稠密索引。带有索引的文件称为索引文件。索引也称为目。带有索引的文件称为索引文件。索引也称为目录。录。索引文件在外存（磁盘、磁鼓等）中可分为两个存储区：索引文件在外存（磁盘、磁鼓等）中可分为两个存储区：索引区和记录区（数据区）索引区和记录区（数据区）。索引表中的索引项顺序存放在索。索引表中的索引项顺序存放在索引区中，但为了便于检索，索引项一般按关键字的大小次序排引区中，但为了便于检索，索引项一般按关键字的大小次序排列。文件中的记录按输入的先后次序存放到记录区；记录区按列。文件中的记录按输入的先后次序存放到记录区；记录区按关键

16、字大小次序排列的索引文件称为索引顺序文件。关键字大小次序排列的索引文件称为索引顺序文件。13 对于索引顺序文件，对于索引顺序文件，可以不必使用稠密索引，可以不必使用稠密索引，只为一个记只为一个记录块（含多个有序记录）建立一个索引项录块（含多个有序记录）建立一个索引项。记录区不按关键字记录区不按关键字大小次序排列的索引文件称为索引非顺序文件，这时应使用稠大小次序排列的索引文件称为索引非顺序文件，这时应使用稠密索引。密索引。通常，索引项所含的数据信息比记录少得多，因而索通常，索引项所含的数据信息比记录少得多，因而索引所需的存储空间比文件本身（记录区）所需要的存储空间少引所需的存储空间比文件本身（记

17、录区）所需要的存储空间少得多。在文件的记录数较少的情况下，可以为每个记录建立一得多。在文件的记录数较少的情况下，可以为每个记录建立一个索引项。文件建立时，开辟一个索引区，一般固定在某个磁个索引项。文件建立时，开辟一个索引区，一般固定在某个磁盘面的一个或多个磁道上。写入一个记录到记录区时，在索引盘面的一个或多个磁道上。写入一个记录到记录区时，在索引区相应登入一个索引项，即把该记录的关键字（主关键字）和区相应登入一个索引项，即把该记录的关键字（主关键字）和记录的存储地址顺序写入索引区。文件建立后，将索引区中的记录的存储地址顺序写入索引区。文件建立后，将索引区中的索引读入内存的缓冲区，按关键字进行内

18、部排序。最后将排序索引读入内存的缓冲区，按关键字进行内部排序。最后将排序好的索引项顺序写回到磁盘上的索引区。好的索引项顺序写回到磁盘上的索引区。14根据关键字查找索引文件的记录分两步进行。第根据关键字查找索引文件的记录分两步进行。第1 1步，访步，访问外存的索引区，将索引读入内存缓冲区，问外存的索引区，将索引读入内存缓冲区，使用顺序查找或折使用顺序查找或折半查找法找出所查记录在外存数据区中的地址半查找法找出所查记录在外存数据区中的地址，这一过程称为，这一过程称为预查找。第预查找。第2 2步，如果在预查中已找到了所查记录的地址，则第步，如果在预查中已找到了所查记录的地址，则第2 2次访问外存，次

19、访问外存，根据已查到的地址，读取所查的记录根据已查到的地址，读取所查的记录。15 删除一个记录时，只需删去相应的索引项，而不必移动数删除一个记录时，只需删去相应的索引项，而不必移动数据区中的记录。插入一个新记录时，将记录放到记录区的末尾，据区中的记录。插入一个新记录时，将记录放到记录区的末尾，在索引区登记相应的索引项，并对索引区中的索引项重新排序。在索引区登记相应的索引项，并对索引区中的索引项重新排序。 在实际应用中，索引顺序文件是被经常采用的一种文件结在实际应用中，索引顺序文件是被经常采用的一种文件结构。它是在顺序文件的基础上，用增加索引的办法而形成的。构。它是在顺序文件的基础上，用增加索引

20、的办法而形成的。文件中的记录按关键字大小顺序存放在磁盘的连续或相邻的存文件中的记录按关键字大小顺序存放在磁盘的连续或相邻的存储区中。储区中。由于记录按关键字排序，因此不必为每一个记录设立由于记录按关键字排序，因此不必为每一个记录设立一个索引项，而把文件划分为若干个记录块一个索引项，而把文件划分为若干个记录块，只为每块中关键，只为每块中关键字最大（或最小）的记录设置一个索引项。这种组织文件的方字最大（或最小）的记录设置一个索引项。这种组织文件的方法称为法称为索引顺序存取法索引顺序存取法，用这种方法建立起来的索引文件称为，用这种方法建立起来的索引文件称为ISAMISAM文件，它是一种专为磁盘存取设

21、计的文件组织方式。文件，它是一种专为磁盘存取设计的文件组织方式。16 由于磁盘是以由于磁盘是以盘组、柱面和磁道盘组、柱面和磁道三级地址存取的设备，三级地址存取的设备，则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。文件的记录在同一盘组上存放时，应先集中放在一个柱面上，文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上，然后再顺序存放在相邻的柱面上，对同一柱面，则应按盘面对同一柱面，则应按盘面的次序顺序存放的次序顺序存放。每个柱面建立一个磁道索引，每个磁道索。每个柱面建立一个磁道索引，每个磁道索引项由两部分组

22、成：引项由两部分组成：基本索引项和溢出索引项基本索引项和溢出索引项，每一部分都，每一部分都包括关键字和指针两项，前者表示该磁道中最大关键字，后包括关键字和指针两项，前者表示该磁道中最大关键字，后者指示该磁道中第一个记录的位置，柱面索引的每一个索引者指示该磁道中第一个记录的位置，柱面索引的每一个索引项也由关键字和指针两部分组成，前者表示该柱面中最末一项也由关键字和指针两部分组成，前者表示该柱面中最末一个记录的关键字（最大关键字），后者指示该柱面上的磁道个记录的关键字（最大关键字），后者指示该柱面上的磁道索引位置。柱面索引存放在某个柱面上，若柱面索引较大，索引位置。柱面索引存放在某个柱面上，若柱面

23、索引较大，占多个磁道时，则可建立柱面索引的索引占多个磁道时，则可建立柱面索引的索引主索引。主索引。179.4 ISAM文件文件1、ISAM（Indexed Sequential Access Method 索引顺序访问方法）索引顺序访问方法） 文件文件文件的组织方式：文件的组织方式：磁道索引磁道索引R14 R21R45 R47 R50R164磁道索引磁道索引R189R215R330磁道索引磁道索引R3843R4150溢出区溢出区溢出区溢出区溢出区溢出区2155038431643304150164330810415062011004150柱面柱面C1柱面柱面C2柱面柱面Cn主索引（柱面主索引（柱

24、面组索引）组索引） 柱面索引柱面索引 磁道索引磁道索引181、ISAM（Indexed Sequential Access Method ） 文件文件 柱面的安排：柱面的安排：柱面柱面 C1磁道索引磁道索引 1 道道 2 道道至至 18道道存存数数据据19和和20道存溢道存溢出记录出记录关键字关键字 指针指针 关键字关键字 指针指针 基本索引项基本索引项 溢出索引项溢出索引项 磁道索引项结构磁道索引项结构 基本索引项基本索引项 关键字关键字：本道的最大关：本道的最大关 键字值键字值 指指 针针：本道第一个记：本道第一个记 录的地址录的地址 溢出索引项溢出索引项 关键字关键字：本道的溢出记：本道

25、的溢出记 录的最大关键录的最大关键 字值字值 指指 针针：本道的溢出记：本道的溢出记 录的第一个溢录的第一个溢 出记录的地址出记录的地址19 查找：主索引查找：主索引 柱面索引柱面索引 磁道索引磁道索引 磁道的第一个记录磁道的第一个记录 柱面柱面 C1磁道索引磁道索引 1 道道2 道道3 道道19和和20道存溢道存溢出记录出记录 2、3 磁道的磁道索引项磁道的磁道索引项50 T2 1 R60 R70 R80 R85 R9090 T3 1R14 R21 R43 R47 R5020 定义：定义： m m 阶阶 B+ B+ 树满足或空，或：树满足或空，或：A A、根结点要么是叶子，要么至少有两个儿子

26、、根结点要么是叶子，要么至少有两个儿子B B、除根结点和叶子结点之外，每个结点的儿子个数为、除根结点和叶子结点之外，每个结点的儿子个数为: : m/2 = s = m m/2 = s 2； 2.关键字集合分布在整颗树中； 3.B-树没有B树平衡的问题；B+B+树树 是B-树的变体，也是一种多路搜索树： 1.其定义基本与B-树同，除了： 2.非叶子结点的子树指针与关键字个数相同； 3.非叶子结点子树指针Pi，指向关键字值属于Ki, Ki+1)的子树； 4.为所有叶子结点增加一个链指针； 5.所有关键字都在叶子结点出现；B B* *树树 是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指

27、针；22 例如：例如：m = 3 阶阶 B+ 树。除根结点和叶子结点之外，每个结点的树。除根结点和叶子结点之外，每个结点的儿子个数至少为儿子个数至少为 m/2 = 2 个；结点的关键字个数至少为个；结点的关键字个数至少为 1 。该。该 B+ 树的深度为树的深度为 4。叶子结点都在第。叶子结点都在第 4 层上。层上。 85 99 47 58 64 35 39 15 27 5 1139，64，9911，27 27， 994245475055586164808185869499258911121520273235373839第第 1 层层第第 2 层层第第 3 层层(L层层)第第 4 层层(L1层层

28、)239.5 散列文件散列文件 散列文件指的是利用杂凑（散列文件指的是利用杂凑（HashHash）法进行组织的文件。）法进行组织的文件。它类似于哈希表，即根据文件中关键字的特点设计一种哈希它类似于哈希表，即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上，故又称散函数和处理冲突的方法将记录散列到存储设备上，故又称散列文件。列文件。 与哈希表不同的是，对于文件来说，磁盘上的文件记录与哈希表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的。通常是成组存放的。若干个记录组成一个存储单位，在散列若干个记录组成一个存储单位，在散列文件中这个存储单位叫作桶。一个桶能存放

29、的逻辑记录的总文件中这个存储单位叫作桶。一个桶能存放的逻辑记录的总数称为桶的容量。假如一个桶能存放数称为桶的容量。假如一个桶能存放m m个记录，即个记录，即m m个同义词个同义词的记录可以存放在同一地址的桶中，当第的记录可以存放在同一地址的桶中，当第m+1m+1个同义词出现时个同义词出现时则发生则发生“溢出溢出”。处理溢出也可采用哈希表中处理冲突的各。处理溢出也可采用哈希表中处理冲突的各种方法；但对散列文件，主要采用种方法；但对散列文件，主要采用链地址法链地址法. .24当发生当发生“溢出溢出”时，需要将第时，需要将第m+1m+1个同义词存放到另一个桶个同义词存放到另一个桶中，通常称此桶为中，

30、通常称此桶为“溢出桶溢出桶”；相对地，称前；相对地，称前m m个同义词存放的个同义词存放的桶为桶为“基桶基桶”。溢出桶可以有多个，它们和基桶大小相同，相。溢出桶可以有多个，它们和基桶大小相同，相互之间用指针相链接。当在基桶中没有找到待查记录时，就顺互之间用指针相链接。当在基桶中没有找到待查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。面上。 25 例如，某例如，某i i文件有文件有1818个记录，其关键字分别

31、为个记录，其关键字分别为2828，1919，1313，9393，8989，1414，5555，6969，8 8，9 9，1616，2121，3333，8181，6262，1111，3434，3535。用除留余。用除留余数法作哈希函数数法作哈希函数H H（keykey）=key MOD 7=key MOD 7。桶的容量。桶的容量m=3m=3，基本桶数，基本桶数=7=7，由此得到的散列文件如图由此得到的散列文件如图10-610-6所示。所示。 桶 编 号 基 桶 溢 出 桶2814213589391681111989331355696234图10-6 散 列 文 件 示 例26 在散列文件中进行查