Browse Prior Art Database

Fault Tolerant Binary Search for Indexed Sequential Files

IP.com Disclosure Number: IPCOM000049941D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 3 page(s) / 37K

Publishing Venue

IBM

Related People

Black, AL: AUTHOR [+2]

Abstract

A search method is required for indexed sequential data sets with variable length records. Since the records are not fixed length, they require a directory to allow quick random access of a particular variable length record. The obvious choice would be a directory with one entry for every N records, where N is some fixed value. To randomly access a record under this scheme is straightforward (divide the record ordinal by N and use the directory to start a short linear search of average length N/2). In some applications, the number of data records per directory entry cannot be a fixed number. Thus, a more complex search mechanism for random access is required. A binary search is used to access entries in this directory.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Fault Tolerant Binary Search for Indexed Sequential Files

A search method is required for indexed sequential data sets with variable length records. Since the records are not fixed length, they require a directory to allow quick random access of a particular variable length record. The obvious choice would be a directory with one entry for every N records, where N is some fixed value. To randomly access a record under this scheme is straightforward (divide the record ordinal by N and use the directory to start a short linear search of average length N/2). In some applications, the number of data records per directory entry cannot be a fixed number. Thus, a more complex search mechanism for random access is required. A binary search is used to access entries in this directory. While the directory and the binary search still allow rapid random access, reliability could be affected if portions of the directory become damaged.

The present search method is operable even when there is damage to the directory with no significant impact on access time for nondamage cases. It provides a general binary search algorithm for fast table lookup and is completely conventional until damage is detected. It allows the binary search to continue even after damage is encountered and allows the entire directory to be damaged. It will also bypass damage in the data set itself in many cases due to tolerance of partially damaged directories.

The organization of the data is set forth in Fig. 1. Assume that an indexed sequential data set has a directory which points, for example, to every 10Oth record. (As noted before, this every 100 entry property cannot be counted on.) To randomly access a record it is only necessary to find the nearest predecessor entry in the directory and go forward from there. To speed the search, a binary search of the directory is used. However, what happens if the directory is unreadable from the disk or is detected to be otherwise damaged?

The solution is to bias the result of the binary search. If the current entry turns out to be damaged, assume that the compare result would have been "search record value less than directory entry value." By forcing the "compare" in this manner, the worst possible result is that a starting record prior to the one normally used will be used to search the file for the particular record. As will be shown, this will provide, in virtually all cases, the closest directory entry which is undamaged. More entries may (or may not) be accessed to get to the desired record, but the search can still be performed.

The record search algorithm is set forth i...