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

摘要：

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

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

CLC Number: 

• TP311