多维索引hB树的改进方法——hB*
作者:

The hB*-Tree——an Improved Multidimensional Indexing Method of hB-Tree
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [1]
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    本文在hB树基础上提出多属性索引方法——hB*树.hB*树索引结点溢出时先寻求避免分裂,以期得到较好的空间利用率;通过避免和消除多父结点,使hB*树成为严格的树形结构.本文表明hB*树提高了空间利用率,树形化的代价也不高.

    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.

    参考文献
    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
    相似文献
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:4397
  • 下载次数: 4621
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:1996-12-17
  • 最后修改日期:1997-04-28
文章二维码
您是第19795585位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号