一種針對二維數據表的高效索引及創建和查詢方法
2023-04-28 13:59:56
專利名稱：一種針對二維數據表的高效索引及創建和查詢方法
技術領域：
本發明屬於數據存儲領域，尤其是涉及一種針對二維數據表的高效索引及創建和查詢方法。
背景技術：
關係型資料庫中的關係表，就是一種典型的二維數據。常見的數據計算系統中往往採用粗粒度索引(rough index)或者精確索引，來降低針對欄位進行搜索時的I/O量，從而提升查詢性能。精確索引又分全局索引和局部索引兩種，以哈希索引為例全局哈希索引查詢性能很好，但創建和維護的代價極高，數據膨脹率很大(往往比原始數據膨脹1. 5倍以上，甚至更大)。局部哈希索引對每個數據塊分別創建索引，對某個數據塊更新時的維護代價僅限於這個數據塊的索引數據，因而維護代價較低。但是，查詢時每塊的索引都要被掃描，I/o次數較多，性能不如全局索引。粗粒度索引是一種局部索引，其存儲的內容是每個數據塊中的統計信息。由於統計信息數據量很小，在查詢時，其I/o代價幾乎可以忽略不計如果要查找某一欄位中取值為100的數據，可以利用帶有最大值、最小值信息的粗粒度索引，即可在無需打開任何數據的前提下，立即排除掉肯定不命中的數據塊(最大值小於100或最小值大於100);同時，可以確定肯定命中的數據塊(最大值和最小值都等於100)。而後，再打開其他無法確定的數據，即可準確定位所有命中的數據。但對於分布較離散的數據非常容易失效(極端情況下，粗粒度索引可能無法過濾掉任何數據，查詢性能無法得到任何提升)。再者，粗粒度索引無法精確定位查詢結果，對於不能精確排除的數據塊，仍要打開原始數據進行掃描。
發明內容
本發明要解決的問題是提供一種針對二維數據表的高效索引及創建和查詢方法。為解決上述技術問題，本發明採用的技術方案是一種針對二維數據表的高效索引的創建方法，包括I)將二維數據表分成若干的數據塊；2)為數據塊創建塊粗粒度索引；3)為數據塊創建塊精確索引。進一步的，所述的第3步驟中的塊局部索引為局部哈希索引。進一步的，所述的第I步驟包括I)按一定行數將二維表進行水平切割；2)按列將二維表進行垂直切割。根據本發明的另一方面還提供了一種針對二維數據表的高效索引，包括塊粗粒度索引，用以排除肯定不命中目標數據塊和確定肯定命中的目標數據塊；
塊局部精確索引，用以精確定位塊中命中數據。進一步的，所述塊局部精確索引為塊局部哈希索引。進一步的，所述的高效索引包括至少一個的塊粗粒度索引和至少一個的塊局部精確索引。進一步的，所述的粗粒度索引存儲針對塊的統計信息。進一步的，所述的粗粒度索引存儲針對塊中數據的最大值和最小值。本發明還提供了一種針對二維數據表的高效索引的查詢方法，包括包括I)根據粗粒度索引選出塊中肯定命中和肯定不命中的目標塊； 2)根據上一步篩選出的結果對於無法判定的目標塊用局部精確索引進行掃描，最終精確定位全部命中的數據。由於採用上述技術方案，能夠以較低的創建和維護代價，同時索引數據膨脹率較小，I/O代價低，有效的提高了效率。
圖1是本發明針對二維數據表的高效索引的創建方法流程示意2是本發明針對二維數據表的高效索引的查詢方法流程示意3是本發明中一個實例中將二維數據表分割成數據塊的示意4是本發明中一個實例二維數據表索引存儲示意5是本發明中一個實例中針對設定查詢條件為數據取值等於100的查詢示意圖
具體實施例方式由圖1可以看出，本發明針對二維數據表的高效索引的創建方法流程按照I)將二維數據表分成若干的數據塊；2)為數據塊創建塊粗粒度索引；3)為數據塊創建塊局部索引；採用以上3個步驟對二維數據表創建高效索引。圖1按照水平分割粒度為η (即每個數據塊中數據行數為η)進行切割。另外，一般都採用如圖3所示按一定行數和列數對二維表進行水平和垂直切割。圖2為是本發明針對二維數據表的高效索引的查詢方法流程示意圖，按照圖2所設定的步驟對二維數據表進行分塊高效檢索。本發明的一個實例場景，如圖3所示，將二維數據從邏輯上二維數據從邏輯上進行網格化(無需將數據在物理上進行網格化存儲)，形成以數據塊為單位的視圖；本實施例作為一個列式資料庫，每個數據列獨立存儲，並以固定行數為單位劃分塊(Data Cell)。在為其中一列數據創建索引時，把粗粒度索引緊湊存儲於一個文件中；本地哈希索引也緊湊存儲保存在另一個文件中(其中，每個塊的某一個哈希索引的中屬於同一個哈希衝突鏈中的所有數據緊湊存儲在一起，保證掃描一個塊的索引只需一次I/o)。圖4中，每個局部索引中的小方塊表示局部哈希索弓I中哈希值相同的數據所組成的哈希桶如圖5所示，在設定了一定的查詢條件以後，在本實施例中設定為查詢數值為100的條件，在對二維數據表進行查詢時，首先對組成二維數據表的每一個數據塊(Data Cell)的粗粒度索引進行過濾，由粗粒度索引的特性可知，如本實例中，粗粒度索引保存了該塊的統計信息，包括了該塊中最大和最小值。通過粗粒度索引的初步過濾，能夠有效的選出肯定命中和肯定不命中的塊，對於暫時無法精確確定是否命中的情況，則由塊中的局部哈希索引進行進一步的掃描，可以精確定位全部命中的數據。在進行精確查詢時，粗粒度索引文件只需一次IO即可被裝入內存。經過粗粒度索引過濾後，每個需要用局部哈希索引進行定位的數據塊也只需一次IO即可。在數億至數百億規模的數據量下進行測試，使用本發明所描述的索引，可以使平均查詢性能提升5倍以上。本發明相對於全局哈希索引方案，雖然查詢性能有所不及，但是其創建和維護代價更低，數據膨脹率也相對較低，雖然增加了粗粒度索引，但由於粗粒度索引的創建維護代價極低，其性能損失和數據膨脹幾乎可以忽略不計。查詢時，首先基於粗粒度索引進行過濾，多數情況下可以過濾掉一些DC，而這個過濾的I/O代價比起打開並掃描這些被過濾掉數據塊的本地哈希索引要小得多。本發明對於二維數據表的追加數據建立索引也非常簡單、便捷，對於新增加的數據也可以按照上述方法創建索引，對於新增加的數據可以分割成若干的塊，單獨為新增加的數據增加一個或多個的塊粗粒度索引及塊哈希索引，這樣無需對整個二維數據表的索引進行修改，維護代價很低。以上對本發明的一個實施例進行了詳細說明，但所述內容僅為本發明的較佳實施例，不能被認為用於限定本發明的實施範圍。凡依本發明申請範圍所作的均等變化與改進等，均應仍歸屬於本發明的專利涵蓋範圍之內。
權利要求
1.一種針對二維數據表的高效索引的創建方法，包括 1)將二維數據表分成若干的數據塊(DataCell，簡稱DC)； 2)為數據塊創建塊粗粒度索引； 3)為數據塊創建塊精確索引。
2.根據權利要求1所述的創建方法，其特徵在於所述的第3步驟中的塊局部索引為局部哈希索引。
3.根據權利要求1所述的創建方法，其特徵在於所述的第I步驟包括 O按一定行數將二維表進行水平切割； 2)按列將二維表進行垂直切割。
4.一種根據權利要求1所述的創建方法所創建的針對二維數據表的高效索引，所述的聞效索引包括 塊粗粒度索引，用以排除肯定不命中目標數據塊和確定肯定命中的目標數據塊； 塊局部精確索引，用以精確定位塊粗粒度索弓I無法精確判定的數據塊中命中數據的精確位置。
5.根據權利要求4所述的高效索引，其特徵在於所述塊局部精確索引為塊局部哈希索引。
6.根據權利要求4所述的高效索引，其特徵在於所述的高效索引包括至少一個的塊粗粒度索引和至少一個的塊局部精確索引。
7.根據權利要求4所述的高效索引，其特徵在於所述的粗粒度索引存儲針對塊的統計信息。
8.根據權利要求7所述的高效索引，其特徵在於所述的粗粒度索引存儲針對塊中數據的最大值和最小值。
9.一種根據權利要求4所述的針對二維數據表的高效索引的查詢方法，包括 1)根據粗粒度索引選出塊中肯定命中和排除肯定不命中的目標塊； 2)根據上一步篩選出的結果對於無法判定的目標塊用局部精確索引進行掃描，最終精確定位全部命中的數據。
全文摘要
本發明提供了一種針對二維數據表的高效索引，包括用以排除所屬塊的肯定不命中的目標的數據塊粗粒度索引和用以精確定位塊粗粒度索引無法精判定的數據塊中命中數據的塊精準索引。此外，本發明還提供了一種針對二維數據表的高效索引的創建及查詢方法。本發明的有益效果是能夠以較低的創建和維護代價來創建和維護二維數據表索引，同時索引數據膨脹率較小，I/O代價低，有效的提高了效率。
文檔編號G06F17/30GK103020305SQ20121059410
公開日2013年4月3日 申請日期2012年12月29日 優先權日2012年12月29日
發明者孟祥斌, 崔維力, 武新, 趙偉 申請人:天津南大通用數據技術有限公司