数据结构——文件.ppt

《数据结构——文件.ppt》由会员分享，可在线阅读，更多相关《数据结构——文件.ppt（53页珍藏版）》请在课桌文档上搜索。

1、第十章 文 件,文件的应用背景，数据结构范畴的文件概念。基于检索的文件的基本形式与特点。常用的文件方式和关键技术实现要点。,学习要点：,10.1.1 文件 文件（file）文件是性质相同、逻辑上相关的数据记录集合。按数据记录的长度是否确定而分为定长文件和不定长文件：定长文件：文件中所有记录含有的数据项个数相同。不定长文件：文件中记录含有的数据项个数不等。,10.1 文件基本概念,按文件实际用途可以分为操作系统文件和数据库文件：操作系统文件 无严格意义下的数据结构，只是作为记录的集合，主要表现为一维无结构连续字符序列，记录之间既没有结构的解释也没有特性的解释；相应文件操作只有“整体”操作即打开或

2、关闭文件、删除文件或复制文件等；以及“字节”操作即从文件读取一个字节或将一个字节写到文件当中。数据库文件 各项记录之间具有严格的逻辑结构（例如基本的线性表结构、关系文件和面向对象文件结构等），同时每个记录也有相应结构，即数据库记录由若干数据项构成。,10.1.1 文件2,数据库文件：例：下图是一个学生学籍文件，每个学生情况形成一个记录。每个记录由学号、姓名、性别、籍贯、出生年月和住址6个数据项组成。定义“学号”是主关键字，“姓名”、“性别”等是次关键字。,10.1.1 文件3,按只有主关键字还是同时具有主关键字和次关键字而分为单关键字文件或多关键字文件：单关键字文件：记录中只有一个惟一标识记录

3、的主关键字。多关键字文件：记录中除了含有一个主关键字外还含有若干个次关键字。,10.1.1 文件4,1、文件逻辑结构作为存储在外存中的数据，文件是具有相同性质的记录集合，其逻辑结构应当为集合。但在实际操作过程中，文件中各个记录至少都是“顺次”进入计算机的，即其至少具有“工作”顺序，在这种意义下，通常将文件看作一种线性表，或者说，文件就是外存中的线性表。注意区分文件中记录的“顺序”（sequential）概念和文件记录的“有序”（order）概念。,10.1.2 文件结构与操作,2、文件存储结构 存储结构是文件在物理存储介质（磁盘或磁带）上的组织方式，它决定了文件信息在存储设备上的存储位置。顺序

4、文件 顺序文件在逻辑上是将数据记录间的顺序作为相应线性表中元素的“次序”关系，在存储上，这种顺序关系与物理存储顺序一致。索引文件 在存储的文件之外，建立一个相对于主文件用于描述文件逻辑记录与物理存储记录之间的一一关系（即文件的第i号记录对应存储的物理地址）的索引表，此时，主文件和其索引表构成的二元组就称为索引文件。散列文件 散列文件也称为哈希（hash）文件或者直接存取文件，其特点是使用散列存储方式组织文件。链式文件 链式文件中的连结点一般都比较大，同时也不定长。在文件存储方式中，链式文件通常都是结合索引文件一起使用，例如多关键字文件等。,10.1.2 文件结构与操作2,3、文件基本操作（1）

5、文件检索 文件检索就是在文件中查找满足给定条件的数据记录，实现途径可以是按照记录进入外存的时间顺序（逻辑序号）查找，也可以是按照记录的关键字大小查找。顺序检索 通过逐次读取所有序号小于i的记录，定位所需要的第i号记录。直接检索 不通过逐次读取所有序号小于i的记录而直接定位第i号记录。直接检索也称为随机检索。按关键字检索 定位关键字与给定关键字相同或相关的数据记录。简单检索：询问单个关键字等于给定值的记录。范围检索：询问单个关键字属于某个范围内的所有记录。函数检索：规定单个关键字的某个函数，询问该函数的某个值。布尔检索：以上三种询问用布尔运算(与、或、非)组合起来的询问。例如查询某成绩表中，查找

6、表中(数学成绩90)and（性别=“女”)的记录。,10.1.2 文件结构与操作3,3、文件基本操作（1）文件检索2按操作的处理方式，可分为实时与批量处理两种不同的方式:实时处理：响应时间要求严格，要求在接受询问后几秒种内完成检索和更新。批量处理：响应时间要求宽松一些，不同的文件系统有不同的要求。例如一个银行的账户系统，需要满足实时检索要求，也可进行批量更新，即可以将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进行批量处理。,10.1.2 文件结构与操作3,3、文件基本操作2（2）文件更新 数据库文件的维护操作可以分为文件更新、故障恢复、安全性保护和完整性约束等基本情形。文件更新操

7、作类型：插入记录 在给定文件中插入给定的数据记录。此时是针对整条数据记录的操作。删除记录 在给定文件中删除其中一条或多条记录，此时也是针对整条记录的操作。修改记录 在给定文件中修改其中一条记录的某个或多个数据项，此时是针对记录中部分数据项的操作。,10.1.2 文件结构与操作3,10.2.1 顺序文件存储结构顺序文件在存储介质中可以有两种不同的存储结构：连续结构和链式结构。连续结构是指逻辑上相邻的记录其存储位置是相邻的;连续顺序文件链式结构是指物理记录之间的次序由指针链来表示。链接顺序文件,10.2 顺序文件,10.2.2 基于磁带/磁盘的顺序存储1、基于顺序存储器的顺序文件存储在顺序存储器（

8、如磁带）上的文件，只能是顺序文件，这种文件只能进行“顺序存取”和“成批处理”。磁带是一种典型的顺序存储设备。磁带适合于存放文件数据量大、文件中的记录平时变化少、只作批量修改的情况。存储在磁带上的顺序文件只能采用顺序查找法，即顺序扫描文件，按记录的主关键字逐个查找。优点：连续存取时速度快，例如，如果文件中的第i个记录刚被存取过，而下一个要存取的记录就是第i+1个记录，则此次存取将会很快完成。批处理效率高，节省存储空间。缺点：实时性差，特别是更新操作要复制整个文件，所以一般不做随机处理，如删除记录时只做标记处理。,10.2 顺序文件2,10.2.2 基于磁带/磁盘的顺序存储22、基于直接存储器的顺

9、序文件顺序文件也可以存放在直接存取设备上，磁盘就是一个直接存取的存储设备。存放于磁盘上的文件，既可以是顺序文件，也可以是索引结构或其它结构类型的文件。对存储在这类设备上的顺序文件不仅可以进行顺序存取，还可进行分块查找、二分查找等查找方法。对磁盘等直接存取设备，还可以对顺序文件进行插值查找和跳步查找。,10.2 顺序文件2,10.3.1 索引概念及操作索引结构是当文件信息存放在若干不连续物理块中时，系统为该文件建立一个专用数据结构即索引表，需要存储的文件（主文件）和索引表构成的二元组就是索引文件。作为文件信息所在逻辑块号和与相应物理块号之间的对照表，索引表中每一个记录称作索引项。索引项由主关键字

10、（或逻辑记录号）和该关键字所属文件记录的物理块号组成。索引表的基本特征是其中索引项必须按关键字（或逻辑记录号）有序排列而无论主文件是否按关键字有序。如果主文件本身按照主关键字有序，就称相应索引文件为索引顺序文件；如果主文件不是按照关键字有序，则称相应索引文件为索引非顺序文件。,10.3 索引文件,10.3.1 索引概念及操作2索引顺序文件通常有ISAM（Indexed Sequential Access Method）文件和VSAM（Virtual Storage Access Method）文件两种类型。索引非顺序文件通常有B-树和B+树等方式。,10.3 索引文件,10.3.1 索引概念及

11、操作3索引文件操作主要是查找和修改两种情形。索引文件查找 一般分为直接存取和按关键字存取，检索可以分成两步进行：首先在索引表容量合适的情况下，将索引表读入内存；然后根据关键字或逻辑记录号通过二分查找方法在索引表中查找记录是否存在。此时在查找记录成功情况下至少需要访问外存两次。索引文件修改 插入记录时，记录插入在主文件的末尾，同时在索引表中合适的位置插入索引项，而删除记录时，在索引表中删除相应的索引项。由于索引表具有顺序存储结构，插入和删除后应当保持新的索引表的顺序结构，因此可能需要移动大量的索引记录。更新记录时，将更新后的记录插入在主文件的末尾，同时修改相应的索引项。,10.3 索引文件,IS

12、AM(Indexed Sequential Access Method)即“索引顺序存取方法”是一种专为磁盘存取文件设计的文件组织方式，采用静态索引结构。1、ISAM 文件结构ISAM对磁盘上的数据文件建立盘组、柱面和磁道三级索引。各级索引结构如下：,10.3.2 ISAM文件,ISAM文件结构图：,2、ISAM 文件检索从主索引出发，找到相应的柱面索引；从柱面索引找到记录所在柱面的磁道索引；从磁道索引找到记录所在磁道的起始地址，由此出发在该磁道上进行顺序查找，直到找到为止。若找遍该磁道均不存在此记录，则表明该文件中无此记录；若被查找的记录在溢出区，则可以从磁道索引项的溢出索引项中得到溢出链表

13、的头指针，然后对该表进行顺序查找。,10.3.2 ISAM文件2,3、ISAM 文件的插入和删除插入新纪录时，首先找到它应插入的磁道，若该磁道不满，则将新纪录插入该磁道的适当位置上即可；若该磁道已满，则新纪录或插在该磁道上，或直接插入到该磁道的溢出链表上。插入后，可能要修改磁道索引中的基本索引项和溢出索引项。删除记录时，只要找到待删除的记录，在其存储位置上作删除标记即可，而不需要移动记录或改变指针。在经过多次的增删后，文件的结构可能变得很不合理。因此，通常需要周期性地整理ISAM文件，把记录读入内存重新排列，复制成一个新的ISAM文件，填满基本区而空出溢出区。,10.3.2 ISAM文件3,V

14、SAM（Virtual Storage Access Method）即“虚拟存储存取方法”也是一种索引顺序文件的组织方式，采用B+树作为动态索引结构。1、VSAM 文件结构VSAM文件的结构由三部分组成：索引集、顺序集和数据集,10.3.3 VSAM文件,VSAM文件结构示意图：,2、VSAM 文件的插入和删除VSAM文件中没有溢出区，解决插入的方法是在初建文件时留出空间：一是每个控制区间内不填满记录，在最后一个记录和控制信息之间留有空隙；二是在每个控制区域中有一些完全空的控制区间，并在顺序集的索引中指明这些空区间。当插入新纪录时，大多数的新纪录能插入到相应的控制区间内，但要注意保持区间记录的

15、关键字从小至大有序。在VSAM文件中删除记录时，需将同一控制区间中比删除记录关键字大的记录向前移动，把空间留给以后插入的新纪录。若整个控制区间变空，则将其回收用作空闲区间，且需删除顺序集中相应的索引项。,10.3.3 VSAM文件2,3、ISAM和VSAM比较ISAM是一种专为磁盘存取设计的文件组织形式，采用静态索引结构，对磁盘上的数据文件建立盘组、柱面、磁道三级索引。ISAM文件中的记录按关键字顺序存放。经过多次插入和删除记录后，文件结构变得不合理，需定时整理ISAM文件。和ISAM文件相比，给基于B+树的VSAM文件有如下优点：能保持较高的查找效率，查找一个后插入记录和查找一个原有记录具有

16、相同的速度；动态地分配和释放存储空间，可以保持平均75%的存储利用率；永远不必对文件进行再组织。因而基于B+树的VSAM文件，通常作为大型索引顺序文件的标准组织。VSAM文件采用B+树动态索引结构，文件只有控制区间和控制区域等逻辑存储单位，与外存储器中的柱面，磁道等具有存储单位没有必然联系。VSAM文件结构包括索引集、顺序集和数据集三部分，记录存放于数据集中，顺序集和索引集构成B+树，作为文件的索引部分。,10.3.3 VSAM文件3,10.4.1 B-树1、B-树基本概念一棵m阶（m3）B-树或者为空树，或者是满足下述条件的m叉树：树中每个结点至多有m棵子树；若根结点不是叶子结点，则至少有两

17、棵子树；所有非叶结点都包含信息：（n，p0，k1，p1，k2，p2，kn，pn），其中：ki（1in）为关键码，且kiki+1（1in）；pj（0jn）为指向子树根结点的指针，且pj（0jn）所指子树中所有结点的关键码均小于kj+1，pn所指子树中所有结点的关键码均大于kn；n（m/2-1nm-1）为关键码个数（n+1为子树个数）。根结点外所有非叶结点至少有m/2棵子树，即每个内部结点至少有m/2-1个关键码；所有叶结点都位于树的同一层次。叶结点本身都不带有数据信息，可以看作外部结点或查找失败的结点。,10.4 动态索引B-树,1、B-树基本概念2一棵3阶B-树实例：,1、B-树基本概念3B-

18、树存储结构中结点类型定义：,00#define MAXM 1001 typedef int KeyType;03 tepedef struct node04 05 int keynum;06 KeyType keyMAXM;07 struct node*patent;08 struct node*ptrMAXM;09 BTNode;10 int m;11 int Max;12 int Min;,2、B-树查找在一棵B-树上进行顺序查找关键码k的步骤如下：将k与根结点中ki进行比较：若k=ki，查找成功。若kki，沿指针ptr0所指子树继续进行查找。若kikki+1，沿指针ptri所示子树继续查

19、找。若k kn，沿指针ptrn所指子树继续查找。,10.4.1 B-树2,2、B-树查找2算法10-1 B-树查找算法00 Result SearchBTree(BTree*T,KeyType K)01 02 BTree*p,*q;03 int n,i;04p=T;05 q=NULL;06 i=0;07while(p)0809 n=p-keynum;10 i=Search(p,K);/*在p-key0.keynum-1中查找 i*/11 p-keyikeyi+1,10.4.1 B-树2,2、B-树查找2算法10-1 B-树查找算法12 if(i0/*查找不成功*/21,10.4.1 B-树2,

20、3、B-树插入与生成（1）B-树插入step 1.位置查找 在B-树中查找k，若找到则直接返回（假设不处理相同关键码插入）；否则查找操作失败于某叶结点,将k插入到p所指叶结点第pos个位置上。step 2.非满插入 若该叶结点原来是非满（结点中原有关键码总数小于m-1），插入k不会破坏B-树平衡性质，插入k后即完成了插入操作。step 3.满则分裂 若p所指示叶结点为满，插入k后keynum=m，破坏B-树平衡性质，须进行调整以维持B-树性质不变。step 4.分裂传递 将km/2插入父结点后，父结点亦可能原本为满，即添加后父结点中关键码个数也破坏了的平衡性质，则需要按照“step 3”方法进

21、行在分裂，再将新的中间位置关键码和新结点向上添加，这个过程可能传递到根结点为止。,10.4.1 B-树3,3、B-树插入与生成2（2）B-树生成设有关键码为1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15，创建一棵5阶B-树关键码插入过程如下：,插入1,2,6,7,插入11,插入4,8,13,插入10,10.4.1 B-树3,设有关键码为1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15，创建一棵5阶B-树关键码插入过程如下：,插入5,17,9,16,插入20,插入3,12,14，18,19,

22、B-树生成例子（续）：,设有关键码为1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15，创建一棵5阶B-树关键码插入过程如下：,插入15,B-树生成例子（续）：,4、B-树删除B-树中删除关键码k的基本步骤如下：Step 1.结点查找Step 2.非叶结点关键码删除Step 3.叶结点关键码删除 此时可以分为下述三种情形：k所在叶子上面一层结点中的关键码数目不小于m/2。k所在叶子上面一层结点中的关键码数目等于m/2-1，而与该结点相邻的右兄弟结点（或左兄弟结点）中的关键码数目大于m/2-1。k所在叶子上面一层结点中的关键码数和其相邻的兄弟结点

23、中的关键码数目均等于m/2-1。,10.4.1 B-树4,删除6,16,B-树删除例子：,删除15,B-树删除例子（续）：,删除4,B-树删除例子（续）：,1、B+树概念满足如下条件的树型结构称为一棵m阶的B+树：树中每个结点至多具有m棵子树；非根结点的每个分枝至少具有m/2棵子树；非叶结点的根结点至少具有两棵子树；具有n棵子树的结点具有n个关键码。每个非叶结点中的关键码 ki 即为其相应指针所指子树中关键码的最大值；所有叶结点都位于树的同一层面，每个叶结点含有 n 个关键码和 n 个指向记录的指针；每个叶结点中关键码个数n满足 m/2nm；所有叶子结点彼此相链接构成一个有序链表，其头指针指向

24、含最小关键码的结点。,10.4.2 B+树,一棵4阶B+树实例：,2、B+树查找B+树一般都设有两个头指针，一个指向根结点，另一个指向关键码最小的叶结点，B+树所有叶结点构成一个线性链表。这样的数据结构既可实现基于最小关键码的顺序查找，也可实现基于根结点进行缩小范围的随机查找。在缩小范围的查找时，无论成功与否都须查找到叶结点方可结束；若在结点内查找时，给定值kki，则应继续在 ai 所指子树中进行查找。B+树中每次查找都需要完成一条由根结点到某个叶结点的路径。在实际应用中，B+树叶结点通常不是只对应一个记录（稠密索引），而是对应一个磁盘块（稀疏索引）。,10.4.2 B+树2,3、B+树插入和

25、删除B+树中关键码插入都在叶结点层进行。当结点中原关键码个数等于m时，同样需要进行相应分割。同时还需要使得它们的父结点中包含这两个结点的最大关键码和指向它们的指针。当其结点关键码个数因此而大于m时，需要继续分裂，依次类推。B+树中关键码删除都在叶结点层进行。当删除关键码破坏了平衡条件时，则需与相应兄弟结点进行合并。,10.4.2 B+树3,散列文件也可称哈希（hash）文件或者直接存取文件，其特点是使用散列存储方式组织文件。散列文件根据文件记录关键字特征，设计相应散列函数和冲突处理的技术方法，从而完成将记录散列存储到外存储器。散列文件不宜使用磁带或光盘存储而比较适宜于磁盘存储；另外，散列文件这

26、种结构更适合于定长记录文件和按主键随机查找的访问方式。散列文件来说，磁盘上一个文件中所有记录一般“分组”存放。具体而言，就是文件中若干个记录组成一个称为“桶”的存储单位，由若干个“桶”来存放一个散列文件。散列文件也可采用散列表中处理冲突的各种方法，但散列文件处理冲突的基本方法是链地址法。（基桶、溢出桶）,10.5 散列文件,例：假定某个文件有20个记录，其中关键字集合为12,23,17,26,21,35,28,18,27,22,7，9,46,19,6,16,30,19,10,64。桶的容量m=3，桶数b=9，用除留余数法作散列函数H（key）=key%9，其对应的散列文件如下所示：,10.5

27、散列文件2,查找记录 首先根据待查记录的关键字值求得散列地址（即基桶地址），将基桶的记录读入内存进行顺序查找，若找到某记录的关键字等于待查记录的关键字，则查找成功；若基桶内无带查记录且基桶内指针为空，则文件中没有待查记录，查找失败，若基桶内无待查记录且基桶内指针不空,则将溢出桶中的记录的如内存进行顺序查找，若在某个溢出桶中查找待查记录，则查找成功，若所有溢出桶链内均未查找到待查记录，则查找失败。插入记录 首先查找该记录是否存在，是则出错，否则插入在最后一个桶尚未填满的页块中。若桶中所有页块都已被填满，则向系统申请一个新溢出桶，链入桶链表之链尾，然后将新记录存入其中。删除记录 首先查找待删记录是

28、否存在，不存在则出错，否则就删除，腾出空位给之后插入的记录用。,10.5 散列文件3,当文件的一个记录中含多个关键字时，对数据文件的检索往往不只是根据主关键字进行查找，经常需要对记录的次关键字（指记录的某些重要属性）或多关键字的组合进行检索时，文件的组织方式应该同时考虑如何便于进行次关键字或多关键字的组合查询。多重表文件倒排文件,10.6 多关键字文件,多重表文件是对文件中的主关键字建立主索引，而对每个需要查询的次关键字均建立一个索引，同时将具有相同次关键字的记录链接成一个链表，并将此链表的头指针，链表长度及次关键字作为索引表的一个索引项。通常多重表文件的主文件是顺序文件。,10.6.1 多重

29、表文件,例子：,10.6.1 多重表文件2,图1 多重表数据文件,图2 多重表文件索引,倒排文件对次关键字的记录之间不需设指针进行链接，而是为每个需要进行检索的次关键字建立一个倒排表，列出具有该次关键字记录的所有物理记录号。倒排表和主文件一起就构成了倒排文件。倒排文件示例：,10.6.2 倒排文件,倒排文件中，先给定次关键字，然后查找含有该次关键字的各个记录，查找次序正好与一般文件的查找次序相反，因此称之为“倒排”。倒排表作索引便于记录的查询，尤其是在处理复杂的多关键字查询时，只需在倒排表中先完成查询的交、并等逻辑运算，得到结果后再对符合条件的记录进行存取，把对记录的查询转换为物理集合的运算，从而提高查找速度。在插入和删除记录时，可能要删除或者修改移动倒排表中的记录号。优点：对于主文件的存储具有相对的独立性，对于多关键字组合查询，可以先对由每个次关键字得到的多个主关键字集合进行集合运算，最后只要对得到的满足多关键字检索要求的主关键字进行存取即可，具有速度快且灵活的优势。缺点：维护困难。,10.6.2 倒排文件2,操作系统文件与数据库文件：,本章小结,数据库文件：,本章小结2,