几种典型树形索引技术对比分析

在以大型数据库为中心的计算机应用系统中,通过索引技术建立起数据的物理位置到逻辑位置的关联,可以提高检索、插入、删除记录的效率。文章通过介绍2-3树、B树和B+树三种典型树索引技术,评价其特点,为我们现实工作提供理论支持。

红黑树的高度

先证明高度是h的准红黑树至少有2「2h﹁+2﹂2h」-2个结点.再证明有n个结点的准红黑树的高度至多是2﹂log2(n+2)」+﹂log2(n+2lo)g-23﹂l-o1g2(n+2)」」-2.最后证明有n个结点的红黑树的高度至多是2﹂log2(n+2)」+﹂log2(n+2lo)g-23﹂l-og12(n+2)」」-2,该式比原来的2﹂log2(n+1)」+1准确.有n个结点的红黑树的高度在﹂log2(n+1)」和2﹂log2(n+2)」+﹂log2(n+2lo)g-23﹂l-og12(n+2)」」-2之间.此文进一步完善了红黑树的性质.