Modification of a multilevel indexed descriptor file

摘要

Multilevel indexed descriptor files have many advantages, such as fast retrieval of exact-, partial- and/or approximate-matches, easy file organization and record insertion, and little storage requirement for indexes. They, however, have a potential problem that a file search may need backtracking, i.e. the examination of more than one block at some level, even for retrieving exact-matches. This paper discusses a method of modifying the existing file structure so as to cope with this problem. The proposed modification algorithm copies the records requiring backtracking into new blocks from which each of them can be retrieved by examining only one block at any level. Also the copy operation does not involve additional costs for records not requiring backtracking. Computational experiments obtained from various generated and real-world data show that the algorithm can be implemented easily and work effectively.