6文件组织与文件格式

第六章文件组织与文件格式2019/9/9信息存储与检索2第六章文件组织与文件格式•6.1外存数据的组织•6.2常用文件的组织•6.3超文本与流媒体•6.4图形文件与其它文件格式2019/9/9信息存储与检索36.1外存数据的组织6.1.1两类外存数据1、文件•文件组织中的数据的结构组织方式一般可分为两类：流式文件和记录文件。•流式文件是数据的序列集合，可以看成是数据的字节流。•记录文件是逻辑记录的集合，记录是按存储数据在逻辑上的独立含义来划分的一个数据结构单位。•文件组织方式的基本特征是，用逻辑记录的定义来实现信息实体组成属性的数据联系。而文件和文件之间可能存在的联系只能依靠用户程序对这些文件的处理逻辑来体现。2019/9/9信息存储与检索46.1、外存数据的组织–数据库文件•数据库中的文件是性质相同的记录的集合。数据库中所研究的文件是带有结构的记录集合，每个记录可由若干个数据项构成。•数据库中的记录是文件中存取的基本单位，数据项是文件可使用的最小单位。数据项有时也称为字段或者称为属性，其值能唯一标志一个记录的数据项或数据项的组合者称为主关键字项。2019/9/9信息存储与检索5•【例】下表是一个简单的职工文件。每个职工情况是一个记录，它由7个数据项组成。其中职工号可作为主关键字项，它能惟一标识一个记录，即它的值对任意两个记录都是不同的。姓名、性别等数据只能作为次关键字项，因为它们的值对不同的记录可以是相同的。2019/9/9信息存储与检索66.1外存数据的组织6.1.2记录式文件的基本属性1、组织形式•记录式文件是记录值的集合，记录值在文件物理存储空间上的存放模式称为文件组织形式。•一方面组织形式涉及文件的物理结构；另一方面在用户的语言界面上文件的组织形式又作为一种逻辑属性来定义，用户按对外存数据的存取要求来选择文件的组织形式。2019/9/9信息存储与检索7常用的文件组织形式•顺序文件•索引文件•相对文件•散列文件2019/9/9信息存储与检索86.1.2记录式文件的基本属性2、存取方式–顺序存取方式：沿某种含义的序列，从序列的指定位置开始依次地存取每一个后继记录。–随机存取方式：指定记录值的某种标志，按标志存取特定的一个记录。3、驻留介质–文件的组织形式和驻留介质有制约关系，如磁带文件、打印机文件、卡片文件只能是顺序文件。磁盘文件可以使用各种组织形式。2019/9/9信息存储与检索94、处理方式文件上检索和更新操作，都可有实时和批量两种不同的处理方式。①实时处理：响应时间要求严格，要求在接受询问后几秒种内完成检索和更新。②批量处理：响应时间要求宽松一些，不同的文件系统有不同的要求。【例】一个民航订票系统，其检索和更新都应当实时处理；而银行的账户系统需要实时检索，但可进行批量更新，即可以将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进行批量处理。6.1.2记录式文件的基本属性2019/9/9信息存储与检索106.2常用文件的组织6.2.1顺序文件1、定义及使用特点顺序文件是指按记录进入文件的先后顺序存放，其逻辑顺序和物理顺序一致的文件。–“逻辑顺序”是指写入的顺序依次为第一个，第二个等；–“物理顺序”是指实际存放在外存中的位置依次排在第一个记录，第二个记录等等。–只有顺序文件有这个二者一致的特点：先进先出，后进后出，且先进者排在前。–顺序文件的记录没有标志，可以不等长，从顺序文件中读记录，必须从第一个记录读起，不能从中间记录读起。2019/9/9信息存储与检索116.2.1顺序文件•顺序文件分类–顺序有序文件•记录按其主关键字有序的顺序文件为顺序有序文件。•在数据库中称为顺排文档，它按某一关键字的顺序存入了数据库的全部记录，故又称为主文档。–顺序无序文件•记录未按其主关键字有序排列的顺序文件为顺序无序文件。2019/9/9信息存储与检索122、顺序文件的处理•批处理2019/9/9信息存储与检索133、顺排文档检索（1）顺序查找法–顺序查找法即顺序扫描文件，按记录的主关键字逐个查找。要检索第i个记录，必须检索前i-1个记录。–注意：•①这种查找法对于少量的检索是不经济的，但适合于批量检索。•②顺序存取存储器上的文件只能用顺序查找法存取。2019/9/9信息存储与检索14顺排文档检索（2）分块查找法设文件按主关键字的递增顺序，每100个记录为一块，各块的最后一个记录的主关键字为Kl00，K200，…，K100i，…。查找时，将所要查找的记录的主关键字K，依次和各块的最后一个记录的主关键字比较，当K大于K100(i-1)且小于或等于K100i时，则在第i块内进行扫描。分块查找法在查找时不必扫描整个文件中的记录。2019/9/9信息存储与检索15（3）二分查找法–二分查找又称折半查找，它是一种效率较高的查找方法。–二分查找要求：1、必须采用顺序存储结构2、必须按关键字大小有序排列。–优缺点：折半查找法的优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。顺排文档检索2019/9/9信息存储与检索16二分查找法•算法思想–首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。–重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。2019/9/9信息存储与检索172019/9/9信息存储与检索186.2.2索引文件与倒排文件1、索引文件及其使用–文件的索引是指记录的关键字与相应记录的存储地址的对照表，带索引的文件称为被索引文件。–索引文件由主文件和索引表构成。主文件是文件本身；索引表是文件本身外建立的一张表，它指明逻辑记录和物理记录之间的一一对应关系。–索引表由若干索引项组成。一般索引项由主关键字和该关键字所在记录的物理地址组成。索引表必须按主关键字有序；而主文件本身则是可以按主关键字有序或无序组织。2019/9/9信息存储与检索19索引文件（1）索引顺序文件和索引非顺序文件–主文件按主关键字有序的文件称索引顺序文件。在索引顺序文件中，可以把记录分成多个组（块），可对一组记录建立一个索引项。这种索引表称为稀疏索引。稀疏索引项的指针指向的是这一组记录在磁盘中的起始位置。–主文件按主关键字无序的文件称索引非顺序文件。在索引非顺序文件中，必须为每个记录建立一个索引项，这样建立的索引表称为稠密索引。2019/9/9信息存储与检索20•注意：–①通常将索引非顺序文件简称为索引文件。–②索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。–③索引顺序文件的主文件是有序的，适合于随机存取、顺序存取。–④索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件组织。–⑤最常用的索引顺序文件：ISAM文件和VSAM文件。ISAM索引顺序存取方法，VSAM虚拟存储存取方法。索引文件2019/9/9信息存储与检索21（2）索引文件的建立–建立索引文件的过程是：•按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的。•待全部记录输入完毕后对索引表进行排序，排序后的索引表和主文件一起就形成了索引文件。2019/9/9信息存储与检索22（3）索引文件的操作•检索操作–检索分两步进行：•①将外存上含有索引区的页块送人内存，查找所需记录的物理地址。•②将含有该记录的页块送人内存–注意：•①索引表不大时，索引表可一次读入内存，在索引文件中检索只需两次访问外存：一次读索引，一次读记录。•②由于索引表有序，对索引表的查找可用顺序查找或二分查找等方法。2019/9/9信息存储与检索23索引文件的操作•更新操作–插入：将插入记录置于数据区的末尾，并在索引表中插入索引项；–删除：删去相应的索引项；–注意：修改主关键字时，要同时修改索引表。2019/9/9信息存储与检索24（4）利用查找表建立多级索引①查找表–对索引表再建立的索引，称为查找表。查找表的建立可以为占据多个页块的索引表的查阅减少外存访问次数。–表3的索引表占用了三个页块的外存，每个页块能容纳三个索引项，则可为之建立一个查找表，在查找表中，列出索引表的每一页块最后一个索引项中的关键字(该块中最大的关键字)及该块的地址，如右图所示。检索记录时，先查找查找表，再查索引表，然后读取记录，三次访问外存即可。2019/9/9信息存储与检索25利用查找表建立多级索引②多级索引–当查找表中项目仍很多，可建立更高一级的索引。通常最高可达四级索引：数据文件一索引表一查找表一第二查找表一第三查找表多级索引是一种静态索引。多级索引的各级索引均为顺序表，结构简单，修改很不方便，每次修改都要重组索引。2019/9/9信息存储与检索26（5）动态索引•动态索引结构是指文件创建、初始装入记录时所生成的索引结构，在系统运行过程中插入或删除记录时，索引结构本身也可能发生改变，改变索引结构的目的是为保持较好的性能，例如较高的检索效率。B树和B+树都是经典的动态索引。2019/9/9信息存储与检索272、倒排索引文档•通常把在次关键字上面建立的索引称为次索引或倒排索引。–在文献检索中，倒排文档是将主文件中的可检字段抽出，按某种顺序重新排列起来所形成的一种文档。不同的字段组织成不同的倒排文档。倒排文档可以按主题词的字顺排，也可以按分类号的大小排。–按表达文献内容特征的主题词排列的文档称为基本索引文档；按表达文献外部特征排列的文档称为辅助索引文档。2019/9/9信息存储与检索28•倒排文档示例关键字相关文献数物理地址计算机3500，501，550用户3501，502，540系统软件2500，533系统硬件2501，509应用软件2500，5022019/9/9信息存储与检索29（1）倒排文档的组织方式和特点–主索引和倒排索引的构造有差异。因为主关键字的取值是唯一的，而次关键字的取值可以不唯一。对应一个次关键字值的记录往往有许多个。–在次关键字索引中，具有相同次关键字的记录之间不进行链接，而是列出具有该次关键字记录的物理地址。倒排文件中的次关键字索引称做倒排表。倒排表和主文件一起就构成了倒排文件。–多重表文件是将索引方法和链接方法相结合的一种组织方式。对每个需要查询的次关键字建立一个索引，同时将具有相同次关键字的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字，作为索引表的一个索引项。通常多重表文件的主文件是一个顺序文件。2019/9/9信息存储与检索30多重表文件2019/9/9信息存储与检索31•建立多重表索引2019/9/9信息存储与检索32•建立倒排文件索引2019/9/9信息存储与检索33（2）倒排文件的查询–倒排表的主要优点是：在处理复杂的多关键字查询时，可在倒排表中先完成查询的交、并等逻辑运算，得到结果后再对记录进行存取。这样不必对每个记录随机存取，把对记录的查询转换为地址集合的运算，从而提高查找速度。–例：要找出所有工资级别小于13的硬件人员，则只需将工资级别倒排表中的次关键字为10，11和12的物理地址集合先做“并”运算，然后与职务倒排表中的硬件人员的物理地址集合做“交”运算：{108}∪{102，106}∪{101})∩{101，102，107，110}={101，102}–即符合条件的记录，其物理地址是101和102。2019/9/9信息存储与检索34作业•某次活动的学生报名登记表文件，部分信息如下：物理地址学号姓名性别年龄专业00108090325张三男18计算机00208070114李四女17外语00308090317王五男19计算机00408060330赵六女17体育00508040203田七男18信息给出性别、年龄、专业的倒排索引表，并检索年龄小于19岁的男生，写出检索过程。2019/9/9信息存储与检索35•倒排文件与一般文件组织的区别在一般的文件组织中