文件组织与文件格式

第六章文件组织与文件格式2023/1/191第六章文件组织与文件格式6.1外存数据的组织6.2常用文件的组织6.3超文本与流媒体6.4图形文件与其它文件格式2023/1/1926.1外存数据的组织6.1.1两类外存数据1、文件文件组织中的数据的结构组织方式一般可分为两类：流式文件和记录文件。流式文件是数据的序列集合，可以看成是数据的字节流。记录文件是逻辑记录的集合，记录是按存储数据在逻辑上的独立含义来划分的一个数据结构单位。文件组织方式的基本特征是，用逻辑记录的定义来实现信息实体组成属性的数据联系。而文件和文件之间可能存在的联系只能依靠用户程序对这些文件的处理逻辑来体现。2023/1/1936.1、外存数据的组织数据库文件数据库中的文件是性质相同的记录的集合。数据库中所研究的文件是带有结构的记录集合，每个记录可由若干个数据项构成。数据库中的记录是文件中存取的基本单位，数据项是文件可使用的最小单位。数据项有时也称为字段或者称为属性，其值能唯一标志一个记录的数据项或数据项的组合者称为主关键字项。2023/1/194【例】下表是一个简单的职工文件。每个职工情况是一个记录，它由7个数据项组成。其中"职工号"可作为主关键字项，它能惟一标识一个记录，即它的值对任意两个记录都是不同的。姓名、性别等数据只能作为次关键字项，因为它们的值对不同的记录可以是相同的。

2023/1/1956.1外存数据的组织6.1.2记录式文件的基本属性1、组织形式记录式文件是记录值的集合，记录值在文件物理存储空间上的存放模式称为文件组织形式。一方面组织形式涉及文件的物理结构；另一方面在用户的语言界面上文件的组织形式又作为一种逻辑属性来定义，用户按对外存数据的存取要求来选择文件的组织形式。2023/1/196常用的文件组织形式顺序文件索引文件相对文件散列文件2023/1/1976.1.2记录式文件的基本属性2、存取方式顺序存取方式：沿某种含义的序列，从序列的指定位置开始依次地存取每一个后继记录。随机存取方式：指定记录值的某种标志，按标志存取特定的一个记录。3、驻留介质文件的组织形式和驻留介质有制约关系，如磁带文件、打印机文件、卡片文件只能是顺序文件。磁盘文件可以使用各种组织形式。2023/1/1984、处理方式

文件上检索和更新操作，都可有实时和批量两种不同的处理方式。

①实时处理：响应时间要求严格，要求在接受询问后几秒种内完成检索和更新。

②批量处理：响应时间要求宽松一些，不同的文件系统有不同的要求。

【例】一个民航订票系统，其检索和更新都应当实时处理；而银行的账户系统需要实时检索，但可进行批量更新，即可以将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进行批量处理。

6.1.2记录式文件的基本属性2023/1/1996.2常用文件的组织6.2.1顺序文件1、定义及使用特点顺序文件是指按记录进入文件的先后顺序存放，其逻辑顺序和物理顺序一致的文件。“逻辑顺序”是指写入的顺序依次为第一个，第二个等；“物理顺序”是指实际存放在外存中的位置依次排在第一个记录，第二个记录等等。只有顺序文件有这个二者一致的特点：先进先出，后进后出，且先进者排在前。顺序文件的记录没有标志，可以不等长，从顺序文件中读记录，必须从第一个记录读起，不能从中间记录读起。2023/1/1910顺顺序文件顺序文件分类类顺序有序文件件记录按其主关关键字有序的的顺序文件为为顺序有序文文件。在数据库中称称为顺排文档档，它按某一一关键字的顺顺序存入了数数据库的全部部记录，故又又称为主文档档。顺序无序文件件记录未按其主主关键字有序序排列的顺序序文件为顺序序无序文件。。2023/1/1112、顺顺序文文件的的处理理批处理理2023/1/1123、顺排排文档档检索索（1）顺序序查找找法顺序查查找法法即顺顺序扫扫描文文件，，按记记录的的主关关键字字逐个个查找找。要要检索索第i个记录录，必必须检检索前前i-1个记录录。注意：：①这这种查查找法法对于于少量量的检检索是是不经经济的的，但但适合合于批批量检检索。。②顺顺序存存取存存储器器上的的文件件只能能用顺顺序查查找法法存取取。2023/1/113顺排文档档检索（2）分块块查找法法设文件按按主关键键字的递递增顺序序，每100个记录为为一块，，各块的的最后一一个记录录的主关关键字为为Kl00，K200，…，K100i，…。查查找时，，将所要要查找的的记录的的主关键键字K，依次和和各块的的最后一一个记录录的主关关键字比比较，当当K大于K100(i-1)且小于或或等于K100i时，则在在第i块内进行行扫描。。分分块查查找法在在查找时时不必扫扫描整个个文件中中的记录录。2023/1/114（3）二分查找找法二分查找又称称折半查找，，它是一种效效率较高的查查找方法。二分查找要求求：1、必须采用顺顺序存储结构构2、必须按关键键字大小有序序排列。优缺点：折半半查找法的优优点是比较次次数少，查找找速度快，平平均性能好；；其缺点是要要求待查表为为有序表，且且插入删除困困难。因此，，折半查找方方法适用于不不经常变动而而查找频繁的的有序列表。。顺排文档检索索2023/1/115二分查找法算法思想首先，将表中中间位置记录录的关键字与与查找关键字字比较，如果果两者相等，，则查找成功功；否则利用用中间位置记记录将表分成成前、后两个个子表，如果果中间位置记记录的关键字字大于查找关关键字，则进进一步查找前前一子表，否否则进一步查查找后一子表表。重复以上过程程，直到找到到满足条件的的记录，使查查找成功，或或直到子表不不存在为止，，此时查找不不成功。2023/1/1162023/1/117索索引引文件件与倒倒排文文件1、索引引文件件及其其使用用文件的的索引引是指指记录的的关键键字与与相应应记录录的存存储地地址的的对照照表，，带索引引的文文件称称为被被索引引文件件。索引文文件由由主文文件和和索引引表构构成。。主文件件是文文件本本身；；索引引表是是文件件本身身外建建立的的一张张表，，它指指明逻逻辑记记录和和物理理记录录之间间的一一一对对应关关系。。索引表表由若若干索索引项项组成成。一般索索引项项由主主关键键字和和该关关键字字所在在记录录的物物理地地址组组成。。索引表表必须须按主主关键键字有有序；；而主主文件件本身身则是是可以以按主主关键键字有有序或或无序序组织织。2023/1/118索引文文件（1）索引引顺序序文件件和索索引非非顺序序文件件主文件件按主主关键键字有有序的的文件件称索索引顺顺序文文件。。在索索引顺顺序文文件中中，可可以把把记录录分成成多个个组（（块）），可可对一组记录建立立一个索索引项。。这种索索引表称称为稀疏疏索引。。稀疏索索引项的的指针指指向的是是这一组组记录在在磁盘中中的起始始位置。。主文件按按主关键键字无序序的文件件称索引引非顺序序文件。。在索引引非顺序序文件中中，必须须为每个记录建立立一个索索引项，，这样建建立的索索引表称称为稠密密索引。。2023/1/119注意：①通常常将索引引非顺序序文件简简称为索索引文件件。②索引引非顺序序文件主主文件无无序，顺顺序存取取将会频频繁地引引起磁头头移动，，适合于于随机存存取，不不适合于于顺序存存取。③索引引顺序文文件的主主文件是是有序的的，适合合于随机机存取、、顺序存存取。④索引引顺序文文件的索索引是稀稀疏索引引。索引引占用空空间较少少，是最最常用的的一种文文件组织织。⑤最常常用的索索引顺序序文件：：ISAM文件和VSAM文件。ISAM索引顺序序存取方方法，VSAM虚拟存储储存取方方法。索引文件件2023/1/120（2）索引引文件件的建建立建立索索引文文件的的过程程是：：按输入入记录录的先先后次次序建建立数数据区区和索索引表表。其其中索索引表表中关关键字字是无无序的的。待全部部记录录输入入完毕毕后对对索引引表进进行排排序，，排序序后的的索引引表和和主文文件一一起就就形成成了索索引文文件。。2023/1/121（3））索引引文件件的操操作检索操操作检索分分两步步进行行：①将将外存存上含含有索索引区区的页页块送送人内内存，，查找找所需需记录录的物物理地地址。。②将将含有有该记记录的的页块块送人人内存存注意：：①索引引表不不大时时，索索引表表可一一次读读入内内存，，在索索引文文件中中检索索只需需两次次访问问外存存：一一次读读索引引，一一次读读记录录。②由于于索引引表有有序，，对索索引表表的查查找可可用顺顺序查查找或或二分分查找找等方方法。。2023/1/122索引文文件的的操作作更新操操作插入：：将将插入入记录录置于于数据据区的的末尾尾，并并在索索引表表中插插入索索引项项；删除：删删去相应应的索引项项；注意：修修改主关关键字时，，要同时修修改索引表表。2023/1/123（4）利用查找找表建立多多级索引①查找表对索引表再再建立的索索引，称为为查找表。。查找表的的建立可以以为占据多多个页块的的索引表的的查阅减少少外存访问问次数。表3的索引表占占用了三个个页块的外外存，每每个页块能能容纳三个个索引项，，则则可为之建建立一个查查找表，在在查找找表中，列列出索引表表的每每一页块最最后一个索索引项中的的关关键字(该块中最大大的关键字字)及该块的地地址，如右右图所示。。检检索记录时时，先查找找查找表，，再再查索索引表，然然后读取记记录，三次次访问外存存即可。2023/1/124利用查找表建建立多级索引引②多级索引当查找表中项项目仍很多，，可建立更高高一级的索引引。通常最高高可达四级索索引：数据文件一索索引表一查找找表一第二查查找表一第三三查找表多级索引是一一种静态索引引。多级索引引的各级索引引均为顺序表表，结构简单单，修改很不不方便，每次次修改都要重重组索引。2023/1/125（5））动态态索引引动态索索引结结构是是指文文件创创建、、初始始装入入记录录时所所生成成的索索引结结构，，在系系统运运行过过程中中插入入或删删除记记录时时，索索引结结构本本身也也可能能发生生改变变，改改变索索引结结构的的目的的是为为保持持较好好的性性能，，例如如较高高的检检索效效率。。B树和B+树都是是经典典的动动态索索引。。2023/1/1262、倒倒排索索引文文档通常把把在次次关键键字上上面建建立的的索引引称为为次索索引或或倒排排索引引。在文献献检索索中，，倒排文文档是是将主主文件件中的的可检检字段段抽出出，按按某种种顺序序重新新排列列起来来所形形成的的一种种文档档。不同的的字段段组织织成不不同的的倒排排文档档。倒倒排文文档可可以按按主题题词的的字顺顺排，，也可可以按按分类类号的的大小小排。。按表达达文献献内容容特征征的主题词词排列列的文档档称为为基本本索引引文档档；按按表达达文献献外部特特征排排列的文档档称为为辅助助索引引文档档。2023/1/127倒排文文档示示例关键字相关文献数物理地址计算机3500，501，550用户3501，502，540系统软件2500，533系统硬件2501，509应用软件2500，5022023/1/128（1）倒排文文档的组组织方式式和特点点主索引和和倒排索索引的构构造有差差异。因因为主关关键字的的取值是是唯一的的，而次次关键字字的取值值可以不不唯一。。对应一一个次关关键字值值的记录录往往有有许多个个。在次关键键字索引引中，具具有相同同次关键键字的记记录之间间不进行行链接，，而是列列出具有有该次关关键字记记录的物物理地址址。倒排排文件中中的次关关键字索索引称做做倒排表表。倒排排表和主主文件一一起就构构成了倒倒排文件件。多重表文文件是将索引方法法和链接接方法相相结合的一种组组织方式式。对每每个需要要查询的的次关键键字建立立一个索索引，同同时将具具有相同同次关键键字的记记录链接接成一个个链表，，并将此此链表的的头指针针、链表表长度及及次关键键字，作作为索引引表的一一个索引引项。通通常多重重表文件件的主文文件是一一个顺序序文件。。2023/1/129多重表文件2023/1/130建立多多重表表索引引2023/1/131建立倒倒排文文件索索引2023/1/132（2））倒倒排排文文件件的的查查询询倒排排表表的的主主要要优优点点是是：：在在处处理理复复杂杂的的多多关关键键字字查查询询时时，，可可在在倒倒排排表表中中先先完完成成查查询询的的交交、、并并等等逻逻辑辑运运算算，，得得到到结结果果后后再再对对记记录录进进行行存存取取。。这这样样不不必必对对每每个个记记录录随随机机存存取取，，把把对对记记录录的的查查询询转转换换为为地地址址集集合合的的运运算算，，从从而而提提高高查查找找速速度度。。例：：要要找找出出所所有有工工资资级级别别小小于于13的硬硬件件人人员员，，则则只只需需将将工工资资级级别别倒倒排排表表中中的的次关关键键字字为为10，11和12的物物理理地地址址集集合合先先做做“并”运算算，，然后后与职职务务倒倒排排表表中中的的硬硬件件人人员员的的物物理理地地址址集集合合做做“交”运算算：{108}∪{102，106}∪{101})∩{101，102，107，110}={101，102}即符符合合条条件件的的记记录录，，其其物物理理地地址址是是101和102。2023/1/133作业某次活动的学学生报名登记记表文件，部部分信息如下下：物理地址学号姓名性别年龄专业00108090325张三男18计算机00208070114李四女17外语00308090317王五男19计算机00408060330赵六女17体育00508040203田七男18信息给出性别、年年龄、专业的的倒排索引表表，并检索年年龄小于19岁的男生，写写出检索过程程。2023/1/134倒排文件与与一般文件件组织的区区别在一般的文文件组织中中，是先找找记录，然然后再找到到该记录所所含的各次次关键字；；而倒排文文件中，是是先给定次次关键字，，然后查找找含有该次次关键字的的各个记录录，这种文文件的查找找次序正好好与一般文文件的查找找次序相反反，因此称称之为“倒排”。注意：多重重表文件实实际上也是是倒排文件件，只不过过索引的方方法不同。。2023/1/135散散列列文文件件和和相相对对文文件件1、散散列列文文件件散列列文文件件是是利利用用散散列列存存储储方方式式组组织织的的文文件件，，亦亦称称直直接接存存取取文文件件。。即即根根据据文文件件中中关关键键字字的的特特点点，，设设计计一一个个散散列列函函数数和和处处理理冲冲突突的的方方法法，，将将记记录录散散列列到到存存储储设设备备上上。。2023/1/136（1）基桶和溢出出桶在散列文件的的存储单位叫叫桶(Bucket)。桶内的最大大存储记录数数目称桶因子。假如一个桶能能存放m个记录，则当当桶中已有m个记录时，存存放第m+1个记录会发生生“溢出”。需要将第m+1个记录存放到到另一个桶中中，通常称此此桶为“溢出桶”。相对地，称称前m个记录存放的的桶为“基桶”。注意：溢出桶和基桶桶大小相同，，相互之间用用指针相链接接。当在基桶中没没有找到待查查记录时，就就沿着指针到到所指溢出桶桶中进行查找找，因此，希希望同一散列列地址的溢出出桶和基桶，，在磁盘上的的物理位置不不要相距太远远，最好在同同一柱面上。。2023/1/137散列文件的的存放方式式散列文件的的记录由关关键字标志志，建立关键字字到记录存存储地址的的一个映射射函数，存储和访问问记录均按按选定的散散列函数值值寻址。记录由选定定的散列函函数决定应应存放在哪哪个桶。记录存储桶桶号=HASH（记录的关关键字值））2023/1/138散列文件示例例【例】某一文件有16个记录，其关关键字分别为为：23，05，26，01，18，02，27，12，07，09，04，19，06，16，33，24。桶的容量m=3，桶数b=7。用除余法作散散列函数H(key)=key％7。由此得到的散散列文件如下下图所示。2023/1/139（2）散散列列文文件件的的查查找找操操作作在散散列列文文件件中中查查找找的的过过程程：：（1）根根据据给给定定值值求求出出散散列列桶桶地地址址。。（2）将将基基桶桶的的记记录录读读人人内内存存，，进进行行顺顺序序查查找找。。（3）若若找找到到关关键键字字等等于于给给定定值值的的记记录录，，则则检检索索成成功；；否否则则，，读读入入溢溢出出桶桶的的记记录录继继续续进进行行查查找找。。2023/1/140（3）散列列文件件特点点实现时时，桶桶是语语言界界面上上可操操纵的的外存存存储储单位位，可可以是是一个个记录录、一一个磁磁道、、一个个物理理块。。桶号号相应应是相相对的的记录录号、、磁道道号、、块号号等，，最终终可以以转换换为外外存空空间上上的物物理地地址。。构造散散列文文件的的要求求是，，选定定一个个散列列函数数并选选定一一个处处理溢溢出记记录的的算法法。最最常使使用的的散列列函数数是除除留余余，即即：H(key)=key%p以关键键字或或和关关键字字对应应的一一个整整数除除以桶桶数p，以余余数为为桶号号，显显然桶桶号为为0~（p-1）之间间。散列文文件只只支持持随机机访问问方式式，无法按按记录录的存存储先先后次次序或或者是是关键键字的的升降降序来来顺序序访问问记录录。2023/1/141散列文文件特特点散列文文件的的优点点（1）文文件随随机存存放，，记录录不需需进行行排序序。（2）插插入、、删除除方便便。（3）存存取速速度快快；不不需要要索引引区，，节省省存储储空间间。散列文文件的的缺点点（1）不不能进进行顺顺序存存取，，只能能按关关键字字随机机存（2）询询问方方式限限于简简单询询问（3）在在经过过多次次插入入、删删除后后，可可能造造成文文件结结构不不合理理，需需要重重新组组织文文件。。2023/1/1422、相对文件件相对文件要要求记录等等长，文件件空间按逻逻辑记录长长度划分为为一个等长长的位置，，把位置编编号，文件件内的记录录存储位置置就可以用用相对记录录号（RRN）来标志和和定位。指定了RRN，就指定存存储在那个个位置上的的记录。RRN是相对文件件记录的标标志，但是是RRN不是被标志志记录的必必然组成项项。相对文件既既支持对记记录的顺序序访问又支支持对记录录的随机访访问。2023/1/143总结文件的存取取方式和组组织形式顺序文件索引文件散列文件相对文件顺序存取按记录存储的先后次序依次访问后继记录按记录关键字的升序序列依次访问后续记录按相对记录号的升序序列依次访问后续记录随机存取按指定的记录关键字值访问一个记录按指定的记录关键字值访问一个记录按指定的相对记录号访问一个记录2023/1/144作业业1、描描述述顺顺序序文文件件的的检检索索方方法法。。2、简简述述索索引引文文件件的的存存储储方方式式。。3、简简述述倒倒排排文文档档和和多多重重表表文文件件的的区区别别。。4、描描述述散散列列文文件件的的存存储储方方式式。。2023/1/1459、静静夜夜四四无无邻邻，，荒荒居居旧旧业业贫贫。。。。1月月-231月月-23Sunday,January1,202310、雨雨中中黄黄叶叶树树，，灯灯下下白白头头人人。。。。20:48:2020:48:2020:481/1/20238:48:20PM11、以我独沈久久，愧君相见见频。。1月-2320:48:2020:48Jan-2301-Jan-2312、故人人江海海别，，几度度隔山山川。。。20:48:2020:48:2020:48Sunday,January1,202313、乍见见翻疑疑梦，，相悲悲各问问年。。。1月-231月-2320:48:2020:48:20January1,202314、他他乡乡生生白白发发，，旧旧国国见见青青山山。。。。01一一月月20238:48:20下下午午20:48:201月月-2315、比不不了得得就不不比，，得不不到的的就不不要。。。。。一月238:48下下午午1月-2320:48January1,202316、行动动出成成果，，工作作出财财富。。。2023/1/120:48:2020:48:2001January202317、做前，能能够环视四四周；做时时，你只能能或者最好好沿着以脚脚为起点的的射线向前前。。8:48:20下下午8:48下下午20:48:201月-239、没有失败，，只有暂时停停止成功！。。1月-231月-23Sunday,January1,202310、很多事事情努力力了未必必有结果果，但是是不努力力却什么么改变也也没有。。。20:48:2020:48:2020:481/1/20238:48:20PM11、成功就是是日复一日日那一点点点小小努力力的积累。。。1月-2320:48:2020:48Jan-2301-Jan-2312、世间成事，，不求其绝对对圆满，留一一份不足，可可得无限完美美。。20:48:2020:48:2020:48Sunday,January1,202313、不知香积寺寺，数里入云云峰。。1月-231月-2320:48:2020:48:20January1,202314、意