【正文】 效率，必須 對(duì)原文件建立索引文件 ，下面簡(jiǎn)單介紹一下索引文件的信息。 索引文件構(gòu)成 1．索引文件 索引文件由主文件和索引表構(gòu)成。 ① 主文件：文件本身。 ② 索引表：在文件本身外建立的一張表，它指明邏輯記錄和物理記錄之間的一一對(duì)應(yīng)關(guān)系。 2．索引表組成 索引表由若干索引項(xiàng)組成。一般索引項(xiàng)由主關(guān) 鍵字和該關(guān)鍵字所在記錄的物理地址組成。 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 2 索引表必須按主關(guān)鍵字有序，而主文件本身則可以按主關(guān)鍵字有序或無(wú)序。 3．索引順序文件和索引非順序文件 （ 1）索引順序文件 (Indexed Sequential File) 主文件按主關(guān)鍵字有序的文件稱(chēng)索引順序文件。 在索引順序文件中，可對(duì)一組記錄建立一個(gè)索引項(xiàng)。這種索引表稱(chēng)為稀疏索引。 （ 2）索引非順序文件 (Indexed NonSequentail File) 主文件按主關(guān)鍵字無(wú)序 的 文件稱(chēng)索引非順序文件。 在索引非順序文件中，必須為每 個(gè)記錄建立一個(gè)索引項(xiàng)，這樣建立的索引表稱(chēng)為稠密索引。 ① 通常將索引非順序文件簡(jiǎn)稱(chēng)為索引文件。 ② 索引非順序文件主文件無(wú)序，順序存取將會(huì)頻繁地引起磁頭移動(dòng)，適合于隨機(jī)存取，不適合于順序存取。 ③ 索引順序文件的主文件是有序的，適合于隨機(jī)存取、順序存取。 ④ 索引順序文件的索引是稀疏索引。索引占用空間較少，是最常用的一種文件組織。 ⑤ 最常用的索引順序文件： ISAM 文件和 VSAM 文件。 索引文件的存儲(chǔ) 1．索引文件的存儲(chǔ) 索引文件在存儲(chǔ)器上分為兩 個(gè)區(qū)：索引區(qū)和數(shù)據(jù)區(qū)。索引區(qū)存放索引表，數(shù)據(jù)區(qū)存放主文件。 2． 索引文件的建立 建立索引文件的過(guò)程： （ 1） 按輸入記錄的先后次序建立數(shù)據(jù)區(qū)和索引表。其中索引表中關(guān)鍵字是無(wú)序的 （ 2） 待全部記錄輸入完畢后對(duì)索引表進(jìn)行排序，排序后的索引表和主文件一起就形成了索引文件。 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 3 索引文件的操作 1．檢索操作 檢索分兩步進(jìn)行： ① 將外存上含有索引區(qū)的頁(yè)塊送 入 內(nèi)存，查找所需記錄的物理地址 ② 將含有該記錄的頁(yè)塊送 入 內(nèi)存 需要 注意 的是 ： ① 索引表不大時(shí)，索 引表可一次讀入內(nèi)存，在索引文件中檢索只需兩次訪問(wèn)外存：一次讀索引，一次讀記錄。 ② 由于索引表有序，對(duì)索引表的查找可用順序查找或二分查找等方法。 2．更新操作 （ 1） 插入： 將插入記錄置于數(shù)據(jù)區(qū)的末尾，并在索引表中插入索引項(xiàng)； （ 2） 刪除： 刪去相應(yīng)的索引項(xiàng)； 需要 注意 的是 ：在 修改主關(guān)鍵字時(shí)，要同時(shí)修改索引表。 利用查找表建立多級(jí)索引 1．查找表 對(duì)索引表建立的索引，稱(chēng)為查找表。查找表的建立可以為占據(jù)多個(gè)頁(yè)塊的索引表的查閱減少外存訪問(wèn)次數(shù)。 2．多級(jí)索引 當(dāng)查找表中項(xiàng)目仍很多，可建立更高一級(jí)的索引。通常最高可達(dá)四級(jí)索引： 數(shù)據(jù)文件 一 — 索引表 —— 查找表 —— 第二查找表 —— 第三查找表。 ① 多級(jí)索引是一種靜態(tài)索引 ② 多級(jí)索引的各級(jí)索引均為順序表，結(jié)構(gòu)簡(jiǎn)單，修改很不方便，每次修改都要重組索引。 3． 動(dòng)態(tài)索引 當(dāng)數(shù)據(jù)文件在使用過(guò)程中記錄變動(dòng)較多時(shí)，利用二叉排序樹(shù) (或 AVL 樹(shù) )、沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 4 B_樹(shù) (或其變型 )等樹(shù)表結(jié)構(gòu)建立的索引，為動(dòng)態(tài)索引。 （ 1）樹(shù)表特點(diǎn) ① 插入、刪除方便 ② 本身是層次結(jié)構(gòu)，無(wú)須建立多級(jí)索引 ③ 建立索引表的過(guò)程即為排序過(guò)程。 （ 2）樹(shù)表結(jié)構(gòu)選擇 ① 當(dāng)數(shù)據(jù)文件的記錄數(shù)不很多，內(nèi)存容量足以容納整個(gè)索引表時(shí)，可采用二叉排序樹(shù) (或 AVL 樹(shù) )作索引； ② 當(dāng)文件很大時(shí)，索引表 (樹(shù)表 )本身也在外存，查找索引時(shí)訪問(wèn)外存的次數(shù)恰為查找路徑上的結(jié)點(diǎn)數(shù)。采用 m 階 B樹(shù) (或其變型 )作為索引表為宜（ m的選擇取決于索引項(xiàng)的多少和緩沖區(qū)的大?。?。 （ 3）外存的索引表的查找性能評(píng)價(jià) 由于訪問(wèn)外存的時(shí)間比內(nèi)存中查找的時(shí)間大得多，所以外存的索引表的查找性能主要著眼于訪問(wèn)外存的次數(shù)，即索引表的深度。 設(shè) 計(jì)目標(biāo) 本課題最終成果是一個(gè)可以實(shí)現(xiàn) 快速文件內(nèi)容查找的工具?；竟δ苋缦拢? 系統(tǒng)支持多文本文檔的導(dǎo)入，是對(duì)多文件進(jìn)行操作。 為了提高查詢(xún)效率，必須建立索引文件。本系統(tǒng)采用倒排文件的方法對(duì)原文件建立索引，索引文件與原文件之前用指針鏈接，查詢(xún)時(shí)先在由鍵盤(pán)輸入查找關(guān)鍵字，然后 到索引文件的詞文件中查找與查找關(guān)鍵字相同的字段，如果兩者相同，通過(guò)鏈接的指針，可給出該詞在原文中的位置，并將其前后約 20個(gè)字符顯示出來(lái)。并給出該詞在原文件中出現(xiàn)的頻率。 本系統(tǒng)是英文類(lèi)別的查找工具。處理時(shí)詞與詞之間用空格與回車(chē)換行 符做為隔符 。 本系統(tǒng)是對(duì)常用詞表進(jìn)行查找的工具，因此詞庫(kù)文件由手動(dòng)添加。這樣可以過(guò)濾一些沒(méi)有意義的詞。 由于是常用詞表查找，所以本系統(tǒng)查找算法采用順序查找算法實(shí)現(xiàn)。 如時(shí)間充裕，可考慮擴(kuò)充詞庫(kù)文件為跟據(jù)導(dǎo)入文件自動(dòng)建立，并分別 建立順序查找，折半查找及二分查找 ，比較其查詢(xún)效率，擇優(yōu)用之。 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 5 第二章 關(guān)鍵問(wèn)題分析 索引算法分析 散列文件的組織方式 散列文件是利用散列存儲(chǔ)方式組織的文件，亦稱(chēng)直接存取文件。即根據(jù)文件中關(guān)鍵字的特點(diǎn)，設(shè)計(jì)一個(gè)散列函數(shù)和處理沖突的方法，將記錄散列 到存儲(chǔ)設(shè)備上。 散列表與散列文件比較 如表 比較項(xiàng)目 散列表 散列文件 存儲(chǔ)單位 若干記錄為一組 桶 處理沖突辦法 開(kāi)放地址法、拉鏈法 拉鏈法 表 基桶和溢出桶 在散列文件的存儲(chǔ)單位叫桶 (Bucket)。假如一個(gè)桶能存放 m 個(gè)記錄，則當(dāng)桶中已有 m 個(gè)同義詞的記錄時(shí)，存放第 m+1 個(gè)同義詞會(huì)發(fā)生 溢出 。需要將第m+1 個(gè)同義詞存放到另一個(gè)桶中，通常稱(chēng)此桶為 溢出桶 。相對(duì)地，稱(chēng)前 m個(gè)同義詞存放的桶為 基桶 。 (1)溢出桶和基桶大小相同，相互之間用指針相鏈接。 (2)當(dāng) 在基桶中沒(méi)有找到待查記錄時(shí)，就沿著指針到所指溢出桶中進(jìn)行查找，因此，希望同一散列地址的溢出桶和基桶，在磁盤(pán)上的物理位置不要相距太遠(yuǎn)，最好在同一柱面上。 散列文件的查找操作 在散列文件中查找的過(guò)程： （ 1） 根據(jù)給定值求出散列桶地址 （ 2） 將基桶的記錄讀人內(nèi)存，進(jìn)行順序查找 （ 3） 若找到關(guān)鍵字等于給定值的記錄，則檢索成功；否則，讀人溢出桶的 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 6 記錄繼續(xù)進(jìn)行查找。 散列文件的刪除操作 在散列文件中刪去一個(gè)記錄，僅需對(duì)被刪記錄作刪除標(biāo)記即可。 散列文件的特點(diǎn) 1） 散列文 件的優(yōu)點(diǎn) （ 1） 文件隨機(jī)存放，記錄不需進(jìn)行排序。 （ 2） 插入、刪除方便。 （ 3） 存取速度快；不需要索引區(qū)，節(jié)省存儲(chǔ)空間。 2） 散列文件的缺點(diǎn) （ 1） 不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取 （ 2） 詢(xún)問(wèn)方式限于簡(jiǎn)單詢(xún)問(wèn) （ 3） 在經(jīng)過(guò)多次插入、刪除后，可能造成文件結(jié)構(gòu)不合理，需要重新組織文件。 多關(guān)鍵字文件 1．多關(guān)鍵字文件 包含有多個(gè)次關(guān)鍵字索引的文件稱(chēng)為多關(guān)鍵字文件。 2．多關(guān)鍵字文件和其他文件的區(qū)別 如表 多關(guān)鍵字文件 其他文件 包含 的關(guān)鍵字 主關(guān)鍵字外還有多個(gè)次關(guān)鍵字 只含一個(gè)主關(guān)鍵字索引 建立的索引 建立主關(guān)鍵字索引和多個(gè)次關(guān)健字索引 只有（沒(méi)有）主關(guān)鍵字索引查詢(xún) 查詢(xún) 對(duì)主關(guān)鍵字索引或次關(guān)鍵字索引查詢(xún) 只能順序存取主文件記錄進(jìn)行比較，效率低 文件組織方式 四種基本組織方法都可以 四種組織方法都可以 表 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 7 多重表文件 多重表文件的組織方式 多重表文件是將索引方法和鏈接方法相結(jié)合的一種組織方式。 具體組織方式： 對(duì)每個(gè)需要查詢(xún)的次關(guān)鍵字建立一個(gè)索引，同時(shí)將具有相同次關(guān)鍵字的記錄鏈接成一 個(gè)鏈表，并將此鏈表的頭指針、鏈表長(zhǎng)度及次關(guān)鍵字，作為索引表的一個(gè)索引項(xiàng)。通常多重表文件的主文件是一個(gè)順序文件。 多重表文件的查詢(xún)操作 （ 1） 單關(guān)鍵字簡(jiǎn)單查詢(xún)基本思想 據(jù)給定值，在對(duì)應(yīng)次關(guān)鍵字索引表中找到對(duì)應(yīng)索引項(xiàng)，從頭指針出發(fā)，列出該鏈表上所有記錄。 （ 2） 多關(guān)鍵字組合查詢(xún)基本思想 在查找同時(shí)滿(mǎn)足兩多個(gè)關(guān)鍵字條件得記錄時(shí)，可先比較兩（多）個(gè)索引鏈表的長(zhǎng)度，然后選較短的鏈表進(jìn)行查找。 多重表的更新操作 1．插入新記錄 相同次關(guān)鍵字鏈表不按主關(guān)鍵字大小鏈接時(shí)，在主 文件中插入新記錄后，將記錄在各個(gè)次關(guān)鍵字鏈表中插在鏈表的頭指針之后即可。 2．刪除記錄 在刪去一個(gè)記錄的同時(shí)，需在每個(gè)次關(guān)鍵字的鏈表中刪去該記錄。 倒排文件 1．倒排文件的組織方式和特點(diǎn) 倒排文件和多重表文件不同。在次關(guān)鍵字索引中，具有相同次關(guān)鍵字的記錄之間不進(jìn)行鏈接，而是列出具有該次關(guān)鍵字記錄的物理地址。 倒排文件中的次關(guān)鍵字索引稱(chēng)做倒排表。倒排表和主文件一起就構(gòu)成了倒排文件。 2．倒排文件的查詢(xún) 倒排表的主要優(yōu)點(diǎn)是：在處理復(fù)雜的多關(guān)鍵字查詢(xún)時(shí) ，可在倒排表中先完成沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 8 查詢(xún)的交、并等邏輯運(yùn)算，得到結(jié)果后再對(duì)記錄進(jìn)行存取。這樣不必對(duì)每個(gè)記錄隨機(jī)存取，把對(duì)記錄的查詢(xún)轉(zhuǎn)換為地址集合的運(yùn)算，從而提高查找速度。 3．倒排文件的更新 在插入和刪除記錄時(shí)，還要修改倒排表。 4．列出主關(guān)鍵字的倒排表 列出主關(guān)鍵字的倒排表的特點(diǎn)： (1) 存取速度較慢 (2) 主關(guān)鍵字可看成是記錄的符號(hào)地址，對(duì)于存儲(chǔ)具有相對(duì)獨(dú)立性。 5．倒排文件與一般文件組織的區(qū)別 在一般的文件組織中，是先找記錄，然后再找到該記錄所含的各次關(guān)鍵字；而倒排文件中，是先