1操作系统研讨.ppt

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