Indexing method and apparatus facilitating a binary search of digital

Abstract

An ordered index file is created for archived report data wherein each index file contains a series of 4-byte offsets into the report data. Each offset points to a field within a row of the report data from archival storage. Upon later retrieval from the report data, a binary search is performed for a key(s) that is contained in a search query, using the index field offsets to determine the order in which to retrieve the report data fields. The binary search resolves each key in the search query to a range of index offsets corresponding to report rows that match the query. The search technique optimize final filtering of matches by using the search query that matched the smallest range as the controlling field for resolving overlap of fields in the search query. Since all of the offsets refer to the same report file, this optimization operation compares the offsets of the fields, rather than comparing the field values themselves. A range check is performed before the binary search to determine whether the search key is outside the range of keys that are in the ordered index files, thereby preventing unnecessary searching of indexes that cannot contain the search key(s).