数据结构课程讲义.pptVIP

10.1基本概念 10.1基本概念 10.1基本概念 10.1基本概念 10.1基本概念 按关键字进行检索时，从第三查找表 开始，至多访问外存五次。 索引表采用查找树表或哈希表。优点： 1）不需要建立多级索引； 2）初建索引不需要进行排序； 3）插入或删除记录时，修改索引方便。 ２．动态索引 用查找树表作索引时，查找索引所 需访问外存次数的最大值恰为查找 树的深度。 稠密索引的优点是，可以实现“预查找” 缺点是，索引表占用的存储空间大。 可以作索引的树表有：二叉排序树、 B-树和键树。 10.5 索 引 顺 序 文 件 主文件按主关键字有序，对一组记 录建立一个索引项(建立非稠密索引)。 结构特点： 一、ISAM文件 ISAM(Index Sequential Access Method) (索引顺序存取方法)是一种专为磁 盘存取设计的文件组织方法。 有两种典型的索引顺序文件： １．文件的组织方式： 主文件按柱面集中存放，同时建立 三级索引：磁道索引、柱面索引和 主索引。 关键字 指针 关键字 指针 磁道索引结构 基本索引项 溢出索引项 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文件， 需要周期 地进行重整。 ４．柱面索引的位置 ISAM文件占有多个柱面，其柱 面索引本身占有一个柱面，为使“磁头”的平均移动距离最小，柱面索引应设在数据文件所占全部柱面的中间位置上。 二、VSAM文件 VSAM(Vistual Storage Access Method) 文件是利用操作系统中提供的虚拟存储器的功能组织的文件，免除了用户为读/写记录时直接对外存进行的操作，对用户而言，文件只有控制区间和控制区域等逻辑存储单位。 … ... ... ... ... 索引集 B+树 顺序集 控制区域 控制区间 数据集 1．文件的结构 2. 控制区间是用户进行一次存取的 逻辑单位，可看成是一个逻辑磁道。 但它的实际大小和物理磁道无关。 VSAM文件初建时，每个控制区 间内的记录数不足额定数，并且有的 控制区间内的记录数为零。 控制区域由若干控制区间和它们 的索引项组成，可看成是一个逻辑柱面。 ３．顺序集本身是一个单链表，它 包含文件的全部索引项，同时，顺 序集中的每个结点即为B+树的叶子 结点，索引集中的结点即为B+树的 非叶结点。 * * Chapter 10 文 件 10.2 有关文件的基本概念 10.3 顺 序 文 件 10.4 索 引 文 件 10.5 索 引 顺 序 文 件 10.6 直 接 存 取 文 件 10.7 多 关 键 字 文 件 10.1基本概念 10.1常用外存： 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末 端记录时）。 . . 读出头 写入头 原始盘 接收盘 IBG（Inter Block Gap）块间间隙 块 1 块 3 块 2 带文件的读写 时间：T i/o = ta + n × tw ta ：延迟时间 tw：传输时间/ 字符 n 字符