The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes.
Abstract
The problem of retrieving multikey records via range queries from a large, dynamic index is considered. By 'large' it is meant that most of the index must be stored on secondary memory. By 'dynamic' it is meant that insertions and deletions are intermixed with queries, so that the index cannot be built beforehand. A new data structure, the K-D-B-tree, is presented as a solution to this problem. K-D-B-trees combine properties of K-D-trees and B-trees. It is expected that the multidimensional search efficiency of balanced K-D-trees and the I/O efficiency of B-trees should both be approximated in the K-D-B-tree. Preliminary experimental results that tend to support this are reported. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1981
- Accession Number
- ADA106550
Entities
People
- John T. Robinson
Organizations
- Carnegie Mellon University