索引順序訪問方法

索引順序訪問方法

索引順序訪問方法(ISAM, Indexed Sequential Access Method),也可以稱之為索引順序存取方法,可以連續地(按照他們進入的順序)或者任意地(根據索引)記錄任何訪問。每個索引定義了一次不同排列的記錄。索引順序訪問檔案是一種專為磁碟存取檔案設計的檔案組織方式,採用靜態索引結構。 由於磁碟是以盤組、柱面和磁軌三級地址存取的設備,則可對磁碟上的數據檔案建立盤組、柱面和磁軌多級索引。有兩種訪問方法:基本的索引順序訪問方法和佇列式的索引順序訪問方法。

索引檔案

索引檔案由數據檔案組成,它是帶索引的順序檔案。索引本身非常小,只占兩個欄位:順序檔案的鍵和在磁碟上相應記錄的地址。存取檔案中的記錄需按以下步驟:

(1)整個索引檔案都載入到記憶體中(檔案很小,只占用很小的記憶體空間)。

(2)搜尋項目,用高效的算法(如折半查詢法)查找目標鍵。

(3)檢索記錄的地址。

(4)按照地址,檢索數據記錄並返回給用戶。

索引檔案由索引表和主檔案兩部分構成。

索引表是一張指示邏輯記錄和物理記錄之間對應關係的表。索引表中的每項稱作索引項。索引項是按鍵(或邏輯記錄號)順序排列。若檔案本身也是按關鍵字順序排列,則稱為索引順序檔案。否則,稱為索引非順序檔案。

檔案

ISAM檔案的組成

索引順序訪問方法 索引順序訪問方法

SAM檔案由多級主索引、柱面索引、磁軌索引和主檔案組成。
檔案的記錄在同一盤組上存放時,應先集中放在一個柱面上,然後再順序存放在相鄰的柱面上。對同一柱面,則應按盤面的次序順序存放。

如圖所示的檔案是存放在同一個磁碟組上的ISAM檔案。

其中:

① C表示柱面;

② T表示磁軌;

③ CiTi表示i號柱面,j號磁軌;

④ Ri表示主關鍵字為i的記錄。

分析:

從圖中可看出,主索引是柱面索引的索引,這裡只有一級主索引。若檔案占用的柱面索引很大,使得一級主索引也很大時,可採用多級主索引。當然,若柱面索引較小時,則主索引可省略。

通常主索引和柱面索引放在同一個柱面上,主索引放在該柱面最前的一個磁軌上,其後的磁軌中存放柱面索引。每個存放主檔案的柱面都建立有一個磁軌索引,放在該柱面的最前面的磁軌To上,其後的若干個磁軌是存放主檔案記錄的基本區,該柱面最後的若干個磁軌是溢出區。基本區中的記錄是按主關鍵字大小順序存儲的,溢出區被整個柱面上的基本區中各磁軌共享,當基本區中某磁軌溢出時,就將該磁軌的溢出記錄,按主關鍵字大小鏈成一個鍊表(以下簡稱溢出鍊表)放人溢出區。

各級索引中的索引項結構

索引順序訪問方法 索引順序訪問方法

磁軌索引中的每一個索引項,都由兩個子索引項組成:基本索引和溢出索引項。

訪問方法

基本的索引順序訪問方法 (BISAM)

在ISAM檔案上檢索記錄時,從主索引出發,找到相應的柱面索引;從柱面索引找到記錄所在柱面的磁軌索引;從磁軌索引找到記錄所在磁軌的起始地址,由此出發在該磁軌上進行順序查找,直到找到為止。若找遍該磁軌均不存在此記錄,則表明該檔案中無此記錄;若被查找的記錄在溢出區,則可從磁軌索引項的溢出索引項中得到溢出鍊表的頭指針,然後對該表進行順序查找。

為了提高檢索效率,通常可讓主索引常駐記憶體,並將柱面索引放在數據檔案所占空間居中位置的柱面上,這樣,從柱面索引查找到磁軌索引時,磁頭移動距離的平均值最小。

佇列順序訪問方法(QSAM)

與 BISAM 類似,QSAM 以記錄進入的順序安排記錄的存放位置,形成一個順序數據集。但與BISAM 不同的是QSAM 由系統組織記錄的成組與分解,也就是說,系統將多個記錄組成塊。為了提高性能,使用佇列順序訪問方法往往在記錄或檔案在使用之前,就已經將記錄或檔案提前讀入記憶體。

相關詞條

熱門詞條

聯絡我們