內(nèi)存數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu)(數(shù)據(jù)庫(kù))

時(shí)間：2022-11-05 04:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-11-05 04:30:01 來(lái)源：信息時(shí)代

    內(nèi)存數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu) : 內(nèi)存數(shù)據(jù)庫(kù)物理數(shù)據(jù)的組織方法與具體存儲(chǔ)結(jié)構(gòu)。這些物理組織與存儲(chǔ)結(jié)構(gòu)是內(nèi)存數(shù)據(jù)庫(kù)總體設(shè)計(jì)目標(biāo)(使內(nèi)存和CPU的利用率盡可能高)的實(shí)現(xiàn)基礎(chǔ),其存儲(chǔ)結(jié)構(gòu)、索引結(jié)構(gòu)、中間數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)都必須考慮內(nèi)存的直接存取這一特征。這里介紹幾種適合于MMDB的物理組織結(jié)構(gòu)。
1. 區(qū)-段式組織結(jié)構(gòu)
區(qū)-段式組織結(jié)構(gòu)將存儲(chǔ)空間邏輯地劃分為“分區(qū)”,每一個(gè)分區(qū)物理地由若干“段”組成。一個(gè)段是內(nèi)存中一個(gè)固定長(zhǎng)度的連續(xù)區(qū)域,相當(dāng)于“頁(yè)”,是內(nèi)外存I/O的單位,也是內(nèi)存空間分配及內(nèi)存數(shù)據(jù)庫(kù)恢復(fù)的單位。
區(qū)-段式組織結(jié)構(gòu)如圖1所示,段中的每個(gè)記錄有一個(gè)唯一標(biāo)識(shí)符(record identifier,Rid),它是一個(gè)三元組<i,j,k>,分別表示分區(qū)號(hào)、段號(hào)、段內(nèi)的記錄槽號(hào)。記錄槽(record slot)包含了對(duì)應(yīng)記錄的長(zhǎng)度和首地址。每次存取時(shí),由于是內(nèi)存數(shù)據(jù)庫(kù),存取方法返回的不必是所需記錄數(shù)據(jù)的副本,只需簡(jiǎn)單地將其槽中的地址返回即可。

圖1 區(qū)-段式存儲(chǔ)結(jié)構(gòu)

2.影子內(nèi)存式組織結(jié)構(gòu)
影子內(nèi)存式組織結(jié)構(gòu)將內(nèi)存數(shù)據(jù)庫(kù)空間劃分成兩部分,一部分是MMDB的主拷貝,另一部分為“影子”拷貝,其體系結(jié)構(gòu)如圖2所示。在事務(wù)的正常操作期間,每次查詢都產(chǎn)生一個(gè)分別對(duì)于影子內(nèi)存(shadow memory,SM)和主拷貝(primary database,PDB)的雙地址,且總是先對(duì)SM試探;若不成功,再對(duì)PDB操作。所有的更新操作都在SM中進(jìn)行,且都記錄在活動(dòng)日志(ative log,AL)中。每當(dāng)一個(gè)事務(wù)提交時(shí),由它所產(chǎn)生的在SM中的“后映像”(after image)拷貝到PDB中。

圖2 影子內(nèi)存式存儲(chǔ)結(jié)構(gòu)

3.索引式組織結(jié)構(gòu)
B-樹(shù)、B⁺-樹(shù)仍然是可用的大型動(dòng)態(tài)索引結(jié)構(gòu)之一。但B-樹(shù)比B⁺-樹(shù)更適合,因?yàn)樗幌馚⁺-樹(shù)那樣高層結(jié)點(diǎn)碼是葉結(jié)點(diǎn)中碼的重復(fù),葉結(jié)點(diǎn)也不含順序鏈接指針,所以更省內(nèi)存。
4. Hash式組織結(jié)構(gòu)
有如下幾種形式的Hashing組織結(jié)構(gòu):
(1)桶散布Hash(如圖3所示): 它將碼值空間映射到一個(gè)“桶散布表”(buckets scatter table)。每一桶由一或少數(shù)幾塊鏈接組成,鏈頭就是“桶散布表”中的一項(xiàng),每一這樣的鏈實(shí)際就是Hashing“碰撞”的一個(gè)“同義鏈”。

圖3 桶散布Hash組織

(2)擴(kuò)展Hash(如圖4所示): 其組織是一個(gè)由目錄結(jié)點(diǎn)和葉結(jié)點(diǎn)組成的二層結(jié)構(gòu)。目錄由一個(gè)指明目錄深度d的目錄頭和2d個(gè)指針的目錄項(xiàng)組成。深度d表示取偽碼(經(jīng)Hashing后的碼)最左的d BIT(位)來(lái)定位目錄項(xiàng),偽碼就是一個(gè)碼K經(jīng)Hash函數(shù)變換而得到的一個(gè)定長(zhǎng)BIT串(見(jiàn)圖4)。每一目錄項(xiàng)是一個(gè)指向葉結(jié)點(diǎn)Li的指針。

圖4 可擴(kuò)展Hash組織

(3)線性擴(kuò)展Hash: 它類(lèi)似于可擴(kuò)展Hash,但又具有桶散布Hash的特色,是可擴(kuò)展Hash與桶散布Hash的結(jié)合。其組織結(jié)構(gòu)如圖5所示,使用一個(gè)可擴(kuò)展Hash式的目錄和桶散布Hash式的塊拉鏈(或桶),不過(guò)這里的鏈不是“碰撞”的“同義鏈”,而且塊的組成也僅是為了提高空間的利用率,它本來(lái)是可以單個(gè)數(shù)據(jù)記錄地拉鏈的。

圖5 線性可擴(kuò)展Hash組織

(4)多目錄Hash:它是將Hash和索引技術(shù)組合的另一種數(shù)據(jù)組織方法。如圖6所示,它首先將碼(值)映射成Hash地址,然后劃分Hash地址成兩部分,分別用來(lái)定位和檢索相應(yīng)目錄。這里目錄的個(gè)數(shù)N是固定的。

圖6 多目錄Hash組織