[發(fā)明專利]一種基于T-lt樹的主存數(shù)據(jù)庫的索引方法

有效

• 申請?zhí)枺?/td>: 200910033414.3
• 申請日: 2009-06-19
• 公開（公告）號: CN101587484A
• 公開（公告）日: 2009-11-25
• 發(fā)明（設(shè)計）人: 秦小麟;柏傳杰;戴華
• 申請（專利權(quán)）人: 南京航空航天大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京經(jīng)緯專利商標代理有限公司
• 代理人: 許 方

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

本發(fā)明涉及一種數(shù)據(jù)庫索引方法，主要應(yīng)用在基于主存的數(shù)據(jù)庫管理系統(tǒng)中，屬于計算機數(shù)據(jù)庫領(lǐng)域。

背景技術(shù)

隨著大容量內(nèi)存越來越便宜，現(xiàn)在配置一臺大內(nèi)存的計算機也越來越容易。對數(shù)據(jù)庫系統(tǒng)而言，已經(jīng)有條件將數(shù)據(jù)庫的“主版本”常駐內(nèi)存，這樣可使系統(tǒng)性能獲得很大的改善，如I/O操作大量減少、事務(wù)的狀態(tài)轉(zhuǎn)換及其相聯(lián)CPU高速緩存的替換大量減少、鎖的競爭下降，更有效的內(nèi)存查找結(jié)構(gòu)和查詢處理可以被使用等。

數(shù)據(jù)庫的“主版本”或者整個數(shù)據(jù)庫都常駐內(nèi)存的數(shù)據(jù)庫系統(tǒng)被稱為主存數(shù)據(jù)庫(MMDB，Main?Memory?Database)。由于內(nèi)存系統(tǒng)與磁盤系統(tǒng)具有不同的特性，因而MMDB與磁盤數(shù)據(jù)庫(DRDB，Disk-Resident?Database)在性能、存儲格式、尤其是查詢處理等方面都有著比較大的差別。DRDB系統(tǒng)的“瓶頸”是磁盤I/O，故查詢處理的優(yōu)化策略主要是針對減少磁盤的存取次數(shù)的，并且盡量存儲臨時結(jié)果，以“空間”換“時間”。而在MMDB中，由于內(nèi)存空間及其寶貴，其查詢處理算法則要極力減少比較次數(shù)，并且盡量不存儲臨時結(jié)果，以“時間”換“空間”。在這樣的前提下，原有的DRDB的索引結(jié)構(gòu)對MMDB來說就不再適用了，研究新的適合MMDB的索引結(jié)構(gòu)也就自然而然的成了研究者關(guān)注的問題。

傳統(tǒng)的主存數(shù)據(jù)庫主要采取以下幾種索引機制：

(1)哈希索引機制：是一種通過哈希函數(shù)實現(xiàn)鍵值和記錄地址快速映射，以提供高速隨機訪問的機制。使用哈希機制能實現(xiàn)快速查詢，但它對空間的利用率不高，并且范圍查詢的效率也不高。

(2)平衡二叉樹(AVL樹)索引機制：AVL樹本質(zhì)上是一棵二叉樹，采用二分查找法，查詢速度很快。但AVL樹上的更新操作經(jīng)常導(dǎo)致樹的不平衡，用于平衡旋轉(zhuǎn)操作的時間開銷過大。而且樹的每個結(jié)點只能保存1個關(guān)鍵字用于比較，同時還要保存父結(jié)點指針、左右孩子結(jié)點指針、平衡因子等其他信息，故Cache利用率較低。

(3)B樹索引機制：B樹是一種適用于磁盤數(shù)據(jù)庫管理系統(tǒng)的索引機制。B樹的每個結(jié)點有多棵子樹，且深度不大，查詢速度較快，只需較少次數(shù)的磁盤I/O就可以找到目標數(shù)據(jù)。B樹中的葉結(jié)點較多，由于葉結(jié)點沒有子樹指針，故指針相對數(shù)據(jù)的空間占用量很小，從而有利于提高內(nèi)存空間的利用率。B樹的一個變種B+樹，則是一種平衡的多路查找樹，已經(jīng)在傳統(tǒng)的磁盤數(shù)據(jù)庫中得到了廣泛的應(yīng)用。由于B+樹的非葉結(jié)點僅具有索引作用，與記錄有關(guān)的信息均存放在葉結(jié)點中，因此會對存儲空間造成一定的浪費。

(4)T樹索引機制：是一種適用于主存數(shù)據(jù)庫的有序數(shù)據(jù)索引機制，在大部分主存數(shù)據(jù)庫系統(tǒng)中都有應(yīng)用。它是由AVL樹和B樹演變而來，是一種在一個結(jié)點中存放多個元素的平衡二叉樹。它保留有AVL樹的二分搜索特性，同時具有B樹的優(yōu)良的存儲性能。T樹的每個結(jié)點可以保存多個關(guān)鍵字，因而提高了空間的利用率。但是，對T樹結(jié)點的更新會導(dǎo)致樹的不平衡，因此用于平衡旋轉(zhuǎn)的開銷還是比較大的。

現(xiàn)有的相關(guān)專利申請情況如下：

①海量數(shù)據(jù)內(nèi)存數(shù)據(jù)庫中快速定位的網(wǎng)格+T樹索引的方法(申請日期：2006.02.20，公開號：CN1838124)。

②數(shù)據(jù)庫索引的方法(申請日期：2008.05.30，公開號：CN101286160)。

相關(guān)的論文情況如下：

①R.Bayer?and?E.M.McCreight，Organization?and?maintenance?of?large?orderedindexes，Acta?Informatica，1972.

②Douglas?Comer，The?Ubiquitous?B-Tree，Computing?Surveys(CSUR)，1979.

③TJ?Lehman，MJ?Carey.A?Study?of?Index?Structures?for?Main?Memory?DatabaseManagement?Systems.Conference?on?Very?Large?Data?Bases，1986：294～302.

其中專利②和論文①、②都是關(guān)于B樹和B+樹的索引機制，適用于基于磁盤的數(shù)據(jù)庫索引機制，并不適用于主存數(shù)據(jù)庫，在時空開銷上類似于平衡二叉樹；專利①和論文③都是關(guān)于T樹的索引機制，雖然T樹是基于主存的數(shù)據(jù)庫的一種比較優(yōu)秀的索引機制，但是，對T樹結(jié)點的更新會導(dǎo)致樹的不平衡，因此用于平衡旋轉(zhuǎn)的開銷還是比較大的。

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

本發(fā)明的目的是提供一種用于主存數(shù)據(jù)庫索引方法，該方法能在主存數(shù)據(jù)庫中提高查詢效率，節(jié)省時空開銷。