6文件組織與文件格式

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

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

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

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

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

【例】一個(gè)民航訂票系統(tǒng)，其檢索和更新都該當(dāng)實(shí)時(shí)處置；而銀行的賬戶系統(tǒng)需求實(shí)時(shí)檢索，但可進(jìn)展批量更新，即可以將一天的存款和提款記錄在一個(gè)事務(wù)文件上，在一天的營業(yè)之后再進(jìn)展批量處置。6.1.2記錄式文件的根本屬性2024/1/229信息存儲與檢索6.2常用文件的組織6.2.1順序文件1、定義及運(yùn)用特點(diǎn)順序文件是指按記錄進(jìn)入文件的先后順序存放，其邏輯順序和物理順序一致的文件?！斑壿嬳樞颞暿侵笇懭氲捻樞蛞来螢榈谝粋€(gè)，第二個(gè)等；“物理順序〞是指實(shí)踐存放在外存中的位置依次排在第一個(gè)記錄，第二個(gè)記錄等等。只需順序文件有這個(gè)二者一致的特點(diǎn)：先進(jìn)先出，后進(jìn)后出，且先進(jìn)者排在前。順序文件的記錄沒有標(biāo)志，可以不等長，從順序文件中讀記錄，必需從第一個(gè)記錄讀起，不能從中間記錄讀起。2024/1/2210信息存儲與檢索6.2.1順序文件順序文件分類順序有序文件記錄按其主關(guān)鍵字有序的順序文件為順序有序文件。在數(shù)據(jù)庫中稱為順排文檔，它按某一關(guān)鍵字的順序存入了數(shù)據(jù)庫的全部記錄，故又稱為主文檔。順序無序文件記錄未按其主關(guān)鍵字有序陳列的順序文件為順序無序文件。2024/1/2211信息存儲與檢索2、順序文件的處置批處置2024/1/2212信息存儲與檢索3、順排文檔檢索〔1〕順序查找法順序查找法即順序掃描文件，按記錄的主關(guān)鍵字逐個(gè)查找。要檢索第i個(gè)記錄，必需檢索前i-1個(gè)記錄。留意：①這種查找法對于少量的檢索是不經(jīng)濟(jì)的，但適宜于批量檢索。②順序存取存儲器上的文件只能用順序查找法存取。2024/1/2213信息存儲與檢索順排文檔檢索〔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信息存儲與檢索〔3〕二分查找法二分查找又稱折半查找，它是一種效率較高的查找方法。二分查找要求：1、必需采用順序存儲構(gòu)造2、必需按關(guān)鍵字大小有序陳列。優(yōu)缺陷：折半查找法的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；其缺陷是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。順排文檔檢索2024/1/2215信息存儲與檢索二分查找法算法思想首先，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，假設(shè)兩者相等，那么查找勝利；否那么利用中間位置記錄將表分成前、后兩個(gè)子表，假設(shè)中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，那么進(jìn)一步查找前一子表，否那么進(jìn)一步查找后一子表。反復(fù)以上過程，直到找到滿足條件的記錄，使查找勝利，或直到子表不存在為止，此時(shí)查找不勝利。2024/1/2216信息存儲與檢索2024/1/2217信息存儲與檢索6.2.2索引文件與倒排文件1、索引文件及其運(yùn)用文件的索引是指記錄的關(guān)鍵字與相應(yīng)記錄的存儲地址的對照表，帶索引的文件稱為被索引文件。索引文件由主文件和索引表構(gòu)成。主文件是文件本身；索引表是文件本身外建立的一張表，它指明邏輯記錄和物理記錄之間的一一對應(yīng)關(guān)系。索引表由假設(shè)干索引項(xiàng)組成。普通索引項(xiàng)由主關(guān)鍵字和該關(guān)鍵字所在記錄的物理地址組成。索引表必需按主關(guān)鍵字有序；而主文件本身那么是可以按主關(guān)鍵字有序或無序組織。2024/1/2218信息存儲與檢索索引文件〔1〕索引順序文件和索引非順序文件主文件按主關(guān)鍵字有序的文件稱索引順序文件。在索引順序文件中，可以把記錄分成多個(gè)組〔塊〕，可對一組記錄建立一個(gè)索引項(xiàng)。這種索引表稱為稀疏索引。稀疏索引項(xiàng)的指針指向的是這一組記錄在磁盤中的起始位置。主文件按主關(guān)鍵字無序的文件稱索引非順序文件。在索引非順序文件中，必需為每個(gè)記錄建立一個(gè)索引項(xiàng)，這樣建立的索引表稱為稠密索引。2024/1/2219信息存儲與檢索留意：①通常將索引非順序文件簡稱為索引文件。②索引非順序文件主文件無序，順序存取將會頻繁地引起磁頭挪動(dòng)，適宜于隨機(jī)存取，不適宜于順序存取。③索引順序文件的主文件是有序的，適宜于隨機(jī)存取、順序存取。④索引順序文件的索引是稀疏索引。索引占用空間較少，是最常用的一種文件組織。⑤最常用的索引順序文件：ISAM文件和VSAM文件。ISAM索引順序存取方法，VSAM虛擬存儲存取方法。

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

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

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

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

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

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

2024/1/2232信息存儲與檢索〔2〕倒排文件的查詢倒排表的主要優(yōu)點(diǎn)是：在處置復(fù)雜的多關(guān)鍵字查詢時(shí)，可在倒排表中先完成查詢的交、并等邏輯運(yùn)算，得到結(jié)果后再對記錄進(jìn)展存取。這樣不用對每個(gè)記錄隨機(jī)存取，把對記錄的查詢轉(zhuǎn)換為地址集合的運(yùn)算，從而提高查找速度。例：要找出一切工資級別小于13的硬件人員，那么只需將工資級別倒排表中的次關(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信息存儲與檢索作業(yè)某次活動(dòng)的學(xué)生報(bào)名登記表文件，部分信息如下：

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

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

2024/1/2237信息存儲與檢索散列文件的存放方式散列文件的記錄由關(guān)鍵字標(biāo)志，建立關(guān)鍵字到記錄存儲地址的一個(gè)映射函數(shù)，存儲和訪問記錄均按選定的散列函數(shù)值尋址。記錄由選定的散列函數(shù)決議應(yīng)存放在哪個(gè)桶。記錄存儲桶號=HASH〔記錄的關(guān)鍵字值〕2024/1/2238信息存儲與檢索散列文件例如【例】某一文件有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信息存儲與檢索〔2〕散列文件的查找操作在散列文件中查找的過程：〔1〕根據(jù)給定值求出散列桶地址?！?〕將基桶的記錄讀人內(nèi)存，進(jìn)展順序查找?！?〕假設(shè)找到關(guān)鍵字等于給定值的記錄，那么檢索成功；否那么，讀入溢出桶的記錄繼續(xù)進(jìn)展查找。

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