数据结构学习12

1、Data StructureData StructurePage 12022-5-21q 学习目标学习目标v熟悉各类熟悉各类文件的特点文件的特点，构造方法构造方法以及如何以及如何实现检索，插入和删除实现检索，插入和删除等操作。等操作。q 重点和难点重点和难点v重点：重点：了解各种文件的结构特点及其适用场合了解各种文件的结构特点及其适用场合。q 知识点知识点v顺序文件、索引文件、索引顺序文件、顺序文件、索引文件、索引顺序文件、VSAMVSAM文件、散列文件、多文件、散列文件、多关键字文件关键字文件 Data StructureData StructurePage 22022-5-2112.1 1

2、2.1 有关文件的基本概念有关文件的基本概念q 文件文件(File)(File)v是由大量性质相同的记录组成的集合，一般放在外存上。是由大量性质相同的记录组成的集合，一般放在外存上。q 记录记录v是数据项的集合，是可存取的数据的基本单位。是数据项的集合，是可存取的数据的基本单位。q 数据项数据项v由一个或多个位或字节组成，是不可分割的数据最小单位。由一个或多个位或字节组成，是不可分割的数据最小单位。q 定长记录文件定长记录文件v文件中每个记录含有的信息长度相等。文件中每个记录含有的信息长度相等。q 不定长文件不定长文件v文件中含有信息长度不等的不定长记录。文件中含有信息长度不等的不定长记录。D

3、ata StructureData StructurePage 32022-5-21q 单关键字文件单关键字文件v文件中的记录只有一个唯一标识记录的主关键字。文件中的记录只有一个唯一标识记录的主关键字。q 多关键字文件多关键字文件v文件中的记录除了含有一个主关键字外，还含有若干个次关键字。文件中的记录除了含有一个主关键字外，还含有若干个次关键字。q 记录的属性记录的属性v记录中所有非关键字的数据项。记录中所有非关键字的数据项。q 记录的逻辑结构记录的逻辑结构v记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式。存取方式。

4、q 记录的物理结构记录的物理结构v数据在物理存储器上存储的方式，是数据的物理表示和组织。数据在物理存储器上存储的方式，是数据的物理表示和组织。Data StructureData StructurePage 42022-5-21q 物理记录物理记录v计算机用一条计算机用一条I/0I/0命令进行读写的基本数据单位（物理块）。命令进行读写的基本数据单位（物理块）。v物理记录和逻辑记录之间可能存在下列三种关系：物理记录和逻辑记录之间可能存在下列三种关系：一个物理记录存放一个逻辑记录；一个物理记录存放一个逻辑记录；一个物理记录包含多个逻辑记录；一个物理记录包含多个逻辑记录；多个物理记录表示一个逻辑记录

5、。多个物理记录表示一个逻辑记录。q 文件的检索方式文件的检索方式v顺序存取：存取下一个逻辑记录。顺序存取：存取下一个逻辑记录。v直接存取；存取第直接存取；存取第i i个逻辑记录。个逻辑记录。v按关键字存取：按关键字存取： 简单查询、区域查询、函数查询、布尔查询简单查询、区域查询、函数查询、布尔查询Data StructureData StructurePage 52022-5-21q 文件的修改文件的修改v记录的插入、删除、修改。记录的插入、删除、修改。q 文件的物理结构文件的物理结构v文件在外存上的组织方式。文件在外存上的组织方式。顺序组织顺序组织随机组织随机组织链组织链组织Data Str

6、uctureData StructurePage 62022-5-21q 顺序文件顺序文件v定义定义 记录按其在文件中的逻辑顺序依次进入存储介质而建立的记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即，即物理记录和逻辑记录的顺序是一致的。物理记录和逻辑记录的顺序是一致的。v分类分类连续（顺序）文件连续（顺序）文件 次序相继的两个物理记录在存储介质上的存储位置是相邻的。次序相继的两个物理记录在存储介质上的存储位置是相邻的。串联（顺序）文件串联（顺序）文件 物理记录之间的次序由指针相链表示。物理记录之间的次序由指针相链表示。Data StructureData StructurePage 7

7、2022-5-21v特点特点存取第存取第i i个记录，必须先搜索在它之前的个记录，必须先搜索在它之前的i-1i-1个记录。个记录。新的记录只能加在文件末尾。新的记录只能加在文件末尾。更新记录，必须将整个文件复制。更新记录，必须将整个文件复制。v优点优点 连续存取的速度快，主要用于只进行顺序存取、批量修改的情况。连续存取的速度快，主要用于只进行顺序存取、批量修改的情况。v存取设备存取设备磁带磁带 适合于文件的数据量大、平时记录变化少、只作批量修改的情况。适合于文件的数据量大、平时记录变化少、只作批量修改的情况。磁盘磁盘Data StructureData StructurePage 82022-

8、5-21q 引入原因引入原因v对于按关键字存取得记录结构，顺序查找和折半查找的速度很慢。对于按关键字存取得记录结构，顺序查找和折半查找的速度很慢。为了避免大量与外存打交道，可以保存一个索引表来指示关键字为了避免大量与外存打交道，可以保存一个索引表来指示关键字与记录地址之间的对应关系。与记录地址之间的对应关系。q 索引文件索引文件v包括数据区和索引表两部分。包括数据区和索引表两部分。v为按建立时，系统自动开辟索引区。按记录进入的顺序登记索引为按建立时，系统自动开辟索引区。按记录进入的顺序登记索引项。索引项指出该记录的物理地址。最后，索引表按关键字排序。项。索引项指出该记录的物理地址。最后，索引表

9、按关键字排序。v只能存储在磁盘存储设备上。只能存储在磁盘存储设备上。Data StructureData StructurePage 92022-5-21Data StructureData StructurePage 102022-5-21q 索引文件的检索索引文件的检索v将索引表读入内存（若一个物理块可容纳一个索引表，则仅一次将索引表读入内存（若一个物理块可容纳一个索引表，则仅一次读入，否则需要多次读入）；查找索引表，确定记录的物理地址读入，否则需要多次读入）；查找索引表，确定记录的物理地址（索引表有序，可折半查找）；（索引表有序，可折半查找）；v根据物理地址，一次读取记录。根据物理地址，

10、一次读取记录。q 索引文件的修改索引文件的修改v删除删除 仅删去相应的索引项。仅删去相应的索引项。v插入插入 记录进入数据区末尾，索引项插入索引表中（或重新排序）。记录进入数据区末尾，索引项插入索引表中（或重新排序）。v更新更新 删除与插入的结合。删除与插入的结合。Data StructureData StructurePage 112022-5-21q 多级索引多级索引v记录数目很大，导致一个物理块容纳不了索引表。此时，查找索记录数目很大，导致一个物理块容纳不了索引表。此时，查找索引表需要多次访问内存。引表需要多次访问内存。v对索引表再建立一个索引。对索引表再建立一个索引。v最高可以有四级索

11、引，此时检索需要访问外存最高可以有四级索引，此时检索需要访问外存5 5次。次。Data StructureData StructurePage 122022-5-21q ISAMISAM文件（文件（索引顺序存取法）索引顺序存取法）v是一种是一种专为磁盘存取而设计的文件组织方式专为磁盘存取而设计的文件组织方式。v由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件盘上的数据文件建立建立盘组、柱面和磁道三级索引盘组、柱面和磁道三级索引。v文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然文件的记录在同一盘组上存放时，应

12、先集中放在一个柱面上，然后再顺序存放在相邻的柱面上，对同一柱面，则应按盘面的次序后再顺序存放在相邻的柱面上，对同一柱面，则应按盘面的次序顺序存放。用这种方法建立起来的索引文件称为顺序存放。用这种方法建立起来的索引文件称为ISAMISAM文件。文件。v包括：索引区、数据基本区、数据溢出区。包括：索引区、数据基本区、数据溢出区。Data StructureData StructurePage 132022-5-21数据区数据区索引区索引区溢出区溢出区Data StructureData StructurePage 142022-5-21q ISAMISAM文件的检索文件的检索v查主索引（驻内存），

13、将相应柱面索引（在其柱面上）调用内存。查主索引（驻内存），将相应柱面索引（在其柱面上）调用内存。v查柱面索引，将磁道索引（一般放在第查柱面索引，将磁道索引（一般放在第0 0道上）调入内存；道上）调入内存；v查磁道索引，将本磁道上的所有记录送入内存；查磁道索引，将本磁道上的所有记录送入内存；v顺序对这一组记录查找。顺序对这一组记录查找。q ISAMISAM文件的插入文件的插入v定位应插入的磁道；定位应插入的磁道；v按关键字顺序插入新纪录，将同一磁道上最后一个记录移至溢出按关键字顺序插入新纪录，将同一磁道上最后一个记录移至溢出区；区；v同时修改磁道索引项。同时修改磁道索引项。Data Struct

14、ureData StructurePage 152022-5-21q ISAMISAM文件的删除文件的删除v找到待删除的记录，在其存储位置上作删除标记即可，而不需要找到待删除的记录，在其存储位置上作删除标记即可，而不需要移动记录或改变指针。移动记录或改变指针。q ISAMISAM文件的整理文件的整理v经过多次的增删后，文件的结构可能变得很不合理。此时，大量经过多次的增删后，文件的结构可能变得很不合理。此时，大量得记录进入溢出区，而基本区中又浪费很多空间。因此，通常需得记录进入溢出区，而基本区中又浪费很多空间。因此，通常需要周期地整理要周期地整理ISAMISAM文件。文件。v把记录读入内存，重新

15、排列，复制成一个新的把记录读入内存，重新排列，复制成一个新的ISAMISAM文件，填满基文件，填满基本区而空出溢出区。本区而空出溢出区。Data StructureData StructurePage 162022-5-21q VSAMVSAM（虚拟存储存取方法）（虚拟存储存取方法）v利用了操作系统的虚拟存储器的功能，给用户提供方便。利用了操作系统的虚拟存储器的功能，给用户提供方便。v对用户来说，存储记录时不需要考虑记录的具体存储位置，也不对用户来说，存储记录时不需要考虑记录的具体存储位置，也不需要考虑何时执行对外存的读写命令。需要考虑何时执行对外存的读写命令。q VSAMVSAM文件结构文件

16、结构v三部分组成：索引集、顺序集和数据集。三部分组成：索引集、顺序集和数据集。Data StructureData StructurePage 172022-5-2159 9759 9715 44 5915 44 5972 9772 9710 1510 1521 37 4421 37 4451 5951 5963 7263 7285 91 9785 91 97索引集索引集顺顺序序集集数数据据集集控制区间控制区间控制区域控制区域Data StructureData StructurePage 182022-5-21q VSAMVSAM文件的检索文件的检索v在控制区间上存取一个记录时，需从控制区间

17、两端出发，同时向在控制区间上存取一个记录时，需从控制区间两端出发，同时向中间扫描。中间扫描。q VSAMVSAM文件的插入文件的插入v新记录插入到相应的控制区间内，移动其它记录，保持有序；新记录插入到相应的控制区间内，移动其它记录，保持有序；v控制区已满时，要进行控制区的分裂，即将一半的记录移入另一控制区已满时，要进行控制区的分裂，即将一半的记录移入另一个控制区间，并修改顺序集中相应索引。个控制区间，并修改顺序集中相应索引。q VSAMVSAM文件的删除文件的删除v删除记录时，需将同一控制区间中记录关键字较大的记录向前移删除记录时，需将同一控制区间中记录关键字较大的记录向前移动，把空间留给以后

18、插入的新记录。动，把空间留给以后插入的新记录。v控制区间变空时，则需修改顺序集中相应的索引项。控制区间变空时，则需修改顺序集中相应的索引项。Data StructureData StructurePage 192022-5-21q VSAMVSAM文件缺点文件缺点v占有较多的存储空间，一般只能保持约占有较多的存储空间，一般只能保持约76%76%的存储空间利用率。的存储空间利用率。q VSAMVSAM文件优点文件优点v动态地分配和释放存储空间，不需要对文件进行重组。动态地分配和释放存储空间，不需要对文件进行重组。v能较快地对插入的记录进行查找，查找一个后插入的记录和查找能较快地对插入的记录进行查

19、找，查找一个后插入的记录和查找一个原有记录的时间是相同的。一个原有记录的时间是相同的。Data StructureData StructurePage 202022-5-21q 散列文件特点散列文件特点v由记录的关键码由记录的关键码“直接直接”得到记录在外存（磁盘）上的映象地址。得到记录在外存（磁盘）上的映象地址。v类似哈希表，根据文件中关键码的特点设计一种类似哈希表，根据文件中关键码的特点设计一种“哈希函数哈希函数”和和“处理冲突的方法处理冲突的方法”，然后将记录散列到外存储设备上，故称，然后将记录散列到外存储设备上，故称“散散列文件列文件”。q 桶桶v散列文件的存储单位，以磁道或块为单位，

20、由若干个记录组成。散列文件的存储单位，以磁道或块为单位，由若干个记录组成。q 基桶基桶v一个桶能存放一个桶能存放m m个记录，表示这个记录，表示这m m个有相同哈希函数值的记录具有同个有相同哈希函数值的记录具有同一个桶地址，该桶称为一个桶地址，该桶称为“基桶基桶” ” 。q 溢出桶溢出桶v当发生当发生“溢出溢出”时，需要将第时，需要将第m+1m+1个同义词存放到另一个桶中。个同义词存放到另一个桶中。Data StructureData StructurePage 212022-5-21v溢出桶可以有多个，它们和基桶大小相同，相互之间用指针相链接。溢出桶可以有多个，它们和基桶大小相同，相互之间用

21、指针相链接。v当在基桶中没有找到待查记录时，就顺指针所指到溢出桶中进行查当在基桶中没有找到待查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢出桶和基桶在磁盘上的物理位置找。因此，希望同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。不要相距太远，最好在同一柱面上。 桶编号 基桶 溢出桶 28 14 21 35 8 93 9 16 81 11 19 89 33 13 55 69 62 34 图 10-6 散列文件示例 Data StructureData StructurePage 222022-5-21q 主关键字文件的主关键字文件的特点特点v在对

22、文件进行检索操作时，不仅对主关键字进行简单询问，还经在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其他类型的询问检索。因此，对多关键字常需要对次关键字进行其他类型的询问检索。因此，对多关键字文件，尚需建立一系列的次关键字索引。文件，尚需建立一系列的次关键字索引。q 次关键字索引与主关键字索引所不同次关键字索引与主关键字索引所不同v每个索引项应包含次关键字、具有同一次关键字的多个记录的主每个索引项应包含次关键字、具有同一次关键字的多个记录的主关键字或或物理记录号。关键字或或物理记录号。q 多重表文件和倒排文件是两种多关键字文件的组织方法。多重表文件和倒排文件是两种多

23、关键字文件的组织方法。Data StructureData StructurePage 232022-5-21q 多重表文件（多重表文件（MultilistMultilist file file）的特点）的特点v记录按主关键字的顺序构成一个串联文件，建立主关键字的索引记录按主关键字的顺序构成一个串联文件，建立主关键字的索引（称为主索引）；（称为主索引）；v对每个次关键字项建立次关键字索引（称为次索引），所有具有对每个次关键字项建立次关键字索引（称为次索引），所有具有同一次关键字的记录构成一个链表。同一次关键字的记录构成一个链表。v主索引为非稠密索引（一组记录建立一个索引项），次索引为稠主索引为

24、非稠密索引（一组记录建立一个索引项），次索引为稠密索引（每个记录建立一个索引项）。每个索引包括次关键字、密索引（每个记录建立一个索引项）。每个索引包括次关键字、头指针和链表长度。头指针和链表长度。v在多重表中插入一个新记录是很容易的，只要修改指针，将记录在多重表中插入一个新记录是很容易的，只要修改指针，将记录插在链表的头指针之后。但是，要删去一个记录却很繁琐，需要插在链表的头指针之后。但是，要删去一个记录却很繁琐，需要在每个次关键字的链表中删去该记录。在每个次关键字的链表中删去该记录。Data StructureData StructurePage 242022-5-21Data Struct

25、ureData StructurePage 252022-5-21q 倒排文件（倒排文件（Inverted fileInverted file）和多重表文件的）和多重表文件的区别区别v次关键字索引的结构不同。次关键字索引的结构不同。 q 倒排表倒排表v倒排文件中的次关键字索引倒排文件中的次关键字索引。 v在倒排表的索引项中没有头指针和链表长度项，而直接用一项存在倒排表的索引项中没有头指针和链表长度项，而直接用一项存放具有同一关键字的所有记录的物理记录号或主关键字。放具有同一关键字的所有记录的物理记录号或主关键字。 Data StructureData StructurePage 262022-

26、5-21Data StructureData StructurePage 272022-5-21q 顺序文件顺序文件v文件中记录的物理顺序和逻辑顺序一致。文件中记录的物理顺序和逻辑顺序一致。v对顺序存储器上的顺序文件只能进行顺序存取；对直接存储器上对顺序存储器上的顺序文件只能进行顺序存取；对直接存储器上的顺序文件还可按记录号或关键码进行随机存取；如果是定长记的顺序文件还可按记录号或关键码进行随机存取；如果是定长记录的顺序有序文件，还可利用折半查找进行快速存取。录的顺序有序文件，还可利用折半查找进行快速存取。v插入记录可以插入在文件的末尾或先存入附加文件。插入记录可以插入在文件的末尾或先存入附加

27、文件。v删除记录仅在原地作标志。删除记录仅在原地作标志。v更新记录需对整个文件进行复制。更新记录需对整个文件进行复制。v更多情况下对顺序文件的操作是按批处理方式进行的。更多情况下对顺序文件的操作是按批处理方式进行的。Data StructureData StructurePage 282022-5-21q 索引文件索引文件v对文件中的每个记录都建立一个由记录的关键码和存储地址构成对文件中的每个记录都建立一个由记录的关键码和存储地址构成的索引项。所有记录的索引项构成一个按关键码有序的索引表。的索引项。所有记录的索引项构成一个按关键码有序的索引表。v索引表可以是顺序结构，也可以是查找树结构，对索引文件可以索引表可以是顺序结构，也可以是查找树结构，对索引文件可以进行直接存取或按关键码存取。进行直接存取或按关键码存取。v按关键码存取时，首先在索引中进行查找，然后按索引项中指示按关键码存取时，首先在索引中进行查找，然后按索引项中指示的存储地址进行存取。的存储地址进行存取。v插入记录时，记录本身可插入在主文件的末尾，同时将相应的索插入记录时，记录本身可插入在主文件的末尾，同时将相应的索引项插入索引中恰当位置。引项插入索引中恰当位置。v删除记录仅需删除相应的索引项。删除记录仅需删除相应的索引项。v更新记录时，可将更新后的记录插入在主文件的末尾，同时修改更新记录时，可