Indexed sequential search

Another technique to improve search efficiency for a sorted file is indexed sequential search. But it involves an increase in the amount of memory space required. An auxiliary table called an index, is set aside in addition to a sorted file. Each element in the index table consists of a key Kindex and pointer to the record in the field that corresponds to the kindex. The elements in the index, as well as elements in the file, must be sorted on the file.

The algorithm used for searching an indexed sequential file is simple and straight. Let r, k and key be defined as before. Let kindex be an array of the keys in the index, and let pindex be the array of pointers within the index to the actual records in the file, and the size of index is also taken in a variable. The indexed sequential search can be explained as the following example in the figure.

The advantage of the indexed sequential method is that items in the table can be examined sequentially if all records in the file have to be accessed, yet the search time for particular items is reduced. A sequential search is performed on the smaller index rather than on the large table. Once the index position is found, the search is made on the record table itself.

Deletion from an indexed sequential table can be most easily by flagging deleted entries. When sequential searching is done deleted items are ignored. The item is deleted from the original table.

Insertion into an indexed sequential table may be difficult as there may not be any place between two table entries which may lead to a shift to a large number of elements.

However, the deleted items can be overwritten.