[發(fā)明專利]基于哈希的聚簇表存儲(chǔ)方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201110392274.6
• 申請(qǐng)日: 2011-11-30
• 公開（公告）號(hào): CN102521304A
• 公開（公告）日: 2012-06-27
• 發(fā)明（設(shè)計(jì)）人: 李茂增;陳建克;何國(guó)明;馮玉;李祥凱;冷建全
• 申請(qǐng)（專利權(quán)）人: 北京人大金倉(cāng)信息技術(shù)股份有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京汲智翼成知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11381
• 代理人: 陳曦;郭亞芳

技術(shù)領(lǐng)域

本發(fā)明涉及一種數(shù)據(jù)庫(kù)存儲(chǔ)方法，尤其涉及一種面向數(shù)據(jù)庫(kù)存儲(chǔ)管理的需要，基于哈希(hash)的聚簇表存儲(chǔ)方法，屬于數(shù)據(jù)庫(kù)存儲(chǔ)技術(shù)領(lǐng)域。

背景技術(shù)

數(shù)據(jù)庫(kù)(Database)是依照某種數(shù)據(jù)模型組織起來(lái)并存放二級(jí)存儲(chǔ)器中的數(shù)據(jù)集合。在數(shù)據(jù)庫(kù)技術(shù)中，可以使用兩種形式描述客觀現(xiàn)實(shí)的數(shù)據(jù)：物理數(shù)據(jù)描述和邏輯數(shù)據(jù)描述。物理數(shù)據(jù)描述是指數(shù)據(jù)在存儲(chǔ)設(shè)備上的存儲(chǔ)方式，物理數(shù)據(jù)是實(shí)際存放在存儲(chǔ)設(shè)備上的數(shù)據(jù)，這些數(shù)據(jù)也稱為物理記錄。邏輯數(shù)據(jù)描述是指用戶或程序員用于操作的數(shù)據(jù)形式，邏輯數(shù)據(jù)是一種抽象的概念，是對(duì)客觀現(xiàn)實(shí)世界的反映和記錄，這些數(shù)據(jù)也可以稱為邏輯記錄。物理數(shù)據(jù)和邏輯數(shù)據(jù)之間的轉(zhuǎn)換通過(guò)數(shù)據(jù)庫(kù)管理系統(tǒng)實(shí)現(xiàn)。

在數(shù)據(jù)庫(kù)管理系統(tǒng)中，采用字段來(lái)標(biāo)記實(shí)體屬性的可以命名的最小信息單位。字段的集合稱為元組。一個(gè)元組表示一個(gè)具體的實(shí)體。在現(xiàn)有的關(guān)系型數(shù)據(jù)庫(kù)中，往往將一個(gè)數(shù)據(jù)表中的行作為元組，列作為字段。一個(gè)數(shù)據(jù)表由行(元組)和列(字段)構(gòu)成，組成一個(gè)二維關(guān)系表。若干個(gè)數(shù)據(jù)表、視圖及相關(guān)的文件等組成一個(gè)統(tǒng)一的相關(guān)聯(lián)的數(shù)據(jù)庫(kù)系統(tǒng)。

在數(shù)據(jù)庫(kù)系統(tǒng)中，索引是對(duì)數(shù)據(jù)表中一列或多列的值進(jìn)行排序的一種結(jié)構(gòu)，使用索引可以快速訪問(wèn)數(shù)據(jù)表中的特定信息。索引分為聚簇索引和非聚簇索引兩種。所謂聚簇是指為了提高某個(gè)字段(或字段組)的查詢速度，將這些字段上具有相同值的元組集中存放在連續(xù)的物理塊中。因此，聚簇索引能夠提高多行檢索的速度，而非聚簇索引適合于單行的檢索。

哈希聚簇(hash?cluster)是指通過(guò)預(yù)先分配空間的方式，將相同關(guān)鍵字(key)的數(shù)據(jù)存放在一起，以提高查詢性能的一項(xiàng)技術(shù)。目前，僅僅在Oracle系列數(shù)據(jù)庫(kù)產(chǎn)品有哈希聚簇功能，其它的數(shù)據(jù)庫(kù)產(chǎn)品，例如SQL?Server、IBM?DB2以及達(dá)夢(mèng)DM等中均沒有類似功能。在實(shí)際使用中，該項(xiàng)技術(shù)仍然存在一定的缺陷，例如關(guān)鍵字(key)的數(shù)量難以精確估計(jì)，造成哈希聚簇技術(shù)的應(yīng)用場(chǎng)景非常有限。

發(fā)明內(nèi)容

鑒于現(xiàn)有技術(shù)所存在的不足，本發(fā)明所要解決的技術(shù)問(wèn)題在于提供一種基于哈希的聚簇表存儲(chǔ)方法。該方法能夠提供跨過(guò)索引直達(dá)元組的數(shù)據(jù)庫(kù)存儲(chǔ)管理機(jī)制。

為實(shí)現(xiàn)上述的發(fā)明目的，本發(fā)明采用下述的技術(shù)方案：

一種基于哈希的聚簇表存儲(chǔ)方法，所述數(shù)據(jù)表由元組和列構(gòu)成，其特征在于包括以下步驟：

步驟1：預(yù)先初始化空的數(shù)據(jù)表頁(yè)面空間；

步驟2：指定所述數(shù)據(jù)表的一個(gè)或多個(gè)列為哈希列；

步驟3：根據(jù)各個(gè)元組的所述哈希列的值來(lái)計(jì)算哈希值，作為相應(yīng)元組的存儲(chǔ)位置；

步驟4：根據(jù)所述哈希值映射出所述相應(yīng)元組在所述頁(yè)面空間上的行指針；

步驟5：根據(jù)所述行指針，將所述相應(yīng)元組插入到所述頁(yè)面空間。

其中較優(yōu)地，根據(jù)可能用到的元組的、哈希列的哈希值的個(gè)數(shù)，對(duì)所述頁(yè)面空間進(jìn)行動(dòng)態(tài)預(yù)分配。

其中較優(yōu)地，在所述步驟3中，當(dāng)各個(gè)元組的哈希列的哈希值中出現(xiàn)兩個(gè)或多個(gè)哈希值相同時(shí)，對(duì)相應(yīng)的哈希值增加溢出鏈，將該元組存儲(chǔ)到溢出鏈中。

其中較優(yōu)地，還包括對(duì)所述聚簇表的查詢步驟：

根據(jù)指定的哈希列的值計(jì)算出相應(yīng)的哈希值，通過(guò)所述哈希值按照已建立的映射關(guān)系找到行指針，根據(jù)所述行指針找到相應(yīng)的元組。

其中較優(yōu)地，當(dāng)所述聚簇表是非獨(dú)特類型聚簇表時(shí)，所述查詢步驟還包括：對(duì)查詢得到的、符合行指針的多條元組的哈希列的值進(jìn)行驗(yàn)證。

其中較優(yōu)地，當(dāng)所述聚簇表是獨(dú)特類型聚簇表時(shí)，對(duì)查詢得到的符合行指針的多條元組的哈希列的值，不進(jìn)行驗(yàn)證。

其中較優(yōu)地，如果在查詢過(guò)程后面有插入操作，那么還包括動(dòng)態(tài)擴(kuò)充聚簇表的頁(yè)面空間的步驟：

獲得需要插入的元組的哈希列的值，然后計(jì)算出哈希值，并通過(guò)一對(duì)一的映射得到所述需要插入的元組存儲(chǔ)在頁(yè)面上的行指針，然后根據(jù)所述行指針找到對(duì)應(yīng)的頁(yè)面進(jìn)行插入。

其中較優(yōu)地，如果所述行指針找到的頁(yè)面的頁(yè)面空間不夠，則將所述需要插入的元組存儲(chǔ)在溢出鏈中。

其中較優(yōu)地，如果查詢列包括所述數(shù)據(jù)表的所有哈希列，或者使用特定哈希函數(shù)時(shí)的查詢列為哈希列的前綴以及排序操作，使用聚簇掃描方式進(jìn)行掃描。

本發(fā)明所提供的聚簇表存儲(chǔ)方法對(duì)現(xiàn)有哈希聚簇技術(shù)做了進(jìn)一步改進(jìn)，可以實(shí)現(xiàn)跨過(guò)索引直達(dá)元組的數(shù)據(jù)庫(kù)存儲(chǔ)管理機(jī)制，從而在大規(guī)模數(shù)據(jù)庫(kù)系統(tǒng)的使用過(guò)程中避免了索引對(duì)緩存資源的大量占用，改善了數(shù)據(jù)庫(kù)系統(tǒng)的使用性能。

附圖說(shuō)明

下面結(jié)合附圖和具體實(shí)施方式對(duì)本發(fā)明做進(jìn)一步的詳細(xì)說(shuō)明。