Robust search methods for B-trees

The authors propose search methods for B-trees that correctly perform the search despite the presence of corrupted indices. If in a search the desired record with a given key is not found, the robust search methods determine if this is caused by a corrupted index. The corrupted index is then detected and corrected so that the value of the index is in a right range. The authors first present a method to handle a single error in the tree and then generalize the method to cope with multiple errors. Unlike the previous attempts for robust data structures, their methods do not require redundancy to be added to the data structure and make use of the constraints by which the indices are organized.<>