• Article
  • | |
  • Metrics
  • |
  • Reference [1]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    This paper is proposed a new multiattribute index method named hB*-tree on the basis of hB-tree. When an index node overflows, the first step is to avoid splitting if splitting will lead to poor balance degree. Therefore the node utilization of hB*-tree is improved. The DAG problem of hB-tree is also reduced by careful selection of extracted k-d-subtree. If a splitting still produces DAG structure, the hB*-tree is reorganized to be a strict tree. The authors show that hB*-tree has reasonable space utilization and access costs.

    Reference
    1  Lomet D, Salzberg B. The hB-tree: a multiattribute indexing method with good guaranteed performance. ACM Transactions on Database Systems, 1990,15(4):625~658 2  Salzberg B, Lomet D. Spatial database access methods. ACM SIGMOD Record, 1991,20(3):5~15 3  Evangelidis G, Lomet D, Salzberg B. The hB-tree: a modified hB-tree supporting concurrency, recovery and node consolidation. In: Dayal U eds. Proceedings of International Conference on Very Large Data Base. Zürich. Morgan Kaufmann Publishers, 1995. 551~561 4  Guttman A. R-trees: a dynamic index structure for spatial searching. In: Yormark B eds. Proceedings of ACM SIGMOD. Boston, MA: ACM Press, 1984. 47~57 5  Sellis A, Roussopoulos, Faloutsos C. The R+-tree: a dynamic index for multi-dimensional objects. In: Stocker P ed. Proceedings of International Conference on Very Large Data Base. Brighton, England: Morgan Kaufmann Publishers, 1987. 1~24 6  Bechmann N, Kriegel H, Schneider R et al. The R*-tree: an efficient and robust access method for points an rectangles, In: Molina H et al eds. Proceedings of ACM SIGMOD Conference on Management of Data. Atalantic City, NJ: ACM Press, 1990. 322~331 7  Samet H. The quadtree and related hierarchical data structures. ACM Computing Surveys, 1984,16(2):187~260 8  Lin K, Jagadish H V, Faloutsos C. The TV-tree: An index structure for high-dimensional data. VLDB Journal, 1994,3:517~542 9  Robinson J T. The K-D-B-tree: a search structure for large multidimensional dynamic indexes. In: Lien Y eds. Proceedings of ACM SIGMOD Conference on Management of Data. Ann Arbor: ACM Press, 1981. 10~18 10  Berchtold S, Keim D A, Kriegel H. The X-tree: an index structure for high-dimensional data. In: Vijayaraman T et al eds. Proceedings of International Conference on Very Large Data Base. Bombay, India: Morgan Kaufmann Publishers, 1996. 28~39 11  Jin S, Feng Y, Sun X. Improved hB-tree with higher space utilization and eliminating DAG. In: Shoval P et al eds. Proceedings of International Workshop on Next-Generation Information Technologies and Systems. Israel, 1997. 162~171
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

金树东,冯玉才,孙小薇.多维索引hB树的改进方法——hB*树.软件学报,1998,9(3):206-212

Copy
Share
Article Metrics
  • Abstract:4407
  • PDF: 4693
  • HTML: 0
  • Cited by: 0
History
  • Received:December 17,1996
  • Revised:April 28,1997
You are the first2045191Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063