[發(fā)明專利]一種針對二維數(shù)據(jù)表的高效索引及創(chuàng)建和查詢方法

無效

• 申請?zhí)枺?/td>: 201210594103.6
• 申請日: 2012-12-29
• 公開（公告）號: CN103020305A
• 公開（公告）日: 2013-04-03
• 發(fā)明（設(shè)計(jì)）人: 孟祥斌;崔維力;武新;趙偉
• 申請（專利權(quán)）人: 天津南大通用數(shù)據(jù)技術(shù)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 天津?yàn)I海科緯知識產(chǎn)權(quán)代理有限公司 12211
• 代理人: 孫春玲

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

本發(fā)明屬于數(shù)據(jù)存儲領(lǐng)域，尤其是涉及一種針對二維數(shù)據(jù)表的高效索引及創(chuàng)建和查詢方法。

背景技術(shù)

關(guān)系型數(shù)據(jù)庫中的關(guān)系表，就是一種典型的二維數(shù)據(jù)。常見的數(shù)據(jù)計(jì)算系統(tǒng)中往往采用粗粒度索引（rough?index）或者精確索引，來降低針對字段進(jìn)行搜索時(shí)的I/O量，從而提升查詢性能。精確索引又分全局索引和局部索引兩種，以哈希索引為例：

全局哈希索引查詢性能很好，但創(chuàng)建和維護(hù)的代價(jià)極高，數(shù)據(jù)膨脹率很大（往往比原始數(shù)據(jù)膨脹1.5倍以上，甚至更大）。

局部哈希索引對每個(gè)數(shù)據(jù)塊分別創(chuàng)建索引，對某個(gè)數(shù)據(jù)塊更新時(shí)的維護(hù)代價(jià)僅限于這個(gè)數(shù)據(jù)塊的索引數(shù)據(jù)，因而維護(hù)代價(jià)較低。但是，查詢時(shí)每塊的索引都要被掃描，I/O次數(shù)較多，性能不如全局索引。

粗粒度索引是一種局部索引，其存儲的內(nèi)容是每個(gè)數(shù)據(jù)塊中的統(tǒng)計(jì)信息。由于統(tǒng)計(jì)信息數(shù)據(jù)量很小，在查詢時(shí)，其I/O代價(jià)幾乎可以忽略不計(jì)

如果要查找某一字段中取值為100的數(shù)據(jù)，可以利用帶有最大值、最小值信息的粗粒度索引，即可在無需打開任何數(shù)據(jù)的前提下，立即排除掉肯定不命中的數(shù)據(jù)塊（最大值小于100或最小值大于100）；同時(shí)，可以確定肯定命中的數(shù)據(jù)塊（最大值和最小值都等于100）。而后，再打開其他無法確定的數(shù)據(jù)，即可準(zhǔn)確定位所有命中的數(shù)據(jù)。但對于分布較離散的數(shù)據(jù)非常容易失效（極端情況下，粗粒度索引可能無法過濾掉任何數(shù)據(jù)，查詢性能無法得到任何提升）。再者，粗粒度索引無法精確定位查詢結(jié)果，對于不能精確排除的數(shù)據(jù)塊，仍要打開原始數(shù)據(jù)進(jìn)行掃描。

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

本發(fā)明要解決的問題是提供一種針對二維數(shù)據(jù)表的高效索引及創(chuàng)建和查詢方法。

為解決上述技術(shù)問題，本發(fā)明采用的技術(shù)方案是：一種針對二維數(shù)據(jù)表的高效索引的創(chuàng)建方法，包括：

1）將二維數(shù)據(jù)表分成若干的數(shù)據(jù)塊；

2）為數(shù)據(jù)塊創(chuàng)建塊粗粒度索引；

3）為數(shù)據(jù)塊創(chuàng)建塊精確索引。

進(jìn)一步的，所述的第3步驟中的塊局部索引為局部哈希索引。

進(jìn)一步的，所述的第1步驟包括：

1）按一定行數(shù)將二維表進(jìn)行水平切割；

2）按列將二維表進(jìn)行垂直切割。

根據(jù)本發(fā)明的另一方面還提供了一種針對二維數(shù)據(jù)表的高效索引，包括：

塊粗粒度索引，用以排除肯定不命中目標(biāo)數(shù)據(jù)塊和確定肯定命中的目標(biāo)數(shù)據(jù)塊；

塊局部精確索引，用以精確定位塊中命中數(shù)據(jù)。

進(jìn)一步的，所述塊局部精確索引為塊局部哈希索引。

進(jìn)一步的，所述的高效索引包括至少一個(gè)的塊粗粒度索引和至少一個(gè)的塊局部精確索引。

進(jìn)一步的，所述的粗粒度索引存儲針對塊的統(tǒng)計(jì)信息。

進(jìn)一步的，所述的粗粒度索引存儲針對塊中數(shù)據(jù)的最大值和最小值。

本發(fā)明還提供了一種針對二維數(shù)據(jù)表的高效索引的查詢方法，包括：

包括：

1）根據(jù)粗粒度索引選出塊中肯定命中和肯定不命中的目標(biāo)塊；

2）根據(jù)上一步篩選出的結(jié)果對于無法判定的目標(biāo)塊用局部精確索引進(jìn)行掃描，最終精確定位全部命中的數(shù)據(jù)。

由于采用上述技術(shù)方案，能夠以較低的創(chuàng)建和維護(hù)代價(jià)，同時(shí)索引數(shù)據(jù)膨脹率較小，I/O代價(jià)低，有效的提高了效率。

附圖說明

圖1是本發(fā)明針對二維數(shù)據(jù)表的高效索引的創(chuàng)建方法流程示意圖

圖2是本發(fā)明針對二維數(shù)據(jù)表的高效索引的查詢方法流程示意圖

圖3是本發(fā)明中一個(gè)實(shí)例中將二維數(shù)據(jù)表分割成數(shù)據(jù)塊的示意圖

圖4是本發(fā)明中一個(gè)實(shí)例二維數(shù)據(jù)表索引存儲示意圖

圖5是本發(fā)明中一個(gè)實(shí)例中針對設(shè)定查詢條件為數(shù)據(jù)取值等于100的查詢示意圖

具體實(shí)施方式

由圖1可以看出，本發(fā)明針對二維數(shù)據(jù)表的高效索引的創(chuàng)建方法流程按照

1）將二維數(shù)據(jù)表分成若干的數(shù)據(jù)塊；

2）為數(shù)據(jù)塊創(chuàng)建塊粗粒度索引；

3）為數(shù)據(jù)塊創(chuàng)建塊局部索引；采用以上3個(gè)步驟對二維數(shù)據(jù)表創(chuàng)建高效索引。圖1按照水平分割粒度為n（即每個(gè)數(shù)據(jù)塊中數(shù)據(jù)行數(shù)為n）進(jìn)行切割。

另外，一般都采用如圖3所示按一定行數(shù)和列數(shù)對二維表進(jìn)行水平和垂直切割。

圖2為是本發(fā)明針對二維數(shù)據(jù)表的高效索引的查詢方法流程示意圖，按照圖2所設(shè)定的步驟對二維數(shù)據(jù)表進(jìn)行分塊高效檢索。