6文件組織與文件格式

第六章文件組織與文件格式第六章文件組織與文件格式6.1外存數(shù)據(jù)的組織6.2常用文件的組織6.3超文本與流媒體6.4圖形文件與其它文件格式2024/1/222信息存儲(chǔ)與檢索6.1外存數(shù)據(jù)的組織6.1.1兩類外存數(shù)據(jù)1、文件文件組織中的數(shù)據(jù)的構(gòu)造組織方式普通可分為兩類：流式文件和記錄文件。流式文件是數(shù)據(jù)的序列集合，可以看成是數(shù)據(jù)的字節(jié)流。記錄文件是邏輯記錄的集合，記錄是按存儲(chǔ)數(shù)據(jù)在邏輯上的獨(dú)立含義來(lái)劃分的一個(gè)數(shù)據(jù)構(gòu)造單位。文件組織方式的根本特征是，用邏輯記錄的定義來(lái)實(shí)現(xiàn)信息實(shí)體組成屬性的數(shù)據(jù)聯(lián)絡(luò)。而文件和文件之間能夠存在的聯(lián)絡(luò)只能依托用戶程序?qū)@些文件的處置邏輯來(lái)表達(dá)。2024/1/223信息存儲(chǔ)與檢索6.1、外存數(shù)據(jù)的組織數(shù)據(jù)庫(kù)文件數(shù)據(jù)庫(kù)中的文件是性質(zhì)一樣的記錄的集合。數(shù)據(jù)庫(kù)中所研討的文件是帶有構(gòu)造的記錄集合，每個(gè)記錄可由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成。數(shù)據(jù)庫(kù)中的記錄是文件中存取的根本單位，數(shù)據(jù)項(xiàng)是文件可運(yùn)用的最小單位。數(shù)據(jù)項(xiàng)有時(shí)也稱為字段或者稱為屬性，其值能獨(dú)一標(biāo)志一個(gè)記錄的數(shù)據(jù)項(xiàng)或數(shù)據(jù)項(xiàng)的組合者稱為主關(guān)鍵字項(xiàng)。2024/1/224信息存儲(chǔ)與檢索【例】下表是一個(gè)簡(jiǎn)單的職工文件。每個(gè)職工情況是一個(gè)記錄，它由7個(gè)數(shù)據(jù)項(xiàng)組成。其中"職工號(hào)"可作為主關(guān)鍵字項(xiàng)，它能獨(dú)一標(biāo)識(shí)一個(gè)記錄，即它的值對(duì)恣意兩個(gè)記錄都是不同的。姓名、性別等數(shù)據(jù)只能作為次關(guān)鍵字項(xiàng)，由于它們的值對(duì)不同的記錄可以是一樣的。

2024/1/225信息存儲(chǔ)與檢索6.1外存數(shù)據(jù)的組織6.1.2記錄式文件的根本屬性1、組織方式記錄式文件是記錄值的集合，記錄值在文件物理存儲(chǔ)空間上的存放方式稱為文件組織方式。一方面組織方式涉及文件的物理構(gòu)造；另一方面在用戶的言語(yǔ)界面上文件的組織方式又作為一種邏輯屬性來(lái)定義，用戶按對(duì)外存數(shù)據(jù)的存取要求來(lái)選擇文件的組織方式。2024/1/226信息存儲(chǔ)與檢索常用的文件組織方式順序文件索引文件相對(duì)文件散列文件2024/1/227信息存儲(chǔ)與檢索6.1.2記錄式文件的根本屬性2、存取方式順序存取方式：沿某種含義的序列，從序列的指定位置開(kāi)場(chǎng)依次地存取每一個(gè)后繼記錄。隨機(jī)存取方式：指定記錄值的某種標(biāo)志，按標(biāo)志存取特定的一個(gè)記錄。3、駐留介質(zhì)文件的組織方式和駐留介質(zhì)有制約關(guān)系，如磁帶文件、打印機(jī)文件、卡片文件只能是順序文件。磁盤(pán)文件可以運(yùn)用各種組織方式。2024/1/228信息存儲(chǔ)與檢索4、處置方式

文件上檢索和更新操作，都可有實(shí)時(shí)和批量?jī)煞N不同的處置方式。

①實(shí)時(shí)處置：呼應(yīng)時(shí)間要求嚴(yán)厲，要求在接受訊問(wèn)后幾秒種內(nèi)完成檢索和更新。

②批量處置：呼應(yīng)時(shí)間要求寬松一些，不同的文件系統(tǒng)有不同的要求。

【例】一個(gè)民航訂票系統(tǒng)，其檢索和更新都該當(dāng)實(shí)時(shí)處置；而銀行的賬戶系統(tǒng)需求實(shí)時(shí)檢索，但可進(jìn)展批量更新，即可以將一天的存款和提款記錄在一個(gè)事務(wù)文件上，在一天的營(yíng)業(yè)之后再進(jìn)展批量處置。6.1.2記錄式文件的根本屬性2024/1/229信息存儲(chǔ)與檢索6.2常用文件的組織6.2.1順序文件1、定義及運(yùn)用特點(diǎn)順序文件是指按記錄進(jìn)入文件的先后順序存放，其邏輯順序和物理順序一致的文件?！斑壿嬳樞颞暿侵笇?xiě)入的順序依次為第一個(gè)，第二個(gè)等；“物理順序〞是指實(shí)踐存放在外存中的位置依次排在第一個(gè)記錄，第二個(gè)記錄等等。只需順序文件有這個(gè)二者一致的特點(diǎn)：先進(jìn)先出，后進(jìn)后出，且先進(jìn)者排在前。順序文件的記錄沒(méi)有標(biāo)志，可以不等長(zhǎng)，從順序文件中讀記錄，必需從第一個(gè)記錄讀起，不能從中間記錄讀起。2024/1/2210信息存儲(chǔ)與檢索6.2.1順序文件順序文件分類順序有序文件記錄按其主關(guān)鍵字有序的順序文件為順序有序文件。在數(shù)據(jù)庫(kù)中稱為順排文檔，它按某一關(guān)鍵字的順序存入了數(shù)據(jù)庫(kù)的全部記錄，故又稱為主文檔。順序無(wú)序文件記錄未按其主關(guān)鍵字有序陳列的順序文件為順序無(wú)序文件。2024/1/2211信息存儲(chǔ)與檢索2、順序文件的處置批處置2024/1/2212信息存儲(chǔ)與檢索3、順排文檔檢索〔1〕順序查找法順序查找法即順序掃描文件，按記錄的主關(guān)鍵字逐個(gè)查找。要檢索第i個(gè)記錄，必需檢索前i-1個(gè)記錄。留意：①這種查找法對(duì)于少量的檢索是不經(jīng)濟(jì)的，但適宜于批量檢索。②順序存取存儲(chǔ)器上的文件只能用順序查找法存取。2024/1/2213信息存儲(chǔ)與檢索順排文檔檢索〔2〕分塊查找法

設(shè)文件按主關(guān)鍵字的遞增順序，每100個(gè)記錄為一塊，各塊的最后一個(gè)記錄的主關(guān)鍵字為Kl00，K200，…，K100i，…。

查找時(shí)，將所要查找的記錄的主關(guān)鍵字K，依次和各塊的最后一個(gè)記錄的主關(guān)鍵字比較，當(dāng)K大于K100(i-1)且小于或等于K100i時(shí)，那么在第i塊內(nèi)進(jìn)展掃描。

分塊查找法在查找時(shí)不用掃描整個(gè)文件中的記錄。2024/1/2214信息存儲(chǔ)與檢索〔3〕二分查找法二分查找又稱折半查找，它是一種效率較高的查找方法。二分查找要求：1、必需采用順序存儲(chǔ)構(gòu)造2、必需按關(guān)鍵字大小有序陳列。優(yōu)缺陷：折半查找法的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；其缺陷是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。順排文檔檢索2024/1/2215信息存儲(chǔ)與檢索二分查找法算法思想首先，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，假設(shè)兩者相等，那么查找勝利；否那么利用中間位置記錄將表分成前、后兩個(gè)子表，假設(shè)中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，那么進(jìn)一步查找前一子表，否那么進(jìn)一步查找后一子表。反復(fù)以上過(guò)程，直到找到滿足條件的記錄，使查找勝利，或直到子表不存在為止，此時(shí)查找不勝利。2024/1/2216信息存儲(chǔ)與檢索2024/1/2217信息存儲(chǔ)與檢索6.2.2索引文件與倒排文件1、索引文件及其運(yùn)用文件的索引是指記錄的關(guān)鍵字與相應(yīng)記錄的存儲(chǔ)地址的對(duì)照表，帶索引的文件稱為被索引文件。索引文件由主文件和索引表構(gòu)成。主文件是文件本身；索引表是文件本身外建立的一張表，它指明邏輯記錄和物理記錄之間的一一對(duì)應(yīng)關(guān)系。索引表由假設(shè)干索引項(xiàng)組成。普通索引項(xiàng)由主關(guān)鍵字和該關(guān)鍵字所在記錄的物理地址組成。索引表必需按主關(guān)鍵字有序；而主文件本身那么是可以按主關(guān)鍵字有序或無(wú)序組織。2024/1/2218信息存儲(chǔ)與檢索索引文件〔1〕索引順序文件和索引非順序文件主文件按主關(guān)鍵字有序的文件稱索引順序文件。在索引順序文件中，可以把記錄分成多個(gè)組〔塊〕，可對(duì)一組記錄建立一個(gè)索引項(xiàng)。這種索引表稱為稀疏索引。稀疏索引項(xiàng)的指針指向的是這一組記錄在磁盤(pán)中的起始位置。主文件按主關(guān)鍵字無(wú)序的文件稱索引非順序文件。在索引非順序文件中，必需為每個(gè)記錄建立一個(gè)索引項(xiàng)，這樣建立的索引表稱為稠密索引。2024/1/2219信息存儲(chǔ)與檢索留意：①通常將索引非順序文件簡(jiǎn)稱為索引文件。②索引非順序文件主文件無(wú)序，順序存取將會(huì)頻繁地引起磁頭挪動(dòng)，適宜于隨機(jī)存取，不適宜于順序存取。③索引順序文件的主文件是有序的，適宜于隨機(jī)存取、順序存取。④索引順序文件的索引是稀疏索引。索引占用空間較少，是最常用的一種文件組織。⑤最常用的索引順序文件：ISAM文件和VSAM文件。ISAM索引順序存取方法，VSAM虛擬存儲(chǔ)存取方法。

索引文件2024/1/2220信息存儲(chǔ)與檢索〔2〕索引文件的建立建立索引文件的過(guò)程是：按輸入記錄的先后次序建立數(shù)據(jù)區(qū)和索引表。其中索引表中關(guān)鍵字是無(wú)序的。待全部記錄輸入終了后對(duì)索引表進(jìn)展排序，排序后的索引表和主文件一同就構(gòu)成了索引文件。2024/1/2221信息存儲(chǔ)與檢索〔3〕索引文件的操作檢索操作檢索分兩步進(jìn)展：①將外存上含有索引區(qū)的頁(yè)塊送人內(nèi)存，查找所需記錄的物理地址。②將含有該記錄的頁(yè)塊送人內(nèi)存留意：①索引表不大時(shí)，索引表可一次讀入內(nèi)存，在索引文件中檢索只需兩次訪問(wèn)外存：一次讀索引，一次讀記錄。②由于索引表有序，對(duì)索引表的查找可用順序查找或二分查找等方法。2024/1/2222信息存儲(chǔ)與檢索索引文件的操作更新操作插入：

將插入記錄置于數(shù)據(jù)區(qū)的末尾，并在索引表中插入索引項(xiàng)；刪除：

刪去相應(yīng)的索引項(xiàng)；留意：

修正主關(guān)鍵字時(shí)，要同時(shí)修正索引表。2024/1/2223信息存儲(chǔ)與檢索〔4〕利用查找表建立多級(jí)索引①查找表對(duì)索引表再建立的索引，稱為查找表。查找表的建立可以為占據(jù)多個(gè)頁(yè)塊的索引表的查閱減少外存訪問(wèn)次數(shù)。表3的索引表占用了三個(gè)頁(yè)塊的外存，每個(gè)頁(yè)塊能包容三個(gè)索引項(xiàng)，那么可為之建立一個(gè)查找表，在查找表中，列出索引表的每一頁(yè)塊最后一個(gè)索引項(xiàng)中的關(guān)鍵字(該塊中最大的關(guān)鍵字)及該塊的地址，如右圖所示。檢索記錄時(shí)，先查找查找表，再查索引表，然后讀取記錄，三次訪問(wèn)外存即可。2024/1/2224信息存儲(chǔ)與檢索利用查找表建立多級(jí)索引②多級(jí)索引當(dāng)查找表中工程仍很多，可建立更高一級(jí)的索引。通常最高可達(dá)四級(jí)索引：數(shù)據(jù)文件一索引表一查找表一第二查找表一第三查找表多級(jí)索引是一種靜態(tài)索引。多級(jí)索引的各級(jí)索引均為順序表，構(gòu)造簡(jiǎn)單，修正很不方便，每次修正都要重組索引。

2024/1/2225信息存儲(chǔ)與檢索〔5〕動(dòng)態(tài)索引動(dòng)態(tài)索引構(gòu)造是指文件創(chuàng)建、初始裝入記錄時(shí)所生成的索引構(gòu)造，在系統(tǒng)運(yùn)轉(zhuǎn)過(guò)程中插入或刪除記錄時(shí)，索引構(gòu)造本身也能夠發(fā)生改動(dòng)，改動(dòng)索引構(gòu)造的目的是為堅(jiān)持較好的性能，例如較高的檢索效率。B樹(shù)和B+樹(shù)都是經(jīng)典的動(dòng)態(tài)索引。2024/1/2226信息存儲(chǔ)與檢索2、倒排索引文檔通常把在次關(guān)鍵字上面建立的索引稱為次索引或倒排索引。在文獻(xiàn)檢索中，倒排文檔是將主文件中的可檢字段抽出，按某種順序重新陳列起來(lái)所構(gòu)成的一種文檔。不同的字段組織成不同的倒排文檔。倒排文檔可以按主題詞的字順排，也可以按分類號(hào)的大小排。按表達(dá)文獻(xiàn)內(nèi)容特征的主題詞陳列的文檔稱為根本索引文檔；按表達(dá)文獻(xiàn)外部特征陳列的文檔稱為輔助索引文檔。2024/1/2227信息存儲(chǔ)與檢索倒排文檔例如關(guān)鍵字相關(guān)文獻(xiàn)數(shù)物理地址計(jì)算機(jī)3500，501，550用戶3501，502，540系統(tǒng)軟件2500，533系統(tǒng)硬件2501，509應(yīng)用軟件2500，5022024/1/2228信息存儲(chǔ)與檢索〔1〕倒排文檔的組織方式和特點(diǎn)主索引和倒排索引的構(gòu)造有差別。由于主關(guān)鍵字的取值是獨(dú)一的，而次關(guān)鍵字的取值可以不獨(dú)一。對(duì)應(yīng)一個(gè)次關(guān)鍵字值的記錄往往有許多個(gè)。在次關(guān)鍵字索引中，具有一樣次關(guān)鍵字的記錄之間不進(jìn)展鏈接，而是列出具有該次關(guān)鍵字記錄的物理地址。倒排文件中的次關(guān)鍵字索引稱做倒排表。倒排表和主文件一同就構(gòu)成了倒排文件。多重表文件是將索引方法和鏈接方法相結(jié)合的一種組織方式。對(duì)每個(gè)需求查詢的次關(guān)鍵字建立一個(gè)索引，同時(shí)將具有一樣次關(guān)鍵字的記錄鏈接成一個(gè)鏈表，并將此鏈表的頭指針、鏈表長(zhǎng)度及次關(guān)鍵字，作為索引表的一個(gè)索引項(xiàng)。通常多重表文件的主文件是一個(gè)順序文件。2024/1/2229信息存儲(chǔ)與檢索多重表文件2024/1/2230信息存儲(chǔ)與檢索建立多重表索引

2024/1/2231信息存儲(chǔ)與檢索建立倒排文件索引

2024/1/2232信息存儲(chǔ)與檢索〔2〕倒排文件的查詢倒排表的主要優(yōu)點(diǎn)是：在處置復(fù)雜的多關(guān)鍵字查詢時(shí)，可在倒排表中先完成查詢的交、并等邏輯運(yùn)算，得到結(jié)果后再對(duì)記錄進(jìn)展存取。這樣不用對(duì)每個(gè)記錄隨機(jī)存取，把對(duì)記錄的查詢轉(zhuǎn)換為地址集合的運(yùn)算，從而提高查找速度。例：要找出一切工資級(jí)別小于13的硬件人員，那么只需將工資級(jí)別倒排表中的次關(guān)鍵字為10，11和12的物理地址集合先做“并〞運(yùn)算，然后與職務(wù)倒排表中的硬件人員的物理地址集合做“交〞運(yùn)算：{108}∪{102，106}∪{101})∩{101，102，107，110}={101，102}即符合條件的記錄，其物理地址是101和102。2024/1/2233信息存儲(chǔ)與檢索作業(yè)某次活動(dòng)的學(xué)生報(bào)名登記表文件，部分信息如下：

物理地址學(xué)號(hào)姓名性別年齡專業(yè)00108090325張三男18計(jì)算機(jī)00208070114李四女17外語(yǔ)00308090317王五男19計(jì)算機(jī)00408060330趙六女17體育00508040203田七男18信息給出性別、年齡、專業(yè)的倒排索引表，并檢索年齡小于19歲的男生，寫(xiě)出檢索過(guò)程。2024/1/2234信息存儲(chǔ)與檢索倒排文件與普通文件組織的區(qū)別

在普通的文件組織中，是先找記錄，然后再找到該記錄所含的各次關(guān)鍵字；而倒排文件中，是先給定次關(guān)鍵字，然后查找含有該次關(guān)鍵字的各個(gè)記錄，這種文件的查找次序正好與普通文件的查找次序相反，因此稱之為“倒排〞。留意：多重表文件實(shí)踐上也是倒排文件，只不過(guò)索引的方法不同。2024/1/2235信息存儲(chǔ)與檢索6.2.3散列文件和相對(duì)文件1、散列文件散列文件是利用散列存儲(chǔ)方式組織的文件，亦稱直接存取文件。即根據(jù)文件中關(guān)鍵字的特點(diǎn)，設(shè)計(jì)一個(gè)散列函數(shù)和處置沖突的方法，將記錄散列到存儲(chǔ)設(shè)備上。2024/1/2236信息存儲(chǔ)與檢索〔1〕基桶和溢出桶在散列文件的存儲(chǔ)單位叫桶(Bucket)。桶內(nèi)的最大存儲(chǔ)記錄數(shù)目稱桶因子。假設(shè)一個(gè)桶能存放m個(gè)記錄，那么當(dāng)桶中已有m個(gè)記錄時(shí)，存放第m+1個(gè)記錄會(huì)發(fā)生“溢出〞。需求將第m+1個(gè)記錄存放到另一個(gè)桶中，通常稱此桶為“溢出桶〞。相對(duì)地，稱前m個(gè)記錄存放的桶為“基桶〞。留意：溢出桶和基桶大小一樣，相互之間用指針相鏈接。當(dāng)在基桶中沒(méi)有找到待查記錄時(shí)，就沿著指針到所指溢出桶中進(jìn)展查找，因此，希望同一散列地址的溢出桶和基桶，在磁盤(pán)上的物理位置不要相距太遠(yuǎn)，最好在同一柱面上。

2024/1/2237信息存儲(chǔ)與檢索散列文件的存放方式散列文件的記錄由關(guān)鍵字標(biāo)志，建立關(guān)鍵字到記錄存儲(chǔ)地址的一個(gè)映射函數(shù)，存儲(chǔ)和訪問(wèn)記錄均按選定的散列函數(shù)值尋址。記錄由選定的散列函數(shù)決議應(yīng)存放在哪個(gè)桶。記錄存儲(chǔ)桶號(hào)=HASH〔記錄的關(guān)鍵字值〕2024/1/2238信息存儲(chǔ)與檢索散列文件例如【例】某一文件有16個(gè)記錄，其關(guān)鍵字分別為：23，05，26，01，18，02，27，12，07，09，04，19，06，16，33，24。桶的容量m=3，桶數(shù)b=7。用除余法作散列函數(shù)H(key)=key％7。由此得到的散列文件如以下圖所示。

2024/1/2239信息存儲(chǔ)與檢索〔2〕散列文件的查找操作在散列文件中查找的過(guò)程：〔1〕根據(jù)給定值求出散列桶地址?！?〕將基桶的記錄讀人內(nèi)存，進(jìn)展順序查找?！?〕假設(shè)找到關(guān)鍵字等于給定值的記錄，那么檢索成功；否那么，讀入溢出桶的記錄繼續(xù)進(jìn)展查找。

2024/1/2240信息存儲(chǔ)與檢索〔3〕散列文件特點(diǎn)實(shí)現(xiàn)時(shí)，桶是言語(yǔ)界面上可支配的外存存儲(chǔ)單位，可以是一個(gè)記錄、一個(gè)磁道、一個(gè)物理塊。桶號(hào)相應(yīng)是相對(duì)的記錄號(hào)、磁道號(hào)、塊號(hào)等，最終可以轉(zhuǎn)換為外存空間上的物理地址。構(gòu)造散列文件的要求是，選定一個(gè)散列函數(shù)并選定一個(gè)處置溢出記錄的算法。最常運(yùn)用的散列函數(shù)是除留余，即：H(key)=key%p以關(guān)鍵