T-reap理论，又称平衡二叉树（Balanced Binary Tree）或平衡树理论。T-reap是一种具有二叉搜索树和堆合并构成的新型数据结构。之所以称其为“平衡树”，是因为它的名字取了Tree和Heap各一半。作为一种新型的数据结构，T-reap具有特殊的性质：①一棵树与它所属子树的高度差的绝对值不超过1；②左右两个子树都是一棵平衡二叉树；③堆和树的性质是冲突的；④二叉搜索树满足左子树＜根节点＜右子树。因此，在平衡二叉树数据结构中，并不是以单一的键值作为节点的数据域，每个节点的数据域包含2个值A和B。在T-reap中，A值和原来的二叉搜索树一样，满足左子树＜根节点＜右子树，B值满足堆的性质，根节点的B值小于等于（或大于等于）左右节点B1、B2。
图1 平衡二叉树示意图(www.xing528.com)
在实际过程中，我们可以形象地把一个数据库比作一棵枝繁叶茂的大树，如果对一棵“数据树”进行查询、搜索等操作，所花的时间与数据库的大小（即树的高度）成正比。基于这样的思考，我们就可以从两个角度开展工作，以提高检索效率，其一是，改造数据库的结构，让它更便于检索，形象地说就是“修剪树”，让树维持矮矮胖胖的好身材，也就可以实现缩短检索周期的目的；其二是，创新索引算法，目的是以较短的时间完成上述工作，总体也能节省较多的时间和精力，本文以“T-reap”理论为立足点，力求对此问题有所突破。关于T-reap检索的性能，可以说如果一次检索需要访问4个节点（这里的节点也相当于树的枝杈），数据库系统设计者利用磁盘预读原理，把节点的大小设计为一个页，那读取一个节点只需要一次I/O操作，完成这次检索操作，最多需要3次I/O操作。T-reap的优点在于其节点只存key，大大地减少了节点的数量，那么每个节点就可以存放更多的记录，“数据树的更矮了”，I/O操作自然就会相应减少。由于数据记录越小，每个节点存放的数据就越多，树的高度也就越小，I/O操作就少了，检索效率自然而然就高了，因此，T-reap也就拥有了更好的性能。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
