时间：2022-11-05 06:30:01 | 来源：信息时代
时间：2022-11-05 06:30:01 来源：信息时代
内存索引 : 有利于内存数据库(MMDB)存取的索引结构,如AVL-树等。但随着计算机处理机技术的快速发展,CPU运算速度的增长要远远高于内存速度的增长,于是造成内存存取成为新的瓶颈。为此,在内存和CPU之间加装一个容量较小的SRAM作为高速缓冲存储器(cache),由于Cache中保存着内存中最常使用的数据和指令,因此可以有效减少CPU的等待时间。Cache命中率越高,CPU的运算效率就越高。因为Cache命中率对MMDB的索引结构的性能影响非常大,因此一些新的基于Cache敏感性的MMDB索引结构被提出,如CSS-树等。
1.AVL-树
1962年,由G.M.Adel`son、Vel`skii和E.M.Landis共同提出了一种高度平衡的树(height-balanced tree),这种树以他们的名字命名,被称之为AVL-树,或者也被称之为平衡二叉树(balanced binary tree)。AVL-树是具有下列性质的二叉排序树(binary sort tree):①若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;②若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;③它的左、右子树也分别为二叉排序树; ④它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。
(1) AVL-树的查找操作: 首先将给定的值和根结点的键值比较,若相等,则查找成功,否则将依据给定值和根结点的键值之间的大小关系,分别在左子树或右子树上继续进行查找。如果小于根结点的键值,就在左子树上查找; 如果大于根结点的键值,就在右子树上查找。
(2) AVL-树的插入操作: 若二叉树为空,则插入结点应成为新的根结点,否则继续在其左子树或右子树上查找,直至某个叶子结点的左子树或右子树为空为止,则插入结点应作为一个新的叶结点并成为该结点的左孩子或右孩子。为了使二叉排序树成为平衡树,需要做以下工作: ①判别插入结点之后是否产生不平衡; ②找到失去平衡的最小子树;③判别旋转类型并作相应调整处理,使二叉排序树由不平衡转化为平衡。
一般情况下,假设由于在二叉排序树上插入结点而失去平衡的最小子树的根结点指针为a(即a是离插入结点最近,且平衡因子绝对值超过1的祖先结点),则失去平衡后进行调整的规律可归纳为下列四种情况:①LL型平衡旋转: 由于在A的左子树的左子树上插入结点,使A的bf由1增至2而失去平衡,需进行一次顺时针旋转操作;②RR型平衡旋转:由于在A的右子树的右子树上插入结点,使A的bf由-1减至-2而失去平衡,需进行一次逆时针旋转操作;③LR型平衡旋转:由于在A的左子树的右子树上插入结点,使A的bf由1增至2而失去平衡,需进行两次旋转操作(先逆时针,后顺时针); ④RL型平衡旋转: 由于在A的右子树的左子树上插入结点,使A的bf由-1减至-2而失去平衡,需进行两次旋转操作(先顺时针,后逆时针)。
2.CSS-树
CSS-树(cache sensitive search tree)是由美国哥伦比亚大学的Jun Rao和Kenneth A.Ross在1999年第25届VLDB会议上提出的,因其查找的性能比B+-树和T-树都要好很多而受到关注。CSS-树就是为了实现快速查找而设计的一种压缩的索引结构。CSS-树与B+-树相似,但与B+-树不同的是,CSS-树去掉了指向孩子结点的指针,将孩子结点保存在大小固定的数组里,结点被编号,从左到右分层保存。如图1所示,结点0有5个孩子结点1～5,这5个孩子结点存放在一个数组中,结点0有两个指针指向这个数组的头部和尾部。CSS-树的查找也与B+-树相似,不同的是孩子结点的位置是通过计算得出,而不是通过指针重定向得出。
图1 CSS-树的逻辑结构
在线咨询
