1操作系统研讨.ppt

操作系统第三次研讨操作系统第三次研讨第一题第一题研讨题目研讨题目 1.若一个逻辑顺序文件中记录数为n。试从检索速度（平均查找次数）、存储费用和适用场合方面比较顺序文件、索引文件、索引顺序文件和两级索引文件。并要求说明索引顺序文件的平均查找次数。文件逻辑结构类型文件逻辑结构类型p有结构文件有结构文件又名记录式文件是由若干个记录组成，每个记录有一个键，可又名记录式文件是由若干个记录组成，每个记录有一个键，可按键（关键字）进行查找。按键（关键字）进行查找。记录可以是定长或变长。记录可以是定长或变长。 按组织方式：u顺序文件u索引文件u索引顺序文件顺序文件顺序文件p特点特点u适用于记录的批量存取适用于记录的批量存取u顺序查找文件记录，开销大顺序查找文件记录，开销大u增加或修改记录困难增加或修改记录困难p存取方法存取方法顺序存取顺序存取：按记录顺序依次存取。即为了存取：按记录顺序依次存取。即为了存取RiRi记录，必须首记录，必须首先存放先存放R0Ri-1R0Ri-1记录。记录。直接存取直接存取：视为：视为随机存取随机存取，根据给定记录能直接定位到文件中，根据给定记录能直接定位到文件中任一记录，而无需存取其前面的记录。任一记录，而无需存取其前面的记录。如如定长记录定长记录文件，既可采用文件，既可采用顺序存取顺序存取也可也可直接存取直接存取。直接存取时可根据给定的记录序号直接存取时可根据给定的记录序号i i，直接求出第，直接求出第i i个记录的首个记录的首地址：即地址：即Ai=iAi=i* *l l可可变长记录变长记录，难以实现直接存取难以实现直接存取，为提高其直接存取效率，采，为提高其直接存取效率，采用索引表的组织。用索引表的组织。顺序文件顺序文件 设主文件有N条记录 定长：顺序或随机存取 变长：顺序存取 平均查找次数=N/2 存储费用=N 适用场合 对诸记录进行批量存取时（每次要读或写一大批记录时）顺序文件顺序文件p特点特点u适用于记录的批量存取适用于记录的批量存取u顺序查找文件记录，开销大顺序查找文件记录，开销大u增加或修改记录困难增加或修改记录困难索引文件索引文件p 索引文件索引文件 设主文件有N条记录 增加了存储的代价 （定长）顺序或随机存储 平均查找次数（设主文件有N条记录）=N/2 存储费用=N 适用场合 对诸记录进行批量存取时（每次要读或写一大批记录时）索引文件索引文件p 索引组织索引组织p 检索效率比较：若顺序文件中记录数为N个，那么采用顺序检查法检索指定关键字的记录： 顺序文件：平均查找N/2个记录 索引顺序文件（每 一组）：只需查找索引顺序文件索引顺序文件p 将顺序文件中的所有记录按关键字分为若干个组，同时为顺序将顺序文件中的所有记录按关键字分为若干个组，同时为顺序 文件建立一张索引表。索引表中为每个记录组中的第一记录建文件建立一张索引表。索引表中为每个记录组中的第一记录建 立索引项，包含记录的键值和指向该记录的指针。立索引项，包含记录的键值和指向该记录的指针。 nn索引顺序文件索引顺序文件索引顺序文件索引顺序文件nn平均查找次数（设主文件有N条记录）=存储费用=适用场合：解决索引文件的存储代价克服变长记录文件不便于直接存取的缺点两级索引的索引顺序文件两级索引的索引顺序文件存在问题：文件记录过大时，找到相应记录需平均查找记录数目仍然很多存在问题：文件记录过大时，找到相应记录需平均查找记录数目仍然很多含有含有10106 6个记录的顺序文件，其检索效率：个记录的顺序文件，其检索效率：顺序文件：平均查找顺序文件：平均查找5 510105 5个记录个记录索引顺序文件：平均查找索引顺序文件：平均查找10001000个记录个记录( (每每10001000个一组）个一组）解决问题：采用两级索引的索引顺序文件，以每解决问题：采用两级索引的索引顺序文件，以每100100个记录一组为例：个记录一组为例：10项102项平均查找505050个记录2两级索引的索引顺序文件两级索引的索引顺序文件两级索引的索引顺序文件两级索引的索引顺序文件两级索引的索引顺序文件两级索引的索引顺序文件 设主文件有N条记录 平均查找次数= 存储费用（设主文件有N条记录）=3 适用场合 OS为一个大文件分配磁盘空间时