ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES
BOEING SCIENTIFIC RESEARCH LABS SEATTLE WA MATHEMATICAL AND INFORMATION SCIENCES LAB
Pagination or Media Count:
Organization and maintenance of an index for a dynamic random access file is considered. It is assumed that the index must be kept on some pseudo random access backup store like a disc or a drum. The index organization described allows retrieval, insertion, and deletion of keys in time proportional to LOGKI where I is the size of the index and k is a device dependent natural number such that the performance of the scheme becomes near optimal. Storage utilization is at least 50 but generally much higher. The pages of the index are organized in a special data-structure, so-called B-trees. The scheme is analyzed, performance bounds are obtained, and a near optimal k is computed. Experiments have been performed with indices up to 100,000 keys. An index of size 15,000 100,000 can be maintained with an average of 9 at least 4 transactions per second on an IBM 36044 with a 2311 disc.
- Computer Hardware