The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance.

David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990)

@article{DBLP:journals/tods/LometS90,
  author    = {David B. Lomet and
               Betty Salzberg},
  title     = {The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed
               Performance},
  journal   = {ACM Trans. Database Syst.},
  volume    = {15},
  number    = {4},
  year      = {1990},
  pages     = {625-658},
  ee        = {http://doi.acm.org/10.1145/99935.99949, db/journals/tods/LometS90.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

A new multiattribute index structure called the hB-tree is introduced. It is derived from the K-D-B- tree of Robinson [15] but has additional desirable properties. The hB-tree internode search and growth processes are precisely analogous to the corresponding processes in B-trees [1]. The intranode processes are unique. A k-d tree is used as the structure within nodes for very efficient searching. Node splitting requires that this k-d tree be split. This produces nodes which no longer represent brick-like regions in k-space, but that can be characterized as holey bricks, bricks in which subregions have been extracted. We present results that guarantee hB-tree users decent storage utilization, reasonable size index terms, and good search and insert performance. These results guarantee that the hB-tree copes well with arbitrary distributions of keys.

Copyright © 1990 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

References

[1]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[2]: Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
[3]: Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979) BibTeX
[4]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[5]: Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX
[6]: Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
[7]: Witold Litwin, David B. Lomet: A New Method for Fast Data Searches with Keys. IEEE Software 4(2): 16-24(1987) BibTeX
[8]: David B. Lomet: Digital B-Trees. VLDB 1981: 333-344 BibTeX
[9]: ...
[10]: David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987) BibTeX
[11]: David B. Lomet: A Simple Bounded Disorder File Organization with Good Performance. ACM Trans. Database Syst. 13(4): 525-551(1988) BibTeX
[12]: Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
[13]: ...
[14]: Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 BibTeX
[15]: John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
[16]: Yehoshua Sagiv: Concurrent Operations on B-Trees with Overtaking. PODS 1985: 28-37 BibTeX
[17]: ...
[18]: ...
[19]: Betty Salzberg: Grid File Concurrency. Inf. Syst. 11(3): 235-244(1986) BibTeX

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]