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

吕 鹏，蒋 平，吴钦章

(1.中国科学院光电技术研究所，成都 610209；2.中国科学院研究生院，北京 100049)

1 概述

随着计算机硬件技术的发展，随机记忆存储价格越来越便宜，使得一个数据库的部分甚至全部的表驻留在主存中变成可能[1]。过去十年，内存数据库成为数据库研究的一个热点[2]。作为内存数据库的主要的索引结构，T树索引已经用于FastDB、Oracle、Times Ten等系统中。通过对T树的优化，这些系统可以提高上述系统的性能。文献[3]发现高速缓存对数据库性能有着显著的影响。由于T树被提出时还没有考虑到缓存性能的方面，并不具有良好的缓存性能。本文根据缓存敏感数据放置技术，对T树进行缓存优化。同时，在T树节点结构中增加节点前驱和后继，较好地处理数据更新操作时数据溢出的情况，使得在进行区间查询操作时不需要遍历整个树，从而避免搜索一些无用的数据。在更新的操作中，对数据溢出的情况，将移动多个数据而非一个数据，进而减少数据溢出的情况，提高其性能。

2 T树的优化思路

2.1 T-树索引结构介绍

AVL树是典型的为内存数据设计的树形索引。AVL树是二叉搜索树，拥有左子树和右子树、一些控制信息、以及一个数据项(Pair)。更新操作可能导致树的失衡，此时需要进行旋转操作使树重新保持平衡。因为每个节点只拥有一个数据项，其空间利用率差是AVL树的主要缺点。为解决这个问题，文献[4]提出了T树索引算法。

如图1所示，T树是每个节点拥有多个数据项的AVL树。T树保留了AVL树的二叉搜索性质，并具有良好的更新和存储特性。……