找書的時間比辦理手續的時間長得多，因而縮短檢查時間是提高效率的關鍵。數據庫中檢
索信息也與此類似。
在沒有索引文件時，DBMS處理用戶查詢的主要操作是：
(1) 通過線性搜索匹配，確定待查信息的位置，進行定位（例如用C語言的fseek）。
(2) 定位記錄作為數據庫當前記錄且裝入工作區，作后續處理（如顯示，計算等等）。
由于采用了數據文件高速緩存，CerBase 中File_IO 模塊的LoadCurrRec(WA_N)函數能
高效地執行第二步。例如，在386/DX40 微機上，用 Turbo Profiler 測得所花平均時間
為T1＝1 微秒左右。而作第一步時，平均讀盤次數 A = 被搜索文件大小/ （緩存器大小
× 2）。設每次讀盤時間為 T2 ，（遠大于T1）則總耗時T=T1+ T2×A,顯然，如果能減少
搜索時的讀盤次數A ，就能大大提高檢索效率。
因為A 正比于被搜索文件大小，一個十分自然的解決辦法是建立一個相對較小的， 從
關鍵字到記錄位置的對查表,即下列三元組的集合: (關鍵字，記錄地址，附加信息)， 于
是，可以花較少讀盤時間來查表，然后按照記錄地址一次就讀入記錄。上述三元組稱為
索引項。其中，附加信息可以為空。保存索引項集合的文件稱為索引文件。由于索引文件
較主文件小，一般可大大減少定位時所需雙平均讀盤次數。顯然，查表又可視為如下的索
引映射IndexMap : 關鍵字集合 —＞ 記錄地址集合。
常用的索引映射有下列幾種：
1. 散列函數（Hash)
現實生活中廣泛地使用著散列函數。
例5.1 以年齡為關鍵字，定義Hash(Age) = Age Mod 12，把人按年齡分成12個組，即
通常的12屬相“鼠、牛、虎、兔，...”。 在同一屬相中再線性搜索，尋址效率提高
12倍。
例5.2 影劇場分單雙號進門，相當于Hash（N ）= N Mod 2，使觀眾入座速度提高一倍。
例5.3 在英文字典每個字母開始處貼一標簽，相當于定 Hash（WordStr）＝ WordStr[1]，
提高了查字典的效率。
2. 無序索引
索引映射 IndexMap：{關鍵字} --> { 記錄號 } ，而索引文件不排序。平均搜索次
數為關鍵字總數/2 ，由于索引文件比主文件小（通常小一個數量級， 可以全部或大部分
讀入內存，在內存中搜索定位，從而提高了速度。可以比喻為＂小無序管大有序＂。
例 5.4 一本書的目錄可看成是無序索引映射 IndexMap : 章節名稱集合 —＞ 頁碼集合。
由于目錄相對較小，易于一目十行地瀏覽，加快了檢索內容的速度。
3. 順序索引（Sequential Index)
在無序索引的基礎上作如下改進：將索引文件排序后保存，因而在索引文件中搜索關
鍵字可以用二分法，計算復雜度為 Log（N ），當N ＞30 時，就有顯著效益。順序索引
又分為兩類，即＂小有序管大有序＂ 和＂小有序管大無序＂。
4.稀索引
是＂小有序管大有序＂的改進型。既然索引文件和主文件都是排序的。那么，隔 N抽
一而建立起來的索引集合就縮小到原來的 1/N，其定位誤差小于N ，然后在N 個項中線性
搜索。
例5.5 英漢字典中的眉索引，再每頁頂上列出當頁的始詞和尾詞，組成了高效的，節省空
間的稀索引。
5.多級索引
有時，在處理數據文件時建立了索引文件，由于的規模仍然太大，為進一步提高速度，
又建立了索引的索引，以及索引的索引的索引。
例5.6 在1971年版的新華字典中查“飛”字，利用了“ 部首檢字”和“檢字表”兩級
索引，因而能在正文中迅速查出釋義，如圖5.1所示。
（建議用Edit HTML方式閱讀圖表)
┏━━━━┓ ┏━━━━┓ ┏━━━━━┓
┃ 一劃 ┃ ┃ ┃ ┃ fei┃--稀索引（書眉）
┃ 乙 15 ┃ ┃ 飛：111┃—密索引 ┃ ┃
┃ ┃ ┃ ┃ ┃飛：鳥在 ┃
┃ ┃ ┃ ┃ ┃空中的運動┃
┗━━━━┛ ┗━━━━┛ ┗━━━━━┛
部首檢字 --> 檢字表第15頁 ---> 正文111頁
圖5.1 多級索引，稀索引和密索引6.結構化索引
設在處理數據文件A.DBF 時建立了索引文件B.NDX，由于 B.NDX 的規模仍然太大，為
進一步提高速度，又建立了索引的索引 C.NDX，以及索引的索引的索引 D.NDX。但這又引
入了新問題：B、 C、 D 三個索引文件的對象層次不同，結構不同，操作三個索引文件比
較繁瑣。 能否用一個結構來實現多重索引的思想呢？ 為此，人們研究了各種各樣的結構
化索引。例如二叉樹索引、B—樹，等等。其中最成功的是 B樹及其變種B＋樹。
由于B 樹的特色和優異性能，目前的每一個成功的DBMS都采用了B 樹，每一本關于數
據結構的教科書都討論B樹。掌握B 樹的結構及其算法是DBMS開發者不可回避的任務。
)
和被動模式(Passive FTP))
)
)
)
