內(nèi)存索引(數(shù)據(jù)庫)

時間：2022-11-05 06:30:01 | 來源：信息時代

時間：2022-11-05 06:30:01 來源：信息時代

    內(nèi)存索引 : 有利于內(nèi)存數(shù)據(jù)庫(MMDB)存取的索引結構,如AVL-樹等。但隨著計算機處理機技術的快速發(fā)展,CPU運算速度的增長要遠遠高于內(nèi)存速度的增長,于是造成內(nèi)存存取成為新的瓶頸。為此,在內(nèi)存和CPU之間加裝一個容量較小的SRAM作為高速緩沖存儲器(cache),由于Cache中保存著內(nèi)存中最常使用的數(shù)據(jù)和指令,因此可以有效減少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-樹的查找操作: 首先將給定的值和根結點的鍵值比較,若相等,則查找成功,否則將依據(jù)給定值和根結點的鍵值之間的大小關系,分別在左子樹或右子樹上繼續(xù)進行查找。如果小于根結點的鍵值,就在左子樹上查找; 如果大于根結點的鍵值,就在右子樹上查找。
(2) AVL-樹的插入操作: 若二叉樹為空,則插入結點應成為新的根結點,否則繼續(xù)在其左子樹或右子樹上查找,直至某個葉子結點的左子樹或右子樹為空為止,則插入結點應作為一個新的葉結點并成為該結點的左孩子或右孩子。為了使二叉排序樹成為平衡樹,需要做以下工作: ①判別插入結點之后是否產(chǎn)生不平衡; ②找到失去平衡的最小子樹;③判別旋轉類型并作相應調整處理,使二叉排序樹由不平衡轉化為平衡。
一般情況下,假設由于在二叉排序樹上插入結點而失去平衡的最小子樹的根結點指針為a(即a是離插入結點最近,且平衡因子絕對值超過1的祖先結點),則失去平衡后進行調整的規(guī)律可歸納為下列四種情況:①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-樹就是為了實現(xiàn)快速查找而設計的一種壓縮的索引結構。CSS-樹與B⁺-樹相似,但與B⁺-樹不同的是,CSS-樹去掉了指向孩子結點的指針,將孩子結點保存在大小固定的數(shù)組里,結點被編號,從左到右分層保存。如圖1所示,結點0有5個孩子結點1～5,這5個孩子結點存放在一個數(shù)組中,結點0有兩個指針指向這個數(shù)組的頭部和尾部。CSS-樹的查找也與B⁺-樹相似,不同的是孩子結點的位置是通過計算得出,而不是通過指針重定向得出。

圖1 CSS-樹的邏輯結構