数据结构 第8章 文件 山东大学管理学院

本章内容 文件概述 顺序文件 直接文件 索引文件倒排文件 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

§ 1 文件概述 一、 文件的概念 域（Field）是数据的基本单位，又称为字段或数据项。域通常用于描述数据对象的属性，不可分割的域含有一个简单的值。 记录（Record）是一组相关域的集合，它可以看作是应用程序的一个单元。根据设计的不同，记录可以是固定长或可变长。如果记录中某些域的长度是可变的，则该记录就是可变长度的记录。 文件（File）是由大量性质相同的记录组成的集合，它被应用程序看作是一个实体。文件有一个惟一的名字，可以被创建或删除。 数据库（Database）是一组相关的数据，它的本质特征是数据单元间存在明确的关系，并且设计成可供许多不同的应用程序使用。数据库自身是由一种或多种不同类型的文件组成。 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

文件的逻辑结构是用户能观察到的，可加以处理的数据集合。 文件的逻辑结构分两种形式：一种是流式文件，另一种是记录式文件。 二、文件的逻辑结构 文件的逻辑结构是用户能观察到的，可加以处理的数据集合。 文件的逻辑结构分两种形式：一种是流式文件，另一种是记录式文件。 记录成组与分解处理 记录式文件是指若干逻辑记录（按信息在逻辑上的独立含意划分的一个信息单位）的集合。 流式文件指文件内的数据不再组织成记录，只是连续的字符序列。 逻辑记录1 逻辑记录2 逻辑记录3 物理记录 逻辑记录 用户缓冲区 系统缓冲区 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

构造文件物理结构的方法：计算法和指针法。 三、 文件的物理结构 构造文件物理结构的方法：计算法和指针法。 四、文件的操作 记录检索 记录插入 记录删除 记录更新 文件排序 实现原理是设计映射算法，通过对记录关键字的计算转换成对应的物理块地址，从而找到所需记录。 置专门指针，指明相应记录的物理地址或表达各记录之间的关联。 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

§ 2 顺序文件 分块块插值查找 算法： (a)i = （1）初始化 low = 1；high=N。 （2）反复执行下面操作，直到high＜low成立 (a)i = (b)读取第i个物理块，获得Li和Hi (c)分下面三种情况执行 Li≤K≤Hi时，查找成功，第i个物理块即为所求; K＞Hi时，执行low = i+1; K＜Li时，执行high = i-1; (3)查找失败，算法结束。 low:查找范围内的最小物理块号； high: 查找范围内的最大物理块号； Li：第i个物理块内的记录的最小关键字； Hi：第i个物理块内的记录的最大关键字 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

§ 3 直接文件（散列文件） 直接文件：记录在介质上的位置是通过对记录的键施加变换而获得相应地址。 一、桶散列 （静态散列） 基本思想： 把文件的记录通过散列函数H分别存储在许多存储桶中，每个存储桶包含一个或多个物理块，一个存储桶中的物理块用指针连接形成链表，每个物理块存放若干记录。如果一个桶溢出，即它容纳不下所有属于它的记录，那么可以给该存储桶增加一个溢出块链表以存放更多的记录。 操作：以i=H(key) 为依据完成查找、插入、删除、更新等操作。 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

§ 3 直接文件（散列文件） 二、 可扩展散列（动态散列文件） i 可散列文件的组织方式：散列函数H把关键字key转换成一个定长的二进制位串k′（伪关键字），取k′前i位二进制数（设为k〞）作为存储桶目录表中的目录项号，即表示目录表中第k〞个目录项，目录项中的指针指向的物理块就是具有关键字key的记录所在的物理块；存储桶目录项的个数为2i。 i 确定记录在该物理块中的成员资格 的二进制位串的位数 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

查找操作 查找关键字为K的记录，先计算出H（K），取出这一二进制位串的前i位（设为k〞），并找到序号为k〞的存储桶目录项。根据此目录项的指针找到物理块B。 插入操作 为了插入关键字为K的记录，先其所在的物理块，若该物理块中有空闲空间，我们就把新记录存入，插入操作完成。如果B中没有空闲空间，那么根据数字i的不同有两种可能： 如果j=i，那么我们必须先将i加1，使存储桶目录项个数增加一倍，即2i+1。在新存储桶目录表中，序号为k〞0和k〞1（分别用0和1扩展k〞）的项都指向原k〞目录项指向的物理块。 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

如果j＜i（j的值可在每个物理块的“小凸块”中找到），那么不必对存储桶目录表做任何变化。按下面规则操作： 插入操作 如果j＜i（j的值可在每个物理块的“小凸块”中找到），那么不必对存储桶目录表做任何变化。按下面规则操作： （a）将物理块B分裂成两个存储块。 （b）根据记录关键字的散列值的第j+1位，将B中的记录分配到这两个存储块中，该位为0的记录继续保留在B中，而该位为1的记录放入到新块中。 （c）把j+1存储到两个存储块的“小凸块”中，以标明用于确定成员资格的二进制位数。 （d）调整存储桶目录项中指针，使原来指向块B的指针项指向块B或新块，这由记录关键字的散列值的第j+1位决定。 注意，分裂B可能解决不了问题，因为有可能块B中所有记录将分配到由B分裂成的两个存储块的其中一块中。如果这样，我们需要对仍太满的块用下一个更大的j值重复上述操作。 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

再插入关键字值为1000的记录 插入关键字为0000、0111的记录 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

§ 4 索引文件 索引文件的结构 二级索引、多级索引 索引区 数据区 ① 查找 ② 稠密索引：每个数据记录，在索引表里都有一个索引项 § 4 索引文件 索引文件的结构 二级索引、多级索引 索引区 记录1 关键字 地址 记录2 … 记录N 文件名 索引表 块 数据区 ① 查找 ② 稠密索引：每个数据记录，在索引表里都有一个索引项 稀疏索引：每一组数据记录仅有一索引项 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

§ 5 索引顺序文件 一、ISAM 专为磁盘存取设计的文件组织方式，是一种静态索引结构。 ISAM采用多级索引：主索引、柱面索引、磁道索引。 § 5 索引顺序文件 一、ISAM 专为磁盘存取设计的文件组织方式，是一种静态索引结构。 ISAM采用多级索引：主索引、柱面索引、磁道索引。 指示 查找键字为99记录路径 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

二、VSAM 总体结构 记录存放区 顺序集：存放每个控制区间的索引项（该控制区间中的最大关键字和指向控制区间的指针）。若干相邻控制区间的索引项构成顺序集中的一个结点，相当于B+树的一个叶子结点 。 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

（1）调用B+树的查找算法，确定该记录应插入的顺序集结点，进而确定该记录应插入的控制区间及相应位置。 VSAM中插入操作 （1）调用B+树的查找算法，确定该记录应插入的顺序集结点，进而确定该记录应插入的控制区间及相应位置。 （2）如果该控制区间中自由空间足以容纳该记录，则将要插入位置右面的记录右移腾出空间插入该记录，并在相应位置建立控制信息。 （3）如果自由空间不够，则检查该控制区间所在的控制域中是否还有空闲的控制区间，若有，则将控制区间分裂，将其中的近似一半的记录移动到一个空闲的控制区间中。如无，则进行一次控制域的分裂。 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

插入ARS、BIT 插入BEC 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

§ 6 倒排文件 倒排表 关键字 指针组 具有这种倒排表形式的索引文件称为倒排文件（Reverse File） § 6 倒排文件 倒排表 具有相同关键字的记录 关键字 指针组 具有这种倒排表形式的索引文件称为倒排文件（Reverse File） 倒排表作索引的好处在于检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。 倒排文件的缺点是维护困难。 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

§ 7 本章小结 1．文件概述 （1）文件是由大量性质相同的记录组成的集合，它被应用程序看作是一个实体。 （2）文件的逻辑结构是用户能观察到的，可加以处理的数据集合。文件的逻辑结构分两种形式：一种是流式文件，另一种是记录式文件。 （3）文件物理结构的构造方法：（1）计算法，通过对记录关键字的计算转换成对应的物理块地址，从而找到所需记录。（2）指针法，这类方法设置专门指针，指明相应记录的物理地址或表达各记录之间的关联。索引文件、索引顺序文件、倒排文件等均属此类。 （4）对文件的操作主要有记录的检索、插入、删除、更新和文件排序。 2．顺序文件 （1）将一个文件中逻辑上连续的信息存放到存储介质的依次相邻的块上便形成顺序结构，这类文件叫顺序文件，又称连续文件。 （2）掌握顺序文件上的物理块插值查找。 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿

§ 7 本章小结 3．直接文件（散列文件） （1）在直接存取存储设备上，记录的关键字与其地址之间可以通过某种方式建立对应关系，利用这种关系实现存取的文件叫直接文件。 （2）桶散列方法的基本思想是把文件的记录通过散列函数H分别存储在许多存储桶中，每个存储桶包含一个或多个物理块，一个存储桶中的物理块用指针连接形成链表，每个物理块存放若干记录。 4．索引文件 （1）索引结构是实现非连续存储的另一种方法，适用于数据记录保存在随机存取存储设备上的文件。索引文件在文件存储器上分两个区：索引区和数据区。 （2）索引文件中的索引项可以分为两类：稠密索引和稀疏索引。 5．索引顺序文件 （1）索引顺序存取方式ISAM是一种专为磁盘存取设计的文件组织方式，是一种静态索引结构。 （2）VSAM的总体结构由三部分组成：索引集、顺序集和数据集。文件的记录均存放在数据集中，顺序集也是文件索引的一部分，顺序集和索引集一起形成一棵B+树结构的文件索引。 6．倒排文件 （1）把具有这种倒排表形式的索引文件称为倒排文件。 （2）倒排表作索引的好处在于检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。 2017/3/5 山东大学管理学院 戚桂杰 姚云鸿