索引分配
允许文件离散地分配在各磁盘块中,系统会为每一个文件建一张索引表
表中记录了文件的哥哥逻辑块对应的物理快
索引表中存放的磁盘块叫索引块
文件数据存放的磁盘块叫数据块
类似于页表
索引分配方式可以支持随机访问。文件拓展也很容易实现
连接方案
如果索引表太大,一个索引快装不下,可以分多个索引快连接起来存放
索引快是顺序访问的,效率低下
多层索引
建立多层索引(类似于多级页表)使第一次索引快指向第二层索引快
若采用多层索引,各层索引大小不能超过一个磁盘块
如果采用K层索引节后,且顶级索引表未调入内存,则访问一个数据库需要K+1次读磁盘操作
混合索引
采用多种索引分配方式结合,即包含直接地址索引,又包含一级间接索引,还包含二级间接索引
对于小文件来说,只需要较少的读磁盘次数就可以访问目标数据库(一般计算机中小文件更多)
索引分配总结
索引分配允许文件离散地分配在各个磁盘块中,系统会为每个文件建立一张索引表,索引表中记录了文生的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表--建立逻辑页面到物理页之间的映射关系)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。若文件太大,索引表项太多,可以采取以下三种方法解决:I链接方案:如果索引表太大,一个索引块装不下,那么可以将多个索引块链接起来存放。缺点:若文件很大,索引表很长,就需要将很多个索引块链接起来。想要找到i号索引块,必须先依次读入0~i-1号索引块,这就导致磁盘I/0次数过多,查找效率低下。
②)多层索引:建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构,且顶级索引表未调入内存,则访问一个数据块只需要K+1次读磁盘操作。缺点:即使是小文件,访问一个数据块依然需要K+1次读磁盘。
③混合索引:多种索引分配方式的结合。例如,一个文件的顶级索引表中,既包含直接地址索引(直接指向数据块),又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。优点:对于小文件来说,访问一个数据块所需的读磁盘次数更少。
超级超级超级重要考点:①要会根据多层索引、混合索的结构计算出文件的最大长度(Key:各级索引表最大不能超过一个块):②要能自己分析访问某个数据块所需要的读磁盘次数(Key:FCB中会存有指向顶级索引块的指针,因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外,要注意题目条件--顶级索引块是否已调入内存)
