The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes

The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes

1981 | John T. Robinson
The paper introduces the K-D-B-tree, a new data structure designed to efficiently handle large, dynamic multidimensional indexes. The K-D-B-tree combines the properties of K-D-trees and B-trees, aiming to achieve both balanced search efficiency and I/O efficiency. The structure is defined with region and point pages, and it supports range queries, insertions, and deletions. The paper outlines the algorithms for these operations and discusses reorganization techniques to improve storage utilization. Preliminary experimental results show that the K-D-B-tree can achieve around 60% storage utilization and good query efficiency for full range queries. The authors conclude that the K-D-B-tree is an efficient solution for large multidimensional dynamic indexes, especially for $K=2,3$, but further research is needed on reorganization and point distributions.The paper introduces the K-D-B-tree, a new data structure designed to efficiently handle large, dynamic multidimensional indexes. The K-D-B-tree combines the properties of K-D-trees and B-trees, aiming to achieve both balanced search efficiency and I/O efficiency. The structure is defined with region and point pages, and it supports range queries, insertions, and deletions. The paper outlines the algorithms for these operations and discusses reorganization techniques to improve storage utilization. Preliminary experimental results show that the K-D-B-tree can achieve around 60% storage utilization and good query efficiency for full range queries. The authors conclude that the K-D-B-tree is an efficient solution for large multidimensional dynamic indexes, especially for $K=2,3$, but further research is needed on reorganization and point distributions.
Reach us at info@study.space
Understanding The K-D-B-tree%3A a search structure for large multidimensional dynamic indexes