作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2013, Vol. 39 ›› Issue (8): 5-8. doi: 10.3969/j.issn.1000-3428.2013.08.002

• 专栏 • 上一篇    下一篇

一种T-树的优化设计与实现方法

吕 鹏1,2,蒋 平1,吴钦章1   

  1. (1. 中国科学院光电技术研究所,成都 610209;2. 中国科学院研究生院,北京 100049)
  • 收稿日期:2012-05-16 出版日期:2013-08-15 发布日期:2013-08-13
  • 作者简介:吕 鹏(1986-),男,博士研究生,主研方向:内存数据库技术,人工智能;蒋 平,副研究员、博士研究生;吴钦章,研究员

An Optimized Design and Implementation Method of T-tree

LV Peng 1,2, JIANG Ping 1, WU Qing-zhang 1   

  1. (1. Institute of Optics and Electronics, Chinese Academy of Sciences, Chengdu 610209, China; 2. China Graduate University of the Chinese Academy of Sciences, Beijing 100049, China)
  • Received:2012-05-16 Online:2013-08-15 Published:2013-08-13

摘要:

在以往的索引结构中,T树索引不具有良好的缓存性能及高效的更新效率,为此,给出一种T-树的优化设计方法。根据缓存结构布局的技术,对T树节点结构进行重新设计,添加前驱和后继指针,增强T树的缓存性能和范围查询能力。在更新溢出处理时,节点之间转移多个数据,减少数据溢出和树失衡的机会,提高T树的更新性能。实验结果表明,该方法在查询以及更新操作上有更好的性能,可节约18%左右的内存空间。

关键词: T树, 索引, 缓存敏感, 内存数据库, 数据安置

Abstract:

As T-tree has not good cache behaviors and update efficiency, this paper gives some optimization design for T-tree. The structure of T-tree’s node is redesigned according to the technology of cache structure and layout, and the precursor and successor pointers are added into the node structure. That can make T-tree more cache conscious and enhances its ability of range query. When there is a data overflow while updating, multiple data items rather than a data item are transferred between nodes. So the chance of data overflows and rebalancing trees can be reduced and the update performance is improved. Experimental results show that the improved T-tree has a better performance in query and updating and can save 18% main memory space.

Key words: T-tree, index, cache conscious, main memory database, data placement

中图分类号: