程序设计与数据结构

数据结构第8章文件山东大学管理学院2020/1/24山东大学管理学院戚桂杰姚云鸿2本章内容•文件概述•顺序文件•直接文件•索引文件倒排文件2020/1/24山东大学管理学院戚桂杰姚云鸿3§1文件概述一、文件的概念•域（Field）是数据的基本单位，又称为字段或数据项。域通常用于描述数据对象的属性，不可分割的域含有一个简单的值。•记录（Record）是一组相关域的集合，它可以看作是应用程序的一个单元。根据设计的不同，记录可以是固定长或可变长。如果记录中某些域的长度是可变的，则该记录就是可变长度的记录。•文件（File）是由大量性质相同的记录组成的集合，它被应用程序看作是一个实体。文件有一个惟一的名字，可以被创建或删除。•数据库（Database）是一组相关的数据，它的本质特征是数据单元间存在明确的关系，并且设计成可供许多不同的应用程序使用。数据库自身是由一种或多种不同类型的文件组成。2020/1/24山东大学管理学院戚桂杰姚云鸿4二、文件的逻辑结构•文件的逻辑结构是用户能观察到的，可加以处理的数据集合。•文件的逻辑结构分两种形式：一种是流式文件，另一种是记录式文件。•记录成组与分解处理流式文件指文件内的数据不再组织成记录，只是连续的字符序列。记录式文件是指若干逻辑记录（按信息在逻辑上的独立含意划分的一个信息单位）的集合。逻辑记录1逻辑记录2逻辑记录3物理记录逻辑记录用户缓冲区系统缓冲区2020/1/24山东大学管理学院戚桂杰姚云鸿5三、文件的物理结构构造文件物理结构的方法：计算法和指针法。四、文件的操作•记录检索•记录插入•记录删除•记录更新•文件排序实现原理是设计映射算法，通过对记录关键字的计算转换成对应的物理块地址，从而找到所需记录。置专门指针，指明相应记录的物理地址或表达各记录之间的关联。2020/1/24山东大学管理学院戚桂杰姚云鸿6§2顺序文件•分块块插值查找算法：（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)查找失败，算法结束。)(lowhighKKKKlowlhllow:查找范围内的最小物理块号；high:查找范围内的最大物理块号；Li：第i个物理块内的记录的最小关键字；Hi：第i个物理块内的记录的最大关键字2020/1/24山东大学管理学院戚桂杰姚云鸿7§3直接文件（散列文件）直接文件：记录在介质上的位置是通过对记录的键施加变换而获得相应地址。一、桶散列（静态散列）基本思想：把文件的记录通过散列函数H分别存储在许多存储桶中，每个存储桶包含一个或多个物理块，一个存储桶中的物理块用指针连接形成链表，每个物理块存放若干记录。如果一个桶溢出，即它容纳不下所有属于它的记录，那么可以给该存储桶增加一个溢出块链表以存放更多的记录。操作：以i=H(key)为依据完成查找、插入、删除、更新等操作。2020/1/24山东大学管理学院戚桂杰姚云鸿8§3直接文件（散列文件）二、可扩展散列（动态散列文件）•可散列文件的组织方式：散列函数H把关键字key转换成一个定长的二进制位串k′（伪关键字），取k′前i位二进制数（设为k〞）作为存储桶目录表中的目录项号，即表示目录表中第k〞个目录项，目录项中的指针指向的物理块就是具有关键字key的记录所在的物理块；存储桶目录项的个数为2i。i确定记录在该物理块中的成员资格的二进制位串的位数2020/1/24山东大学管理学院戚桂杰姚云鸿9•查找操作查找关键字为K的记录，先计算出H（K），取出这一二进制位串的前i位（设为k〞），并找到序号为k〞的存储桶目录项。根据此目录项的指针找到物理块B。•插入操作为了插入关键字为K的记录，先其所在的物理块，若该物理块中有空闲空间，我们就把新记录存入，插入操作完成。如果B中没有空闲空间，那么根据数字i的不同有两种可能：–如果j=i，那么我们必须先将i加1，使存储桶目录项个数增加一倍，即2i+1。在新存储桶目录表中，序号为k〞0和k〞1（分别用0和1扩展k〞）的项都指向原k〞目录项指向的物理块。2020/1/24山东大学管理学院戚桂杰姚云鸿10•插入操作–如果j＜i（j的值可在每个物理块的“小凸块”中找到），那么不必对存储桶目录表做任何变化。按下面规则操作：•（a）将物理块B分裂成两个存储块。•（b）根据记录关键字的散列值的第j+1位，将B中的记录分配到这两个存储块中，该位为0的记录继续保留在B中，而该位为1的记录放入到新块中。•（c）把j+1存储到两个存储块的“小凸块”中，以标明用于确定成员资格的二进制位数。•（d）调整存储桶目录项中指针，使原来指向块B的指针项指向块B或新块，这由记录关键字的散列值的第j+1位决定。•注意，分裂B可能解决不了问题，因为有可能块B中所有记录将分配到由B分裂成的两个存储块的其中一块中。如果这样，我们需要对仍太满的块用下一个更大的j值重复上述操作。2020/1/24山东大学管理学院戚桂杰姚云鸿11插入关键字为0000、0111的记录再插入关键字值为1000的记录2020/1/24山东大学管理学院戚桂杰姚云鸿12§4索引文件•索引文件的结构•二级索引、多级索引记录1关键字地址记录2……记录N文件名索引表块块块…数据区索引区查找①②稠密索引：每个数据记录，在索引表里都有一个索引项稀疏索引：每一组数据记录仅有一索引项2020/1/24山东大学管理学院戚桂杰姚云鸿13§5索引顺序文件一、ISAM•专为磁盘存取设计的文件组织方式，是一种静态索引结构。•ISAM采用多级索引：主索引、柱面索引、磁道索引。指示查找键字为99记录路径2020/1/24山东大学管理学院戚桂杰姚云鸿14二、VSAM•总体结构记录存放区顺序集：存放每个控制区间的索引项（该控制区间中的最大关键字和指向控制区间的指针）。若干相邻控制区间的索引项构成顺序集中的一个结点，相当于B+树的一个叶子结点。2020/1/24山东大学管理学院戚桂杰姚云鸿15•VSAM中插入操作（1）调用B+树的查找算法，确定该记录应插入的顺序集结点，进而确定该记录应插入的控制区间及相应位置。（2）如果该控制区间中自由空间足以容纳该记录，则将要插入位置右面的记录右移腾出空间插入该记录，并在相应位置建立控制信息。（3）如果自由空间不够，则检查该控制区间所在的控制域中是否还有空闲的控制区间，若有，则将控制区间分裂，将其中的近似一半的记录移动到一个空闲的控制区间中。如无，则进行一次控制域的分裂。2020/1/24山东大学管理学院戚桂杰姚云鸿16插入ARS、BIT插入BEC2020/1/24山东大学管理学院戚桂杰姚云鸿17§6倒排文件关键字指针组倒排表具有这种倒排表形式的索引文件称为倒排文件（ReverseFile）具有相同关键字的记录倒排表作索引的好处在于检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。倒排文件的缺点是维护困难。2020/1/24山东大学管理学院戚桂杰姚云鸿18§7本章小结1．文件概述（1）文件是由大量性质相同的记录组成的集合，它被应用程序看作是一个实体。（2）文件的逻辑结构是用户能观察到的，可加以处理的数据集合。文件的逻辑结构分两种形式：一种是流式文件，另一种是记录式文件。（3）文件物理结构的构造方法：（1）计算法，通过对记录关键字的计算转换成对应的物理块地址，从而找到所需记录。（2）指针法，这类方法设置专门指针，指明相应记录的物理地址或表达各记录之间的关联。索引文件、索引顺序文件、倒排文件等均属此类。（4）对文件的操作主要有记录的检索、插入、删除、更新和文件排序。2．顺序文件（1）将一个文件中逻辑上连续的信息存放到存储介质的依次相邻的块上便形成顺序结构，这类文件叫顺序文件，又称连续文件。（2）掌握顺序文件上的物理块插值查找。2020/1/24山东大学管理学院戚桂杰姚云鸿19§7本章小结3．直接文件（散列文件）（1）在直接存取存储设备上，记录的关键字与其地址之间可以通过某种方式建立对应关系，利用这种关系实现存取的文件叫直接文件。（2）桶散列方法的基本思想是把文件的记录通过散列函数H分别存储在许多存储桶中，每个存储桶包含一个或多个物理块，一个存储桶中的物理块用指针连接形成链表，每个物理块存放若干记录。4．索引文件（1）索引结构是实现非连续存储的另一种方法，适用于数据记录保存在随机存取存储设备上的文件。索引文件在文件存储器上分两个区：索引区和数据区。（2）索引文件中的索引项可以分为两类：稠密索引和稀疏索引。5．索引顺序文件（1）索引顺序存取方式ISAM是一种专为磁盘存取设计的文件组织方式，是一种静态索引结构。（2）VSAM的总体结构由三部分组成：索引集、顺序集和数据集。文件的记录均存放在数据集中，顺序集也是文件索引的一部分，顺序集和索引集一起形成一棵B+树结构的文件索引。6．倒排文件（1）把具有这种倒排表形式的索引文件称为倒排文件。（2）倒排表作索引的好处在于检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。