数据结构12要点解析.ppt

主文件按主关键字有序，对一组记 录建立一个索引项(建立非稠密索引)。 结构特点： 12.4 索引顺序文件 一、ISAM文件 ISAM(Index Sequential Access Method) (索引顺序存取方法)是一种专为磁 盘存取设计的文件组织方法。 有两种典型的索引顺序文件： 1.文件的组织方式： 主文件按柱面集中存放，同时建立 三级索引：磁道索引、柱面索引和 主索引。 磁道索引结构 关键字 指针 关键字 指针 基本索引项 溢出索引项 210 1024 主 索 引 r(14) r(21) r(38) r(41) r(57) r(63) r(72) r(85) r(99) 溢出区 磁道索引 r(514) … … 溢出区 磁道索引 … … r(1024) 一 个 柱 面 …. 柱 面 索 引 99 210 1024 T0 T1 T2 T3 T4 T5 ２.操作的特点： 检 索 插入 删除 检索： 可有两种方式： 按关键字存取—从主索引开始,到柱面索引，到磁道索引，最后取得记录，先后访问四次外存。 顺序存取— 依关键字最小至大顺序存取。 插入: 修改本磁道的索引项(包括基本索引项 和溢出索引项)。 将该磁道上关键字最大的记录移出到本柱面的溢出区中; 将记录插入在某个磁道的合适位置上; 删除: 在被删记录当前存储位置上作“删 除标记”。 ３．文件重组 在经过多次的插入和删除操作后，大量的记录进入文件的“溢出区”，而“基本存储区”中出现很多已被删去的记录空间，此时的文件结构很不合理。 因此,对ISAM文件,需要周期地进行重整。 4.柱面索引的位置 ISAM文件占有多个柱面，其柱面索引本身占有一个柱面，为使“磁头”的平均移动距离最小，柱面索引应设在数据文件所占全部柱面的中间位置上。 * * 第十二章 文 件 12.1 有关文件的基本概念 12.2 顺序文件 12.3 索引文件 12.4 索引顺序文件 12.5 直接存取文件 12.6 多关键字文件 12.1 有关文件的基本概念 一、文件即为记录的集合，和“查找表”的差别在于，“文件”指的是存储在外存储器中的记录的集合。记录是文件中可以存取的数据的基本单位。 二、文件可按其中记录的类型不同而分成两类： 其一为操作系统的文件，文件中的记录仅是一个字符组。由于操作系统中的文件仅是一维的连续字符序列，为了用户存取和加工的方便，将文件中的信息划分为若干组，其中每一组信息称作一个记录； 其二为数据库文件，文件中的记录带 有结构，是数据项的集合。记录是文件中可以存取的数据基本单位，数据项是文件中可以使用的数据最小单位。 三、记录中能识别不同记录的数据项被称为关键字，若该数据项能唯一识别一个记录，则称为主关键字，若能识别多个记录则称为次关键字。 四、文件的逻辑结构指的是呈现在用户面 前的文件中记录之间的逻辑关系；文件的 物理结构指的是文件中的逻辑记录在存储 器中的组织方式。 五、文件的操作： 检索 修改 排序 1.检索 顺序存取：存取“当前记录的”下一个记录； 直接存取：存取第i个记录； 按关键字存取：存取其关键字等于给定值的记录。 2.修改 往文件中插入一个或一批记录； 更新文件中某个记录的属性。 从文件中删除一个或一批记录； 文件的操作方式可以实时处理或 批量处理。 3.排序 本章讨论文件的几种常见的物理结构： 顺序文件 索引文件 索引顺序文件 直接存取文件 多关键字文件 结构特点： 记录在文件中的排列顺序是由记录进入存储介质的次序决定的， 即文件物理结构中记录的排列顺序和文件的逻辑结构中记录的排列顺序一致。 12.2 顺序文件 顺序文件的具体组织形式有两种： 串联文件：物理记录之间的顺序由指针相 链。 连续文件：次序相继的两个物理记录存储 位置相邻； 操作特点： 1.便于进行顺序存取； 2.不便于进行直接存取，为取第i个记录，必须先读出前i-1个记录，对于磁盘上的等长记录的连续文件可以进行折半查找； 3.插入新的记录只能加在文件的末尾； 4.删除记录时，只作标记； 5.更新记录必须生成新的文件。 顺序文件的插入、删除和更新操 作在多数情况下都采用批处理方式。 此时，为处理方便，通常将顺序文件 作成有序文件，称作“主文件”，同时将 所有的操作作成一个“事务文件”（经过 排序也成为有序文件），所谓“批处理”， 就是将这两个文件“合”为一个新的主文 件。具体操作相当于“归并两个有序表”。 （1）对于事务文件中的每个操作先要 判别其