6文件组织与文件格式

第六章文件组织与文件格式第六章文件组织与文件格式6.1外存数据的组织6.2常用文件的组织6.3超文本与流媒体6.4图形文件与其它文件格式2024/1/222信息存储与检索6.1外存数据的组织6.1.1两类外存数据1、文件文件组织中的数据的构造组织方式普通可分为两类：流式文件和记录文件。流式文件是数据的序列集合，可以看成是数据的字节流。记录文件是逻辑记录的集合，记录是按存储数据在逻辑上的独立含义来划分的一个数据构造单位。文件组织方式的根本特征是，用逻辑记录的定义来实现信息实体组成属性的数据联络。而文件和文件之间能够存在的联络只能依托用户程序对这些文件的处置逻辑来表达。2024/1/223信息存储与检索6.1、外存数据的组织数据库文件数据库中的文件是性质一样的记录的集合。数据库中所研讨的文件是带有构造的记录集合，每个记录可由假设干个数据项构成。数据库中的记录是文件中存取的根本单位，数据项是文件可运用的最小单位。数据项有时也称为字段或者称为属性，其值能独一标志一个记录的数据项或数据项的组合者称为主关键字项。2024/1/224信息存储与检索【例】下表是一个简单的职工文件。每个职工情况是一个记录，它由7个数据项组成。其中"职工号"可作为主关键字项，它能独一标识一个记录，即它的值对恣意两个记录都是不同的。姓名、性别等数据只能作为次关键字项，由于它们的值对不同的记录可以是一样的。

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

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

①实时处置：呼应时间要求严厉，要求在接受讯问后几秒种内完成检索和更新。

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

【例】一个民航订票系统，其检索和更新都该当实时处置；而银行的账户系统需求实时检索，但可进展批量更新，即可以将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进展批量处置。6.1.2记录式文件的根本属性2024/1/229信息存储与检索6.2常用文件的组织6.2.1顺序文件1、定义及运用特点顺序文件是指按记录进入文件的先后顺序存放，其逻辑顺序和物理顺序一致的文件。“逻辑顺序〞是指写入的顺序依次为第一个，第二个等；“物理顺序〞是指实践存放在外存中的位置依次排在第一个记录，第二个记录等等。只需顺序文件有这个二者一致的特点：先进先出，后进后出，且先进者排在前。顺序文件的记录没有标志，可以不等长，从顺序文件中读记录，必需从第一个记录读起，不能从中间记录读起。2024/1/2210信息存储与检索6.2.1顺序文件顺序文件分类顺序有序文件记录按其主关键字有序的顺序文件为顺序有序文件。在数据库中称为顺排文档，它按某一关键字的顺序存入了数据库的全部记录，故又称为主文档。顺序无序文件记录未按其主关键字有序陈列的顺序文件为顺序无序文件。2024/1/2211信息存储与检索2、顺序文件的处置批处置2024/1/2212信息存储与检索3、顺排文档检索〔1〕顺序查找法顺序查找法即顺序扫描文件，按记录的主关键字逐个查找。要检索第i个记录，必需检索前i-1个记录。留意：①这种查找法对于少量的检索是不经济的，但适宜于批量检索。②顺序存取存储器上的文件只能用顺序查找法存取。2024/1/2213信息存储与检索顺排文档检索〔2〕分块查找法

设文件按主关键字的递增顺序，每100个记录为一块，各块的最后一个记录的主关键字为Kl00，K200，…，K100i，…。

查找时，将所要查找的记录的主关键字K，依次和各块的最后一个记录的主关键字比较，当K大于K100(i-1)且小于或等于K100i时，那么在第i块内进展扫描。

分块查找法在查找时不用扫描整个文件中的记录。2024/1/2214信息存储与检索〔3〕二分查找法二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求：1、必需采用顺序存储构造2、必需按关键字大小有序陈列。优缺陷：折半查找法的优点是比较次数少，查找速度快，平均性能好；其缺陷是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。顺排文档检索2024/1/2215信息存储与检索二分查找法算法思想首先，将表中间位置记录的关键字与查找关键字比较，假设两者相等，那么查找胜利；否那么利用中间位置记录将表分成前、后两个子表，假设中间位置记录的关键字大于查找关键字，那么进一步查找前一子表，否那么进一步查找后一子表。反复以上过程，直到找到满足条件的记录，使查找胜利，或直到子表不存在为止，此时查找不胜利。2024/1/2216信息存储与检索2024/1/2217信息存储与检索6.2.2索引文件与倒排文件1、索引文件及其运用文件的索引是指记录的关键字与相应记录的存储地址的对照表，带索引的文件称为被索引文件。索引文件由主文件和索引表构成。主文件是文件本身；索引表是文件本身外建立的一张表，它指明逻辑记录和物理记录之间的一一对应关系。索引表由假设干索引项组成。普通索引项由主关键字和该关键字所在记录的物理地址组成。索引表必需按主关键字有序；而主文件本身那么是可以按主关键字有序或无序组织。2024/1/2218信息存储与检索索引文件〔1〕索引顺序文件和索引非顺序文件主文件按主关键字有序的文件称索引顺序文件。在索引顺序文件中，可以把记录分成多个组〔块〕，可对一组记录建立一个索引项。这种索引表称为稀疏索引。稀疏索引项的指针指向的是这一组记录在磁盘中的起始位置。主文件按主关键字无序的文件称索引非顺序文件。在索引非顺序文件中，必需为每个记录建立一个索引项，这样建立的索引表称为稠密索引。2024/1/2219信息存储与检索留意：①通常将索引非顺序文件简称为索引文件。②索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头挪动，适宜于随机存取，不适宜于顺序存取。③索引顺序文件的主文件是有序的，适宜于随机存取、顺序存取。④索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件组织。⑤最常用的索引顺序文件：ISAM文件和VSAM文件。ISAM索引顺序存取方法，VSAM虚拟存储存取方法。

索引文件2024/1/2220信息存储与检索〔2〕索引文件的建立建立索引文件的过程是：按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的。待全部记录输入终了后对索引表进展排序，排序后的索引表和主文件一同就构成了索引文件。2024/1/2221信息存储与检索〔3〕索引文件的操作检索操作检索分两步进展：①将外存上含有索引区的页块送人内存，查找所需记录的物理地址。②将含有该记录的页块送人内存留意：①索引表不大时，索引表可一次读入内存，在索引文件中检索只需两次访问外存：一次读索引，一次读记录。②由于索引表有序，对索引表的查找可用顺序查找或二分查找等方法。2024/1/2222信息存储与检索索引文件的操作更新操作插入：

将插入记录置于数据区的末尾，并在索引表中插入索引项；删除：

删去相应的索引项；留意：

修正主关键字时，要同时修正索引表。2024/1/2223信息存储与检索〔4〕利用查找表建立多级索引①查找表对索引表再建立的索引，称为查找表。查找表的建立可以为占据多个页块的索引表的查阅减少外存访问次数。表3的索引表占用了三个页块的外存，每个页块能包容三个索引项，那么可为之建立一个查找表，在查找表中，列出索引表的每一页块最后一个索引项中的关键字(该块中最大的关键字)及该块的地址，如右图所示。检索记录时，先查找查找表，再查索引表，然后读取记录，三次访问外存即可。2024/1/2224信息存储与检索利用查找表建立多级索引②多级索引当查找表中工程仍很多，可建立更高一级的索引。通常最高可达四级索引：数据文件一索引表一查找表一第二查找表一第三查找表多级索引是一种静态索引。多级索引的各级索引均为顺序表，构造简单，修正很不方便，每次修正都要重组索引。

2024/1/2225信息存储与检索〔5〕动态索引动态索引构造是指文件创建、初始装入记录时所生成的索引构造，在系统运转过程中插入或删除记录时，索引构造本身也能够发生改动，改动索引构造的目的是为坚持较好的性能，例如较高的检索效率。B树和B+树都是经典的动态索引。2024/1/2226信息存储与检索2、倒排索引文档通常把在次关键字上面建立的索引称为次索引或倒排索引。在文献检索中，倒排文档是将主文件中的可检字段抽出，按某种顺序重新陈列起来所构成的一种文档。不同的字段组织成不同的倒排文档。倒排文档可以按主题词的字顺排，也可以按分类号的大小排。按表达文献内容特征的主题词陈列的文档称为根本索引文档；按表达文献外部特征陈列的文档称为辅助索引文档。2024/1/2227信息存储与检索倒排文档例如关键字相关文献数物理地址计算机3500，501，550用户3501，502，540系统软件2500，533系统硬件2501，509应用软件2500，5022024/1/2228信息存储与检索〔1〕倒排文档的组织方式和特点主索引和倒排索引的构造有差别。由于主关键字的取值是独一的，而次关键字的取值可以不独一。对应一个次关键字值的记录往往有许多个。在次关键字索引中，具有一样次关键字的记录之间不进展链接，而是列出具有该次关键字记录的物理地址。倒排文件中的次关键字索引称做倒排表。倒排表和主文件一同就构成了倒排文件。多重表文件是将索引方法和链接方法相结合的一种组织方式。对每个需求查询的次关键字建立一个索引，同时将具有一样次关键字的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字，作为索引表的一个索引项。通常多重表文件的主文件是一个顺序文件。2024/1/2229信息存储与检索多重表文件2024/1/2230信息存储与检索建立多重表索引

2024/1/2231信息存储与检索建立倒排文件索引

2024/1/2232信息存储与检索〔2〕倒排文件的查询倒排表的主要优点是：在处置复杂的多关键字查询时，可在倒排表中先完成查询的交、并等逻辑运算，得到结果后再对记录进展存取。这样不用对每个记录随机存取，把对记录的查询转换为地址集合的运算，从而提高查找速度。例：要找出一切工资级别小于13的硬件人员，那么只需将工资级别倒排表中的次关键字为10，11和12的物理地址集合先做“并〞运算，然后与职务倒排表中的硬件人员的物理地址集合做“交〞运算：{108}∪{102，106}∪{101})∩{101，102，107，110}={101，102}即符合条件的记录，其物理地址是101和102。2024/1/2233信息存储与检索作业某次活动的学生报名登记表文件，部分信息如下：

物理地址学号姓名性别年龄专业00108090325张三男18计算机00208070114李四女17外语00308090317王五男19计算机00408060330赵六女17体育00508040203田七男18信息给出性别、年龄、专业的倒排索引表，并检索年龄小于19岁的男生，写出检索过程。2024/1/2234信息存储与检索倒排文件与普通文件组织的区别

在普通的文件组织中，是先找记录，然后再找到该记录所含的各次关键字；而倒排文件中，是先给定次关键字，然后查找含有该次关键字的各个记录，这种文件的查找次序正好与普通文件的查找次序相反，因此称之为“倒排〞。留意：多重表文件实践上也是倒排文件，只不过索引的方法不同。2024/1/2235信息存储与检索6.2.3散列文件和相对文件1、散列文件散列文件是利用散列存储方式组织的文件，亦称直接存取文件。即根据文件中关键字的特点，设计一个散列函数和处置冲突的方法，将记录散列到存储设备上。2024/1/2236信息存储与检索〔1〕基桶和溢出桶在散列文件的存储单位叫桶(Bucket)。桶内的最大存储记录数目称桶因子。假设一个桶能存放m个记录，那么当桶中已有m个记录时，存放第m+1个记录会发生“溢出〞。需求将第m+1个记录存放到另一个桶中，通常称此桶为“溢出桶〞。相对地，称前m个记录存放的桶为“基桶〞。留意：溢出桶和基桶大小一样，相互之间用指针相链接。当在基桶中没有找到待查记录时，就沿着指针到所指溢出桶中进展查找，因此，希望同一散列地址的溢出桶和基桶，在磁盘上的物理位置不要相距太远，最好在同一柱面上。

2024/1/2237信息存储与检索散列文件的存放方式散列文件的记录由关键字标志，建立关键字到记录存储地址的一个映射函数，存储和访问记录均按选定的散列函数值寻址。记录由选定的散列函数决议应存放在哪个桶。记录存储桶号=HASH〔记录的关键字值〕2024/1/2238信息存储与检索散列文件例如【例】某一文件有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。由此得到的散列文件如以下图所示。

2024/1/2239信息存储与检索〔2〕散列文件的查找操作在散列文件中查找的过程：〔1〕根据给定值求出散列桶地址。〔2〕将基桶的记录读人内存，进展顺序查找。〔3〕假设找到关键字等于给定值的记录，那么检索成功；否那么，读入溢出桶的记录继续进展查找。

2024/1/2240信息存储与检索〔3〕散列文件特点实现时，桶是言语界面上可支配的外存存储单位，可以是一个记录、一个磁道、一个物理块。桶号相应是相对的记录号、磁道号、块号等，最终可以转换为外存空间上的物理地址。构造散列文件的要求是，选定一个散列函数并选定一个处置溢出记录的算法。最常运用的散列函数是除留余，即：H(key)=key%p以关键