|
索引文件的操作 检索操作 检索分两步进行 ① 将外存上含有索引区的页块送人内存查找所需记录的物理地址 ② 将含有该记录的页块送人内存 注意 ①索引表不大时索引表可一次读入内存在索引文件中检索只需两次访问外存一次读索引一次读记录 ②由于索引表有序对索引表的查找可用顺序查找或二分查找等方法 更新操作 () 插入 将插入记录置于数据区的末尾并在索引表中插入索引项; () 删除 删去相应的索引项; 注意 修改主关键字时要同时修改索引表 利用查找表建立多级索引 查找表 对索引表建立的索引称为查找表查找表的建立可以为占据多个页块的索引表的查阅减少外存访问次数 【例】表的索引表占用了三个页块的外存每个页块能容纳三个索引项则可为之建立一个查找表在查找表中列出索引表的 每一页块最后一个索引项中的关键字(该块中最大的关键字)及该块的地址如表所示检索记录时先查找查找表再查索引表 然后读取记录三次访问外存即可 多级索引 当查找表中项目仍很多可建立更高一级的索引通常最高可达四级索引 数据文件一索引表一查找表一第二查找表一第三查找表 【例】检索过程从最高一级索引第三查找表开始需要次访问外存 注意 ① 多级索引是一种静态索引 ② 多级索引的各级索引均为顺序表结构简单修改很不方便每次修改都要重组索引 动态索引 当数据文件在使用过程中记录变动较多时利用二叉排序树(或AVL树)B_树(或其变型)等树表结构建立的索引为动态索引 ()树表特点 ① 插入删除方便 ② 本身是层次结构无须建立多级索引 ③ 建立索引表的过程即为排序过程 ()树表结构选择 ① 当数据文件的记录数不很多内存容量足以容纳整个索引表时可采用二叉排序树(或AVL树)作索引; ② 当文件很大时索引表(树表)本身也在外存查找索引时访问外存的次数恰为查找路径上的结点数采用m阶B树(或其变 型)作为索引表为宜(m的选择取决于索引项的多少和缓沖区的大小) () 外存的索引表的查找性能评价 由于访问外存的时间比内存中查找的时间大得多所以外存的索引表的查找性能主要着眼于访问外存的次数即索引表的深度 |
