內(nèi)存數(shù)據(jù)庫索引結(jié)構(gòu)(數(shù)據(jù)庫)

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

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

    內(nèi)存數(shù)據(jù)庫索引結(jié)構(gòu) : 內(nèi)存數(shù)據(jù)庫索引結(jié)構(gòu)是為具有特定屬性值的MMDB數(shù)據(jù)提供指針,以實現(xiàn)快速存取的一種專門數(shù)據(jù)結(jié)構(gòu)。內(nèi)存數(shù)據(jù)庫索引的概念與DRDB完全一樣,所以原則上一般索引結(jié)構(gòu)也可用于MMDB。但由于對內(nèi)存數(shù)據(jù)庫而言,“時-空”這對矛盾的地位正好對調(diào),因此各種索引結(jié)構(gòu)在內(nèi)存數(shù)據(jù)庫中表現(xiàn)出與原來不同的特征。另外還開發(fā)出了許多適合內(nèi)存數(shù)據(jù)庫的專門索引結(jié)構(gòu)。
1. 一般內(nèi)存索引
適用于MMDB的索引結(jié)構(gòu)可分為兩大類: 一是數(shù)據(jù)保持某種自然排序,如各種樹結(jié)構(gòu); 另一類是數(shù)據(jù)隨機分布,如各種Hash索引結(jié)構(gòu)。常用的內(nèi)存數(shù)據(jù)庫索引結(jié)構(gòu)有:
(1)數(shù)組: 在IBM的內(nèi)存數(shù)據(jù)庫系統(tǒng)OBE中,采用數(shù)組作索引結(jié)構(gòu)。它使用的空間最小,但每一維護操作所引起的數(shù)據(jù)移動量是O(N)級的(N為數(shù)組元素個數(shù))。其代價太高,除只讀(read-only)環(huán)境外,幾乎沒有什么實用性。
(2) AVL樹: AT&T BeLL實驗室的“硅數(shù)據(jù)庫機”(silicon database machine)中用它作內(nèi)存索引結(jié)構(gòu)。它的操作時間復雜度為O(Log₂N)(N為記錄數(shù)),因此具有較高的存取性能。但每個結(jié)點只有一個數(shù)據(jù)元素,卻有兩個指針和有關(guān)控制信息,其內(nèi)存的有效利用率很低。
(3) B-樹: 操作性能好,且能動態(tài)維護。但它的內(nèi)存有效利用率很低,因為①結(jié)點空間的平均占用率約66%,且其階K越大,雖然操作性能越好,但每一結(jié)點的絕對未用空間就越大; ②任一結(jié)點中若有m個數(shù)據(jù)元素(索引碼),則有(m+1)+m個(對于內(nèi)結(jié)點)或0+m個(對于葉結(jié)點)指針(后一個m是指向數(shù)據(jù)記錄的指針數(shù)),指針占用空間的比例太多。
(4) B⁺-樹: 在內(nèi)存情況下,B⁺-樹不具有比B-樹更大的優(yōu)越性。
2. SB-樹索引結(jié)構(gòu)
兼有AVL樹和B-樹的主要特征,是一種滿足下列條件的樹結(jié)構(gòu)(D,E),其中D為其結(jié)點集,E為邊集:
(1) D中存在唯一的稱為根的結(jié)點r,無父輩。
(2) D={r}∪D_L^r∪D_R^r, D_L^r∩D_R^r＝∅; 且存在唯-X_R^r∈D_L^r,X_L^r∈D_L^r,使得E={<r,X_L^r>,<r,X_R^r>,E_L^r,E_R^r}。
(3)(D_L^r,E_L^r),(D_R^r,E_R^r)是符合本定義的SB-樹,分別稱為根r的以X_L^r和X_R^r為根的左子樹和右子樹,且它們是平衡的,即|h_L^r-h_R^r|≤1(h_L^r和h_R^r分別為左、右子樹的高度)。
(4)結(jié)點N的形式為(bf,lc,rc,lp,rp;e₀,e₁,…,e_n,…,e_2n)(見圖1),其中:①bf=h_L^N-h_R^N,稱為N的平衡因子; ②lp和rp分別為指向左、右子樹的指針; ③lc和rc分別為左半部e_i(0≤i≤n-1)和右半部e_i(n+1≤i≤2n)的實際個數(shù); ④所有元素e_i(i=0,1,…,2n)構(gòu)成一個標識順序集: ∀e_i＝K_i∈N,K_i<K_i+1(i=0,1,…,2n-1);⑤若N為葉結(jié)點,則1≤(lc+rc+1)≤2n+1;否則2n+1-m≤(lc+rc+1)≤2n+1。n稱為SB-樹的階,m為很小的正整數(shù),表示空元素個數(shù)。

圖1 SB-樹結(jié)點的結(jié)構(gòu)

(5)對任一結(jié)點N, 若D_L^N≠∅, D_R^N≠∅, 則在N的左子樹中存在所有碼值最大者K_max^N,其元素e_max^N稱為N的最大下界,其結(jié)點N_max^N稱為N的最大下界結(jié)點。同樣,在N的右子樹中有N的最小上界碼值K_min^N及其元素e_min^N和最小上界結(jié)點N_min^N,且K_max^N

。SB-樹整體結(jié)構(gòu)如圖2所示。

圖2 SB-樹結(jié)構(gòu)

3.SB-樹的性能
(1)查找性能:①具有N個索引項(或數(shù)據(jù)記錄)的SB-樹的最大高度h為h<1.44log₂(N+2n+1-m)-1.44log₂(2n+1-m)+1。②最壞情況下查找的時間復雜度為0(log₂(N+2n))+0(Blog₂n),其中B為結(jié)點內(nèi)的二分查找代價。
(2)存儲空間:①設(shè)結(jié)點的格式與大小一樣,令bf、rc、lc各一字節(jié),lp、rp是兩個指針,2n+1個Rid實際上也是指針,令指針長度為PR,則其存儲記錄大小為S_N＝3+2PR+(2n+1)PR=(2n+3)PR+3字節(jié)。②SB-樹的存儲空間依賴于其是否成塊,若不成塊,則N個數(shù)據(jù)記錄的n階SB-樹的結(jié)點數(shù)為

其存儲空間為ST=S_N×N_n。若成塊,設(shè)BS為塊的大小,則組成因子為

其存儲空間為

(3)性能比較:將SB-樹和代表性的B-樹、AVL樹的性能進實驗測試比較,其結(jié)果如下: ①插入:SB-樹最好。因為它的查找時間接近于AVL樹,但沒有那么多的內(nèi)存分配和旋轉(zhuǎn)操作; 它具有類似于B-樹的維護特征,但沒有B-樹的結(jié)點內(nèi)和結(jié)點間的數(shù)據(jù)移動。②查找: AVL樹最好,因無結(jié)點內(nèi)的查找; SB-樹比B-樹好,因為在搜索路徑上,不需要對每一結(jié)點進行二分查找,只需比較其最大(右)和最小(左)元素即可。③存儲代價: SB-樹最好,B-樹次之,AVL-樹最差。
綜上所述,SB-樹綜合性能最優(yōu),AVL樹的存取性能最優(yōu),但存儲性能明顯低于B-樹。