[發(fā)明專利]基于固態(tài)硬盤的高維數(shù)據(jù)索引結(jié)構(gòu)設(shè)計方法

有效

• 申請?zhí)枺?/td>: 201110452044.4
• 申請日: 2011-12-29
• 公開（公告）號: CN102542057A
• 公開（公告）日: 2012-07-04
• 發(fā)明（設(shè)計）人: 崔斌;呂雁飛;李井
• 申請（專利權(quán)）人: 北京大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京路浩知識產(chǎn)權(quán)代理有限公司 11002
• 代理人: 王瑩

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

本發(fā)明涉及數(shù)據(jù)庫索引結(jié)構(gòu)，具體涉及一種基于固態(tài)硬盤的高維數(shù)據(jù)索引結(jié)構(gòu)設(shè)計方法。

背景技術(shù)

R樹，是目前應(yīng)用最廣的高維數(shù)據(jù)索引結(jié)構(gòu)之一。傳統(tǒng)的R樹設(shè)計均假設(shè)外存為磁盤。隨著閃存技術(shù)的成熟，基于閃存的固態(tài)硬盤得到了廣泛使用。由于閃存的自身特點，固態(tài)硬盤的隨機更新較慢。R樹結(jié)構(gòu)由于有大量隨機更新操作，所以傳統(tǒng)的R樹設(shè)計不能很好地適應(yīng)固態(tài)硬盤的特性。

上至大型數(shù)據(jù)中心，小到嵌入式系統(tǒng)，閃存(flash?memory)作為硬盤(hard?disk)的理想替代品，被廣泛應(yīng)用于不同的系統(tǒng)中。這樣大規(guī)模的應(yīng)用主要得益于其出色的I/O特性，高度的可靠性及其低功耗特性。基于閃存的磁盤，如固態(tài)硬盤(SSD)，作為對傳統(tǒng)磁盤的替代，越來越廣泛地被應(yīng)用于各種場合。下表列出了固態(tài)硬盤在2KB大小塊訪問下的I/O數(shù)據(jù)，單位是MB/sec。

從表中數(shù)據(jù)可以看出，1)固態(tài)硬盤具有不對稱的IO特性：其讀操作的速度遠超其寫操作的速度，特別是隨機寫操作；2)閃存的隨機讀性能與順序讀操作相差不多。這些特性也使得之前針對磁盤的優(yōu)化在固態(tài)硬盤上失效了。如何針對固態(tài)硬盤的讀寫特性設(shè)計相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法成為近年來研究工作的熱點。

R樹(R-Tree)，作為一個針對高維數(shù)據(jù)的通用索引結(jié)構(gòu)，已經(jīng)被整合進了諸多數(shù)據(jù)庫系統(tǒng)，如PostgreSQL，MySQL等中。圖1是一棵R樹的示例。在R樹上的修改常常散落在整棵樹的各個角落，因此這些修改會導(dǎo)致大量的隨機寫操作。而隨機寫操作是固態(tài)硬盤上最慢的操作，這大大地惡化了閃存上R樹的整體性能。從I/O的角度上看R樹與一維索引結(jié)構(gòu)B樹相比有如下的特點：

重疊讀。在R樹中，同一層級的節(jié)點的最小包容矩形(MBR)常常存在重疊，這導(dǎo)致查詢一個節(jié)點可能需要更多次的讀取祖先節(jié)點的操作(很可能超過樹的高度)，是為R樹和B樹的一個顯著差異。

最小包容矩形的級聯(lián)更新。樹葉節(jié)點的更新可能會導(dǎo)致這該節(jié)點最小包容矩形大小的變化，而此更新可能會導(dǎo)致父親節(jié)點的邊界的擴大。這樣的更新很可能一直傳遞到根節(jié)點。因此，R樹中高層節(jié)點的更新比B樹上要頻繁得多。

RFTL方法是R樹上針對閃存特定優(yōu)化的經(jīng)典工作，該工作使用日志鏈的方式來管理R樹的更新操作。在這種方式中，更新被記為“日志”順序?qū)懟兀瑥亩纬梢粋€日志的序列，每個結(jié)點的更新其附在每個節(jié)點之后來完成消減隨機寫的目的。當這個日志鏈的長度超過一個預(yù)先設(shè)定的閾值時，日志鏈中的內(nèi)容才會被真正更新到節(jié)點中。當讀取一個結(jié)點中的信息時，除了要讀出原始數(shù)據(jù)，還要將日志鏈中的數(shù)據(jù)也全部讀出。然而這個方法的最大的問題是：隨著日志鏈長度的增加，在日志鏈上的讀操作將會急劇增加。特別是節(jié)點越接近根節(jié)點，日志鏈越長(因為R樹高層的更新非常頻繁)，而另一方面，高層節(jié)點又正是讀密集的節(jié)點，這樣會導(dǎo)致讀操作的代價急劇增加。

近些年來，技術(shù)的進步使得固態(tài)硬盤的讀寫的差距減小，過多的讀操作的引入會降低整體的性能。如何在不大量增加讀操作的基礎(chǔ)上降低隨機寫操作是在固態(tài)硬盤上移植R樹的關(guān)鍵問題。

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

(一)要解決的技術(shù)問題

本發(fā)明的目的在于提出一種基于固態(tài)硬盤的高維數(shù)據(jù)索引結(jié)構(gòu)設(shè)計方法，在不大量增加讀操作的基礎(chǔ)上降低隨機寫操作，以在固態(tài)硬盤上移植R樹。

(二)技術(shù)方案

為了解決上述技術(shù)問題，本發(fā)明提供一種基于固態(tài)硬盤的高維數(shù)據(jù)索引結(jié)構(gòu)設(shè)計方法，包括步驟：

將索引結(jié)構(gòu)分為原始R樹區(qū)和節(jié)點差異日志區(qū)兩個部分，分別存儲原始版本數(shù)據(jù)和原始版本與最近版本的差異日志；

在內(nèi)存中設(shè)計一個哈希表來存儲節(jié)點及其更新在所述節(jié)點差異日志區(qū)存儲位置對應(yīng)關(guān)系的信息；一旦一個新的更新完成，讀出這個節(jié)點更早時候的更新日志，然后將其和現(xiàn)在的日志合并并重新存入，作為到目前為止該節(jié)點的所有更新日志。

優(yōu)選地，所述節(jié)點差異日志區(qū)分為日志頁來進行使用，一個日志頁能夠存儲多個節(jié)點差異的信息。

優(yōu)選地，當日志達到一定量時，將所述節(jié)點差異日志區(qū)與原始R樹區(qū)進行合并日志操作。

優(yōu)選地，每次更新包括多個更新項，每個更新項記錄了對R樹節(jié)點的一個分支的更新操作，包括三種不同的更新操作：插入分支、更新分支和刪除分支。

優(yōu)選地，每個更新項的前兩位標識操作類型，接下來的位標識分支號和值。

優(yōu)選地，對同一分支的更新會合并成一個更新項記錄，記錄的值為最后更新的值。

優(yōu)選地，該索引結(jié)構(gòu)滿足應(yīng)用程序查詢請求的方法包括步驟：

讀取節(jié)點的號；