文件 - 索引文件（二）

　　索引文件的操作

　　檢索操作

　　檢索分兩步進行

　　① 將外存上含有索引區的頁塊送人內存查找所需記錄的物理地址

　　② 將含有該記錄的頁塊送人內存

　　注意

　　①索引表不大時索引表可一次讀入內存在索引文件中檢索只需兩次訪問外存一次讀索引一次讀記錄

　　②由於索引表有序對索引表的查找可用順序查找或二分查找等方法

　　更新操作

　　() 插入

　　將插入記錄置於數據區的末尾並在索引表中插入索引項;

　　() 刪除

　　刪去相應的索引項;

　　注意

　　修改主關鍵字時要同時修改索引表

　　利用查找表建立多級索引

　　查找表

　　對索引表建立的索引稱為查找表查找表的建立可以為占據多個頁塊的索引表的查閱減少外存訪問次數

　　【例】表的索引表占用了三個頁塊的外存每個頁塊能容納三個索引項則可為之建立一個查找表在查找表中列出索引表的

　　每一頁塊最後一個索引項中的關鍵字(該塊中最大的關鍵字)及該塊的地址如表所示檢索記錄時先查找查找表再查索引表

　　然後讀取記錄三次訪問外存即可

　　

　　多級索引

　　當查找表中項目仍很多可建立更高一級的索引通常最高可達四級索引

　　數據文件一索引表一查找表一第二查找表一第三查找表

　　【例】檢索過程從最高一級索引第三查找表開始需要次訪問外存

　　注意

　　① 多級索引是一種靜態索引

　　② 多級索引的各級索引均為順序表結構簡單修改很不方便每次修改都要重組索引

　　 動態索引

　　當數據文件在使用過程中記錄變動較多時利用二叉排序樹(或AVL樹)B_樹(或其變型)等樹表結構建立的索引為動態索引

　　()樹表特點

　　① 插入刪除方便

　　② 本身是層次結構無須建立多級索引

　　③ 建立索引表的過程即為排序過程

　　()樹表結構選擇

　　① 當數據文件的記錄數不很多內存容量足以容納整個索引表時可采用二叉排序樹(或AVL樹)作索引;

　　② 當文件很大時索引表(樹表)本身也在外存查找索引時訪問外存的次數恰為查找路徑上的結點數采用m階B樹(或其變

　　型)作為索引表為宜(m的選擇取決於索引項的多少和緩沖區的大小)

　　() 外存的索引表的查找性能評價

　　由於訪問外存的時間比內存中查找的時間大得多所以外存的索引表的查找性能主要著眼於訪問外存的次數即索引表的深度

From:http://tw.wingwit.com/Article/program/sjjg/201311/23618.html