索引文件 顺序文件的査询速度很慢。采用索引文件可以提高检索效率。实际上,在前面的章节中我们已经运用了索引技术。 索引用来表示关键字与相应记录的存储地址之间的对应关系。换言之,索引指出了记录在存储器中的存储地址 设记录R的关键字为K;,R在外存中的存储地址为A,则(K,A)称为记录R的索引项。索引表(简称索引 是索引项的集合。如果文件中的每个记录都有一个索引项,则这样的索引称为稠密索引。如果多个记录只有 索引项,则这样的索引称为非稠密索引。带有索引的文件称为索引文件。索引也称为目录, 索引文件在外存(磁盘、磁鼓等)中可分为两个存储区:索引区和记录区(数据区)。索引表中的索引项顺序存 放到记录区;记录区按关键字大小次序排列的索引文件称为索引顺序文件。对于索引顺序文件,可以不必使 用稠密索引,只为一个记录块(含多个有序记录)建立一个索引项。记录区不按关键字大小次序排列的索引 文件称为索引非顺序文件,这时应使用稠密索引。图10-2所示的个人书库(价格)索引文件,是一个索引非 顺序文件。 通常,索引项所含的数据信息比记录少得多,因而索引所需的存储空间比文件本身(记录区)所需要的存储空 间少得多。在文件的记录数较少的情况下,可以为每个记录建立一个索引项。文件建立时,开辟一个索引区 般固定在某个磁盘面的一个或多个磁道上。写入一个记录到记录区时,在索引区相应登入一个索引项,即 的缓冲,接关键走行丙部排序。最后将排序好的索分项序写回到磁盘上的素 将索引区中的索引读入内 根据关键字查找索引文件的记录分两步进行。第1步,访问外存的索引区,将索引读入内存缓冲区,使用顺序查 找或折半查找法找出所查记录在外存数据区中的地址,这一过程称为预查找。第2步,如果在预查中已找到了 所查记录的地址,则第2次访问外存,根据已查到的地址,读取所查的记录 删除一个记录时,只需删去相应的索引项,而不必移动数据区中的记录。插入一个新记录时,将记录放到记录 区的末尾,在索引区登记相应的索引项,并对索引区中的索引项重新排序索引文件 顺序文件的查询速度很慢。采用索引文件可以提高检索效率。实际上，在前面的章节中我们已经运用了索引技术。 索引用来表示关键字与相应记录的存储地址之间的对应关系。换言之，索引指出了记录在存储器中的存储地址。 设记录Ri的关键字为Ki，Ri在外存中的存储地址为Ai，则（Ki，Ai）称为记录Ri的索引项。索引表（简称索引） 是索引项的集合。如果文件中的每个记录都有一个索引项，则这样的索引称为稠密索引。如果多个记录只有 一个索引项，则这样的索引称为非稠密索引。带有索引的文件称为索引文件。索引也称为目录。 索引文件在外存（磁盘、磁鼓等）中可分为两个存储区：索引区和记录区（数据区）。索引表中的索引项顺序存 放在索引区中，但为了便于检索，索引项一般按关键字的大小次序排列。文件中的记录按输入的先后次序存 放到记录区；记录区按关键字大小次序排列的索引文件称为索引顺序文件。对于索引顺序文件，可以不必使 用稠密索引，只为一个记录块（含多个有序记录）建立一个索引项。记录区不按关键字大小次序排列的索引 文件称为索引非顺序文件，这时应使用稠密索引。图10-2所示的个人书库（价格）索引文件，是一个索引非 顺序文件。 通常，索引项所含的数据信息比记录少得多，因而索引所需的存储空间比文件本身（记录区）所需要的存储空 间少得多。在文件的记录数较少的情况下，可以为每个记录建立一个索引项。文件建立时，开辟一个索引区， 一般固定在某个磁盘面的一个或多个磁道上。写入一个记录到记录区时，在索引区相应登入一个索引项，即 把该记录的关键字（主关键字）和记录的存储地址顺序写入索引区。文件建立后，将索引区中的索引读入内 存的缓冲区，按关键字进行内部排序。最后将排序好的索引项顺序写回到磁盘上的索引区。 根据关键字查找索引文件的记录分两步进行。第1步，访问外存的索引区，将索引读入内存缓冲区，使用顺序查 找或折半查找法找出所查记录在外存数据区中的地址，这一过程称为预查找。第2步，如果在预查中已找到了 所查记录的地址，则第2次访问外存，根据已查到的地址，读取所查的记录。 删除一个记录时，只需删去相应的索引项，而不必移动数据区中的记录。插入一个新记录时，将记录放到记录 区的末尾，在索引区登记相应的索引项，并对索引区中的索引项重新排序