数据结构课程讲义ppt课件

《数据结构课程讲义ppt课件》由会员分享，可在线阅读，更多相关《数据结构课程讲义ppt课件（63页珍藏版）》请在金锄头文库上搜索。

1、Chapter 10 Chapter 10 文文 件件 10.2 有关文件的基本概念有关文件的基本概念10.3 顺顺 序序 文文 件件10.4 索索 引引 文文 件件10.5 索索 引引 顺顺 序序 文文 件件10.6 直直 接接 存存 取取 文文 件件10.7 多多 关关 键键 字字 文文 件件10.1基本概念基本概念10.1基本概念基本概念10.1常用外存：常用外存： 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始

2、盘组成。 便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末 端记录时）。端记录时）。端记录时）。端记录时）。.读读出出头头写写入入头头原原始始盘盘接接收收盘盘IBG（Inter Block Gap）块间块间间隙间隙块块 1块块 3块块 2带文件的读写带文件的读写带文件的读写带文件的读写时间：时间：时间：时间：T T i/o i/o = = t ta a + n + n t

3、tww t ta a ：延迟时间延迟时间延迟时间延迟时间 t tww：传输时间传输时间传输时间传输时间/ / 字符字符字符字符 n n 字符字符字符字符数。数。数。数。10.1基本概念基本概念 磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。 速度快、容量大、直接存取设备。速度快、容量大、直接存取设备。速度快、容量大、直接存取设备。速度快、容量大、直接存取设

4、备。 种类：固定头磁盘、活动头磁盘种类：固定头磁盘、活动头磁盘种类：固定头磁盘、活动头磁盘种类：固定头磁盘、活动头磁盘 固定头磁盘：每个磁道都有一个磁头（速度快）固定头磁盘：每个磁道都有一个磁头（速度快）固定头磁盘：每个磁道都有一个磁头（速度快）固定头磁盘：每个磁道都有一个磁头（速度快） 活动头磁盘：每个盘面共用一个磁头，活动头磁盘：每个盘面共用一个磁头，活动头磁盘：每个盘面共用一个磁头，活动头磁盘：每个盘面共用一个磁头， 增加了找道的时间，应用广泛。增加了找道的时间，应用广泛。增加了找道的时间，应用广泛。增加了找道的时间，应用广泛。 柱面：各盘面的直径相同的磁道的总和。柱面：各盘面的直径相同

5、的磁道的总和。柱面：各盘面的直径相同的磁道的总和。柱面：各盘面的直径相同的磁道的总和。 物理位置：盘组号、物理位置：盘组号、物理位置：盘组号、物理位置：盘组号、 柱面号、柱面号、柱面号、柱面号、 磁道号、磁道号、磁道号、磁道号、 块（扇区号）块（扇区号）块（扇区号）块（扇区号） 盘文件的读写时间：盘文件的读写时间：盘文件的读写时间：盘文件的读写时间：T T i/o i/o = = t tseckseck + + t tlala + n + nt twmwm t tseckseck ：找道时间找道时间找道时间找道时间t tlala ：等待时间等待时间等待时间等待时间t twmwm ：传输时间传输

6、时间传输时间传输时间/ / 字符，字符，字符，字符，n n 字符数。字符数。字符数。字符数。10.1基本概念基本概念 数据域（数据场）：记录中的每个数据项，称之为域或场（数据域（数据场）：记录中的每个数据项，称之为域或场（数据域（数据场）：记录中的每个数据项，称之为域或场（数据域（数据场）：记录中的每个数据项，称之为域或场（FieldField） 关键字：唯一标识记录的域，称之为关键字。辅助关键字，称之为次关键字。关键字：唯一标识记录的域，称之为关键字。辅助关键字，称之为次关键字。关键字：唯一标识记录的域，称之为关键字。辅助关键字，称之为次关键字。关键字：唯一标识记录的域，称之为关键字。辅助关

7、键字，称之为次关键字。 记录（记录（记录（记录（RecordRecord）：）：）：）：若干相关的若干相关的若干相关的若干相关的数据项的集合。如果存之于外存，则叫做记录。数据项的集合。如果存之于外存，则叫做记录。数据项的集合。如果存之于外存，则叫做记录。数据项的集合。如果存之于外存，则叫做记录。 文件：记录的集合。文件：记录的集合。文件：记录的集合。文件：记录的集合。 记录的物理结构和逻辑结构：记录的物理结构和逻辑结构：记录的物理结构和逻辑结构：记录的物理结构和逻辑结构： 逻辑结构：记录在用户或程序员面前呈现的形式。逻辑结构：记录在用户或程序员面前呈现的形式。逻辑结构：记录在用户或程序员面前呈

8、现的形式。逻辑结构：记录在用户或程序员面前呈现的形式。 物理结构：记录在在物理存储器上的存储方式，是数据的物理表示和组织。物理结构：记录在在物理存储器上的存储方式，是数据的物理表示和组织。物理结构：记录在在物理存储器上的存储方式，是数据的物理表示和组织。物理结构：记录在在物理存储器上的存储方式，是数据的物理表示和组织。 物理记录和逻辑记录：物理记录和逻辑记录：物理记录和逻辑记录：物理记录和逻辑记录： 物理记录：计算机用一条物理记录：计算机用一条物理记录：计算机用一条物理记录：计算机用一条 I/O I/O 指令进行读写外存的基本单位。通常，对一定指令进行读写外存的基本单位。通常，对一定指令进行读

9、写外存的基本单位。通常，对一定指令进行读写外存的基本单位。通常，对一定 的设备和操作系统，大小是固定不变的。的设备和操作系统，大小是固定不变的。的设备和操作系统，大小是固定不变的。的设备和操作系统，大小是固定不变的。 逻辑记录：程序员加以定义，用户要求使用的。逻辑记录：程序员加以定义，用户要求使用的。逻辑记录：程序员加以定义，用户要求使用的。逻辑记录：程序员加以定义，用户要求使用的。 关系：关系：关系：关系： 物理记录物理记录物理记录物理记录 - 逻辑记录逻辑记录逻辑记录逻辑记录2、基本术语：、基本术语：10.1基本概念基本概念记录记录B记录记录C记录记录D记录记录A记录记录A记录记录B记录记

10、录C10.1基本概念基本概念 检索：检索：检索：检索： 顺序存取：存取下一个逻辑记录顺序存取：存取下一个逻辑记录顺序存取：存取下一个逻辑记录顺序存取：存取下一个逻辑记录 直接存取：存取第直接存取：存取第直接存取：存取第直接存取：存取第 i i 个逻辑记录个逻辑记录个逻辑记录个逻辑记录 按关键字值存取相应的记录：按关键字值存取相应的记录：按关键字值存取相应的记录：按关键字值存取相应的记录：简单询问：查单个记录简单询问：查单个记录简单询问：查单个记录简单询问：查单个记录区域询问：查多个记录区域询问：查多个记录区域询问：查多个记录区域询问：查多个记录函数询问：满足某种条件的记录函数询问：满足某种条件

11、的记录函数询问：满足某种条件的记录函数询问：满足某种条件的记录布尔询问：满足布尔运算组合的询问布尔询问：满足布尔运算组合的询问布尔询问：满足布尔运算组合的询问布尔询问：满足布尔运算组合的询问 修改：插入、修改、更新修改：插入、修改、更新修改：插入、修改、更新修改：插入、修改、更新 更新方式：实时、批量两种方式更新方式：实时、批量两种方式更新方式：实时、批量两种方式更新方式：实时、批量两种方式3、检索和修改、检索和修改一、文件一、文件即即为记录的集合为记录的集合，和，和“查找查找 表表”的差别在于，的差别在于，“文件文件”指的是存指的是存 储在外存储器中的记录的集合。储在外存储器中的记录的集合。

12、 记录是文件中可以存取的数据的记录是文件中可以存取的数据的 基本单位基本单位。10.2 有关文件的基本概念有关文件的基本概念二、文件二、文件可按其中记录的类型不同而可按其中记录的类型不同而 分成分成两类两类：其一其一为为操作系统的文件操作系统的文件，文件中的记，文件中的记 录仅是一个字符组。由于操作系录仅是一个字符组。由于操作系 统中的文件仅是统中的文件仅是一维的连续字符一维的连续字符 序列序列，为了用户存取和加工的方，为了用户存取和加工的方 便，将文件中的信息划分为若干便，将文件中的信息划分为若干 组，其中每一组信息称作一个记组，其中每一组信息称作一个记 录；录；其二其二为为数据库文件数据库

13、文件，文件中的，文件中的记录带记录带 有结构，是数据项的集合有结构，是数据项的集合。记录。记录 是文件中可以存取的数据基本单是文件中可以存取的数据基本单 位，位，数据项是文件中可以使用的数据项是文件中可以使用的 数据最小单位。数据最小单位。三、记录中能识别不同记录的数据项 被称为关键字，若该数据项能唯 一识别一个记录，则称为主关键 字，若能识别多个记录则称为次 关键字。四、文件的逻辑结构指的是呈现在用 户面前的文件中记录之间的逻辑 关系；文件的物理结构指的是文 件中的逻辑记录在存储器中的组 织方式。 1检索顺序存取：存取“当前记录的”下一个记录；直接存取：存取第i个记录；按关键字存取：存取其关

14、键字等于给定值的记录。五、文件的操作：2修改修改往文件中往文件中插入插入一个或一批记录；一个或一批记录；更新更新文件中某个记录的属性。文件中某个记录的属性。从文件中从文件中删除删除一个或一批记录；一个或一批记录；文件的操作方式可以文件的操作方式可以实时处理实时处理或或批量处理。批量处理。3排序排序 主要讨论文件的几种常见的物理结构：顺序文件索引文件索引顺序文件直接存取文件多关键字文件结结 构构 特特 点：点： 记录在文件中的排列顺序是由记记录在文件中的排列顺序是由记录进入存储介质的次序决定的，录进入存储介质的次序决定的， 即即文文件物理结构中记录的排列顺序和文件件物理结构中记录的排列顺序和文件

15、的逻辑结构中记录的排列顺序一致。的逻辑结构中记录的排列顺序一致。10.3 顺顺 序序 文文 件件顺序文件的具体组织形式有两种：顺序文件的具体组织形式有两种：串联文件串联文件：物理记录之间的顺序由指：物理记录之间的顺序由指 针相链。针相链。连续文件连续文件：次序相继的两个物理记录：次序相继的两个物理记录 其存储位置相邻其存储位置相邻;操作特点操作特点：1便于便于进行顺序存取；进行顺序存取；2不不便便于于进进行行直直接接存存取取，为为取取第第i个个记记录录，必必须须先先读读出出前前i-1个个记记录录，对对于于磁磁盘盘上上的的等等长长记记录录的的连续文件可以进行折半查找；连续文件可以进行折半查找；3

16、插入新的记录插入新的记录只能只能加在文件加在文件的末尾；的末尾；4删除记录时，删除记录时，只作标记只作标记；5更新记录必须更新记录必须生成新的文件生成新的文件。 顺序文件的插入、删除和更新操顺序文件的插入、删除和更新操作在多数情况下都采用作在多数情况下都采用批处理方式批处理方式。此时，为处理方便，通常将顺序文件此时，为处理方便，通常将顺序文件作成有序文件，称作作成有序文件，称作“主文件主文件”，同时，同时将所有的操作作成一个将所有的操作作成一个“事务文件事务文件”（经过排序也成为有序文件），所谓（经过排序也成为有序文件），所谓“批处理批处理”，就是将这两个文件，就是将这两个文件“合合”为为一个

17、新的主文件一个新的主文件。具体操作相当于。具体操作相当于“归并两个有序表归并两个有序表”。（1）对于事务文件中的每个）对于事务文件中的每个操作操作 首先要判别其首先要判别其“合法性合法性”（2）事务文件中可能存在）事务文件中可能存在多个操多个操 作作是是对对主文件中主文件中同一个记录同一个记录 进行的进行的但有两点不同：但有两点不同： 假设主文件中含有假设主文件中含有n个记录，事个记录，事务文件中含有务文件中含有m个记录，则对事务文个记录，则对事务文件进行排序的时间复杂度为件进行排序的时间复杂度为O(mlogm），），内部归并的时间复杂度为内部归并的时间复杂度为O(m+n），），则则总的内部处

18、理的时间为总的内部处理的时间为O(mlogm+n）。 批处理的时间分析批处理的时间分析： 假设对外存进行一次读假设对外存进行一次读/取为取为s个个记录，则整个批处理过程中记录，则整个批处理过程中读读/写外存写外存的次数为的次数为2 （ m/s + (m+n)/s ） （其中（其中s s为对外存进行一次读为对外存进行一次读/ /取的取的记录数）。记录数）。一、结构特点：一、结构特点：1 1索引文件由索引文件由索引文件由索引文件由“ “主文件主文件主文件主文件” ”和多级和多级和多级和多级“ “索引索引索引索引” ”组成；组成；组成；组成；2 2索引中的每个记录由索引中的每个记录由索引中的每个记录

19、由索引中的每个记录由“ “关键字关键字关键字关键字” ”和和和和“ “指针指针指针指针” ”组成；组成；组成；组成；3 3通通通通常常常常，索索索索引引引引文文文文件件件件中中中中的的的的主主主主文文文文件件件件是是是是无无无无序序序序文文文文件件件件，索索索索引引引引是是是是 ( (按关键字有序按关键字有序按关键字有序按关键字有序) )的有序文件；的有序文件；的有序文件；的有序文件；4 4“ “索索索索引引引引” ”是是是是在在在在输输输输入入入入数数数数据据据据建建建建立立立立文文文文件件件件时时时时自自自自动动动动生生生生成成成成。初初初初建建建建时时时时的的的的“ “静静静静态态态态索

20、索索索引引引引” ”为为为为无无无无序序序序文文文文件件件件，经经经经过过过过排排排排序序序序后后后后成成成成为为为为有有有有序序序序文件。文件。文件。文件。10.4 10.4 索索 引引 文文 件件二、操作的特点：二、操作的特点：检检索索方方式式为为：直直接接存存取取和和按按关关键键字字存存取取。“按按关关键键字字检检索索”将将分分两两步步进进行行：先先查查索索引引，然后根据索引中指针所指索取记录；然后根据索引中指针所指索取记录；插插入入记记录录时时，“记记录录”插插入入在在主主文文件件的的末末尾尾，而而相相应应的的“索索引引项项”必必须须插插入入在在索索引引的的合合适适位位置置上上。因因此

21、此，最最好好在在建建索索引引表表时时留留有一定有一定“空位空位”；删删除除记记录录时时，仅仅需需删删除除索索引引表中相应的索引项即可；表中相应的索引项即可；更更新新记记录录时时，应应将将更更新新后后的的记记录录插插入入在在主主文文件件的的末末尾尾，同同时时修改相应的索引项。修改相应的索引项。 主主 文文 件件 索索 引引 表表 查查 找找 表表 第第 二二 查查 找表找表 第三查找表第三查找表 . . . .此时的索引文件结构：此时的索引文件结构：多级静态索引多级静态索引对对主文件中每个记录建立一个索引项主文件中每个记录建立一个索引项： 主关键字主关键字 记录在主文件中的存储位置记录在主文件中

22、的存储位置称作称作稠密索引稠密索引，由这些索引项构成，由这些索引项构成索引表。索引表。从索引表建立的索引称从索引表建立的索引称查找表查找表，其中，其中每个索引项为：每个索引项为： 最大关键字最大关键字 其其所在数据块的存储位置所在数据块的存储位置称这类索引为称这类索引为非稠密索引非稠密索引。类似地，由查找表建立的索引为类似地，由查找表建立的索引为第二第二查找表查找表；由第二查找表建立的索引为；由第二查找表建立的索引为第第三查找表三查找表。按关键字进行检索按关键字进行检索时，从时，从第三查找表第三查找表开始，开始，至多访问外存五次至多访问外存五次。索索引表引表采用查找树表或哈希表。采用查找树表或

23、哈希表。优点优点： 1）不需要建立多级索引；不需要建立多级索引； 2）初建索引不需要进行排序；初建索引不需要进行排序； 3）插入或删除记录时，修改索）插入或删除记录时，修改索引方便。引方便。动态索引动态索引用查找树表作索引时，查找索引所用查找树表作索引时，查找索引所需访问外存次数的最大值恰为查找需访问外存次数的最大值恰为查找树的深度。树的深度。 稠密索引的稠密索引的优点优点是，是，可以实现可以实现“预查找预查找” 缺点缺点是，是，索引表占用的存储空间大。索引表占用的存储空间大。可以作索引的树表有：可以作索引的树表有：二叉排序树、二叉排序树、B-树和键树。树和键树。10.5 索索 引引 顺顺 序

24、序 文文 件件主文件按主关键字有序，对一组记录建立一个索引项(建立非稠密索引)。结构特点：一、ISAM文件ISAM(Index Sequential Access Method)(索引顺序存取方法)是一种专为磁盘存取设计的文件组织方法。有两种典型的索引顺序文件：有两种典型的索引顺序文件：文件的组织方式文件的组织方式： 主文件按柱面集中存放，同时建立主文件按柱面集中存放，同时建立 三级索引：磁道索引、柱面索引和三级索引：磁道索引、柱面索引和 主索引。主索引。 关键字关键字 指针指针 关键字关键字 指针指针 磁道索引结构磁道索引结构基本索引项基本索引项溢出索引项溢出索引项2101024主索引 r(

25、14) r(21) r(38) r(41) r(57) r(63) r(72) r(85) r(99) 溢 出 区 磁磁 道道 索索 引引 r(514) 溢 出 区 磁道索引 r(1024)一 个 柱 面 .柱面索引992101024T0T1T2T3T4T5操作的特点：操作的特点：检检 索索插入插入删除删除检索：检索： 可有两种方式：可有两种方式： 按关键字存取按关键字存取 从主索引开始从主索引开始, ,到到 柱面索引，到磁道索引，最后取柱面索引，到磁道索引，最后取 得记录，先后访问四次外存。得记录，先后访问四次外存。顺序存取顺序存取 依关键字最小至大顺序依关键字最小至大顺序 存取。存取。插入

26、插入: : 修改修改本磁道的索引项本磁道的索引项( (包括基本索包括基本索 引项和溢出索引项引项和溢出索引项) )。将该磁道上关键字最大的记录将该磁道上关键字最大的记录移出移出 到本柱面的溢出区中到本柱面的溢出区中; ; 将记录将记录插入插入在某个磁道的合适位置上在某个磁道的合适位置上; ;删除删除: :在被删记录当前存储位置上在被删记录当前存储位置上 作作“删除标记删除标记”。文件重组文件重组 在经过多次的插入和删除操作之在经过多次的插入和删除操作之后，大量的记录进入文件的后，大量的记录进入文件的“溢出区溢出区”，而而“基本存储区基本存储区”中出现很多已被删去中出现很多已被删去的记录空间，此

27、时的文件结构很不合的记录空间，此时的文件结构很不合理。因此，对理。因此，对ISAM文件，文件， 需要周期需要周期地进行重整。地进行重整。柱面索引的位置柱面索引的位置 ISAM文件占有多个柱面，其柱文件占有多个柱面，其柱面索引本身占有一个柱面，为使面索引本身占有一个柱面，为使“磁头磁头”的平均移动距离最小，柱面的平均移动距离最小，柱面索引应设在数据文件所占全部柱面索引应设在数据文件所占全部柱面的中间位置上。的中间位置上。二、二、VSAM文件文件VSAM(Vistual Storage Access Method) 文件是利用操作系统中提供的文件是利用操作系统中提供的虚拟虚拟存储器存储器的功能组织

28、的文件，免除了的功能组织的文件，免除了用户为读用户为读/写记录时直接对外存进行写记录时直接对外存进行的操作，的操作，对用户而言，文件只有控对用户而言，文件只有控制区间和控制区域等逻辑存储单位制区间和控制区域等逻辑存储单位。 . 索引集索引集B+树树 顺序集顺序集控制区域控制区域控制区间控制区间数据集数据集1 1文件的结构文件的结构 2. 控制区间控制区间是用户进行一次存取的是用户进行一次存取的逻辑单位，可看成是一个逻辑磁道。逻辑单位，可看成是一个逻辑磁道。但它的实际大小和物理磁道无关。但它的实际大小和物理磁道无关。 VSAM文件初建时，每个控制区文件初建时，每个控制区间内的记录数不足额定数，并

29、且有的间内的记录数不足额定数，并且有的控制区间内的记录数为零。控制区间内的记录数为零。 控制区域控制区域由若干控制区间和它们由若干控制区间和它们的索引项组成，可看成是一个逻辑柱面。的索引项组成，可看成是一个逻辑柱面。顺序集顺序集本身是一个单链表，它本身是一个单链表，它包含文件的全部索引项，同时，顺包含文件的全部索引项，同时，顺序集中的每个结点即为序集中的每个结点即为B+树的叶子树的叶子结点，结点，索引集索引集中的结点即为中的结点即为B+树的树的非叶结点。非叶结点。文件的操作检索：可进行顺序存取和按关键字存取；插入：按关键字大小插入在某个适当的控制区间中，当控制区间中的记录数超过文件规定的大小时

30、，要“分裂”控制区间，必要时，还需要“分裂”控制区域；删除：必须“真实地”删除记录，因此要在控制区间内“移动”记录。VSAM文件文件通常被作为大型索引通常被作为大型索引顺序文件的标准组织方式。顺序文件的标准组织方式。其其缺点是缺点是：占有较多的存储空间，一般只：占有较多的存储空间，一般只 能保持约能保持约75%的存储空间利用的存储空间利用 率。率。(因此，一般情况下，极少因此，一般情况下，极少 产生需要分裂控制区域的情况产生需要分裂控制区域的情况)其其优点是优点是：动态地分配和释放空间：动态地分配和释放空间, 不需不需 要重组文件；能较快地实现对要重组文件；能较快地实现对 “后插入后插入”的记

31、录的检索；的记录的检索；10.6 直直 接接 存存 取取 文文 件件和前几节讨论的文件组织方法和前几节讨论的文件组织方法不同，不同，直接存取文件的特点直接存取文件的特点是，由是，由记录的关键字记录的关键字“直接直接”得到得到记录在外记录在外存上的存上的映象地址映象地址。 类似于哈希表的构造方法，类似于哈希表的构造方法，根根据据文件中关键字的特点设计一种文件中关键字的特点设计一种“哈哈希函数希函数”和和“处理冲突的方法处理冲突的方法”将记录将记录散列到外存储设备上散列到外存储设备上，又称，又称“散列文件散列文件”。哈希文件的结构哈希文件的结构 由于记录在外存上是成组存放的，由于记录在外存上是成组

32、存放的，因此允许多个记录映象到同一个地址因此允许多个记录映象到同一个地址上。在此，称外存储器中存放多个记上。在此，称外存储器中存放多个记录的录的“数据块数据块”为为“桶桶”。 因此因此由哈希函由哈希函数得到的映象地址为数得到的映象地址为“桶地址桶地址”。例如：有一组关键字如下所列例如：有一组关键字如下所列 589，063，269，505，764，182，166，330假设哈希函数为假设哈希函数为 key MOD 7，每个桶可以容纳每个桶可以容纳3个记录（称桶的容量为个记录（称桶的容量为3），则哈希文件如下），则哈希文件如下:基桶基桶063 182589 505 764269166330溢出桶溢

33、出桶 在哈希文件中，在哈希文件中，“冲突冲突”和和“溢出溢出”是不同的概念是不同的概念。一般情况下，假设桶。一般情况下，假设桶的大小为的大小为m，则允许哈希地址产生则允许哈希地址产生m-1次的冲突，当发生第次的冲突，当发生第m次冲突时，才次冲突时，才需要进行需要进行“冲突处理冲突处理”，对散列文件而，对散列文件而言，通常采用链地址法出路冲突。为言，通常采用链地址法出路冲突。为区别起见，区别起见，称直接称直接“散列散列”的数据块为的数据块为“基桶基桶”，而因，而因“溢出溢出”存放的数据块为存放的数据块为“溢出桶溢出桶”。文件的操作检索：只能进行按关键字的查找，不能进行顺序查找。检索时，先在基桶内

34、进行查找，若不存在，则再到溢出桶中进行查找；插入：当查找不成功时，将记录插入在相应的基桶或溢出桶内；删除：对被删记录作特殊标记。优点：优点：记录随机存放，记录随机存放，不需要不需要进行进行排排 序；插入、删除方便，存取速序；插入、删除方便，存取速 度快；节省存储空间度快；节省存储空间，不需要，不需要 索引区。索引区。缺点：缺点：不能进行顺序存取不能进行顺序存取；在经过多；在经过多 次插入和删除操作之后，需进次插入和删除操作之后，需进 行行“重组文件重组文件”的操作。的操作。10.7 多多 关关 键键 字字 文文 件件一、多关键字文件的特点一、多关键字文件的特点 除需要对主关键字建立除需要对主关

35、键字建立“主索引主索引”外，外， 尚需对各个次关键字建立尚需对各个次关键字建立“次索引次索引”。次索引项：次索引项： 次关键字次关键字 （指向记录的）指针（指向记录的）指针二、次索引的组织方法二、次索引的组织方法1多重链表文件多重链表文件特点：将所有特点：将所有具有相同次关键字的具有相同次关键字的记录链接在同一链表中记录链接在同一链表中，该链表的，该链表的头指针即为次索引项中头指针即为次索引项中“指针域指针域”的值；的值；2倒排文件倒排文件特特点点：将将所所有有具具有有相相同同次次关关键键字字的的记记录录构构成成一一个个次次索索引引顺顺序序表表，此此时时的的次次索索引引顺顺序序表表中中仅仅存存放放记记录录的的“主主关关键键字字”或或记记录录的的“物物理理记记录录号号”。次次索索引引项项中中的的“指指针针”指指向向相相应应的的次次索索引引顺序表；顺序表；3次次关关键键字字索索引引表表本本身身的的结结构构 可可以以是是顺顺序序表表，也也可可以以是是树树表表或或哈哈希希表表，视具体的次关键字的特性而定。视具体的次关键字的特性而定。本章学习要求：本章学习要求：熟悉各类文件的特点，构造熟悉各类文件的特点，构造方法以及如何实现检索，插方法以及如何实现检索，插入和删除等操作。入和删除等操作。