中国地质大学（武汉）：《数据结构和VC编程》课程教学资源（课件讲稿）第九章 文件

第九章文件 9.1有关文件的基本概念和文件的存储结构 1、有关基本概念 (1)、记录、关键字 (2)、文件 (3)、记录的逻辑结构和物理结构 PT PRESS 退出 续不一

第 九 章 文件 9．1有关文件的基本概念和文件的存储结构 1、有关基本概念 （1）、记录、关键字 ( 2 ) 、文件 （3）、记录的逻辑结构和物理结构 退出

6、文件的存储结构 (1)、顺序结构 (2)、计算寻址结构 (3)、索引结构 (4)、表结构 7、选择文件的存储结构应考虑哪些因素？ (1)外存的种类 (2)、询问的类型 (3)、操作类型 (4)操作方式 PT PRESS 然东续了一列

6、文件的存储结构 （1）、顺序结构 ( 2 )、计算寻址结构 ( 3 )、索引结构 ( 4 )、表结构 7、选择文件的存储结构应考虑哪些因素？ ( 1 )、外存的种类 ( 2 )、询问的类型 ( 3 )、操作类型 ( 4 )、操作方式

9.2顺序文件 9.2.1存储在顺序存储器上的顺序文件 1、顺序查找 2、更新 9.2.2存储在直接存取存储器上的顺序文件 1、随机查找 设当前查找范围内的最低和最高块号分别为ow 和high,相应的最低和最高关键字分别为keylow和 keyhigh; 设待查关键字为aidkey,.待比较的块号为i,它 的最低和最高关键字分别为blokeymin,blokeymax; PT PRESS 续下一

9．2顺序文件 9．2．1 存储在顺序存储器上的顺序文件 1、顺序查找 2、更新 9．2．2 存储在直接存取存储器上的顺序文件 1、随机查找 设当前查找范围内的最低和最高块号分别为low 和high，相应的最低和最高关键字分别为keylow和 keyhigh； 设待查关键字为aidkey，待比较的块号为i，它 的最低和最高关键字分别为blokeymin，blokeymax；

插值查找的算法步骤如下： (1)、置初值 low=1;high=n;keylow=keymin;keyhigh=keymax; (2)、计算待比较的块号i i=low+(aidkey-keylow)/(keyhigh-keylow)*(high-low); (3)、调入第i块，查得blokeymin,blokeymax; PT PRESS 按续不一列

插值查找的算法步骤如下： （1）、置初值 low=1; high=n; keylow=keymin; keyhigh=keymax; （2）、计算待比较的块号i i=low+(aidkey-keylow)/(keyhigh-keylow)*(high-low); （3）、调入第i块，查得blokeymin，blokeymax；

(4)、若blokeymin-.blokeymax)则：low=it1;keylow= blokeymax; 若aidkey<-blokeymin则：high=i-l; keyhigh=blokeymin; 若high<low则查找失败结束，否则重复（(2) 到(4) PT PRESS 然东续了一列

（4）、若blokeymin blokeymax则： low=i+1; keylow= blokeymax; 若aidkey<blokeymin则： high=i-1; keyhigh=blokeymin; 若high<low则查找失败结束，否则重复（2） 到（4）

2、更新 9.2.3堆文件 9.3索引文件和索引顺序文件 1、建立稠密索引B树 2、索引文件的查找、插入、删除 9.3.2索引顺序文件 1、建立非稠密索引B+树 3、索引顺序文件的查找、插入、删除 PT PRESS 然东续了一列

2、更新 9．2．3堆文件 9．3索引文件和索引顺序文件 1、建立稠密索引B树 2、索引文件的查找、插入、删除 9．3．2索引顺序文件 1、建立非稠密索引B+树 3、索引顺序文件的查找、插入、删除

9.3.3对于B树、B+树需要注意的问题 ,7 B C B 2356 9 1012 23 5 6 9 1012 (a) (b) 图9-1 PT PRESS 然东续了一 n

9．3．3对于B树、B+树需要注意的问题 图9-1

A A 9、 4 9 F B H F 4 10 2 10 13 E 8 (a) (b) 图9-2 PT PRESS 然东续了一 n

图9-2

9.4哈希文件（也称为散列文件或直接存取文件） 9.4.1文件组织方式 桶目录表 0 A 2 m-2 m-1 A 图9-3 PT PRESS

9．4哈希文件（也称为散列文件或直接存取文件） 9．4．1文件组织方式 图9-3

9.4.2文件的操作 查找、修改、插入、删除 9.4.3文件的扩充 9.5多关键字文件 9.5.1索引链接文件（多重表文件） PT PRESS 按续不一列 n

9．4．2文件的操作 查找、修改、插入、删除 9．4．3文件的扩充 9．5多关键字文件 9．5．1索引链接文件（多重表文件）