用於創建索引的方法和系統的製作方法

2023-12-04 03:50:36

專利名稱：用於創建索引的方法和系統的製作方法
技術領域：
本發明涉及資料庫領域。更確切的，本發明涉及資料庫領域中為資料庫創建索引的方法和系統。
背景技術：
隨著計算機技術的發展，資料庫的應用越來越廣泛，資料庫的容量也日益增長。為了對資料庫進行快速查詢，現有的資料庫管理系統通常為資料庫建立索引。索引是建立在資料庫表中的某些列的上面的。一般來說，在這些列上創建索引1)在經常需要搜索的列上，可以加快搜索的速度；幻在作為主鍵的列上，強制該列的唯一性和組織表中數據的排列結構；3)在經常用在連接的列上，這些列主要是一些外鍵，可以加快連接的速度；4)在經常需要根據範圍進行搜索的列上創建索引，因為索引已經排序，其指定的範圍是連續的；5) 在經常需要排序的列上創建索引，因為索引已經排序，這樣查詢可以利用索引的排序，加快排序查詢時間；6)在經常使用在WHERE子句中的列上面創建索引，加快條件的判斷速度，等寸。創建索引可以大大提高資料庫系統的性能。通過創建唯一性索引，可以保證資料庫表中每一行數據的唯一性，可以大大加快數據的檢索速度，還可以加速表和表之間的連接，特別是在實現數據的參考完整性方面特別有意義。在使用分組和排序子句進行數據檢索時，同樣可以顯著減少查詢中分組和排序的時間。通過使用索引，可以在查詢的過程中， 使用優化隱藏器，提高系統的性能。在現有的資料庫管理系統中，B+Tree索引是最常見的索引結構，默認建立的索引就是這種類型的索引。B+Tree索引是一種平衡樹，是基於二叉樹的，由根節點、中間節點和葉節點組成。根節點、中間節點和葉節點都位於索引頁中，統稱為索引節點。其中，不存在父親節點的是根節點，不存在子節點的是葉節點，位於根節點和葉節點之間的是中間節點。 其中，根節點存儲指向中間節點的指針；中間節點位於根節點和葉級節點之間，存儲指向下一級中間節點或葉節點的指針；而葉節點則存儲指向數據頁(即數據的物理存儲位置)的指針。一個資料庫查詢往往是多重的，假設有兩個表Tl和T2，其中Tl有兩個索引在第一列(coll)上的索引Tl_il以及在第二列(col2)上的索引Tl_i2,以如下查詢為例Select^from Tl,T2where Tl. coll = T2. coll and Tl. col2> = 60 and Tl. col2 =60 and Tl. col2 < 90掃描索引Tl_ i2獲得中間結果並將中間結果複製到內存或其他臨時的存儲位置中，這時，中間結果對應於表Tl中由第二列索引的第60行到第90行的內容。然後，利用該中間結果的第一列與表 T2的第一列進行匹配得到查詢結果。這時，由於表Tl的第一列(coll)上的索引Tl_il的葉節點中存儲的是指向原表Tl中數據的物理存儲位置的指針，而中間結果被複製到內存或其他臨時的存儲位置，因此，索引Tl_il中的指針對中間結果來說將變得無效。也就是
3說，中間結果不能利用索引Tl_il，因此，對中間結果只能進行全表遍歷。

發明內容
由於對於中間結果，已經存在的索引中的指針變得無效，索引帶來的好處將不能得到利用。而且，在大型企業應用中，資料庫表的容量往往很大，對資料庫表的全表遍歷將大量耗費計算資源。本公開的說明性實施例認識到現有技術中的缺點，提供了一種用於為資料庫創建索引的方法，包括選取資料庫表的至少一列作為創建索引的依據；根據該至少一列產生至少一個樹結構的索引，其中該至少一個索引的葉節點中存儲的指針為空值。根據本公開的另一方面，用於為資料庫創建索引的方法還包括如果有中間結果生成，則根據中間結果向葉節點中存儲的指針賦值，其中被賦值的葉節點中存儲的指針指向存儲中間結果的數據頁。根據本公開的另一方面，用於為資料庫創建索引的方法還包括響應於利用中間結果進行運算的完成，將葉節點中存儲的指針重置為空值。根據本公開的一個方面，提供了一種用於為資料庫創建索引的系統，包括選取部件，被配置用於選取資料庫表的至少一列作為創建索引的依據；產生部件，被配置用於根據該至少一列產生至少一個樹結構的索引，其中該至少一個的葉節點中存儲的指針為空。根據本公開的另一方面，用於為資料庫創建索引的系統還包括指針賦值部件，被配置用於如果有中間結果生成，則根據中間結果向葉節點中存儲的指針賦值，其中被賦值的葉節點中存儲的指針指向存儲中間結果的數據頁。根據本公開的另一方面，用於為資料庫創建索引的系統還包括指針重置部件，被配置為用於響應於利用中間結果進行運算的完成，將葉節點中存儲的指針重置為空值。根據本公開的方法和系統，產生的索引可以重複使用，而且，由於能夠利用索引對中間結果進行運算，也大大提高了資料庫操作的效率。


本公開可以通過參考下文中結合附圖所給出的描述而得到更好的理解，其中在所有附圖中使用了相同或相似的附圖標記來表示相同或者相似的部件。所述附圖連同下面的詳細說明一起包含在本說明書中並且形成本說明書的一部分，而且用來進一步舉例說明本公開的優選實施例和解釋本公開的原理和優點。在附圖中圖1顯示了根據本公開一個實施例的用於為資料庫創建索引的方法100 ；圖2示例性地顯示了索引的根節點、中間節點和葉節點生成的過程；圖3顯示了根據本公開一個實施例的用於為資料庫創建索引的系統300。
具體實施例方式在下文中將結合附圖對本公開的示範性實施例進行描述。為了清楚和簡明起見， 在說明書中並未描述實際實施方式的所有特徵。然而，應該了解，在開發任何這種實際實施例的過程中必須做出很多特定於該實際實施方式的決定，以便實現開發人員的具體目標， 例如，符合與系統及業務相關的那些限制條件，並且這些限制條件可能會隨著實施方式的不同而有所改變。此外，還應該了解，雖然開發工作有可能是非常複雜和費時的，但對得益於本公開公開內容的本領域技術人員來說，這種開發工作僅僅是例行的任務。在此，還需要說明的一點是，為了避免因不必要的細節而模糊了本公開，在附圖中僅僅示出了與根據本公開的方案密切相關的裝置結構和/或處理步驟，而省略了與本公開關係不大的其他細節。如背景技術部分描述的，現有的資料庫管理系統中，B+Tree索引是最常見的索引結構。下面，將以B+Tree作為示例對發明進行描述，但所屬領域技術人員知道，對於其他類型的索引，只要具有類似的結構都能應用本發明，利用B+Tree作為示例只是出於說明的目的，而不能作為對本發明的限制。下面參考圖1，其中顯示了根據本公開一個實施例的用於為資料庫創建索引的方法 100。如圖1所示，根據本公開一個實施例的用於為資料庫創建索引的方法100從步驟 102開始。接下來，方法100進入步驟104，其中，選取資料庫表的一列或多列作為創建索引的依據。這些列包括1)經常需要搜索的列上，可以加快搜索的速度；2)作為主鍵的列，強制該列的唯一性和組織表中數據的排列結構；3)經常用在連接的列，這些列主要是一些外鍵，可以加快連接的速度；4)經常需要根據範圍進行搜索的列，因為索引已經排序，其指定的範圍是連續的；5)經常需要排序的列，因為索引已經排序，這樣查詢可以利用索引的排序，加快排序查詢時間；6)經常使用在WHERE子句中的列，可以加快條件的判斷速度，等等。 然後，方法100進入步驟106，其中根據該一列或多列產生索引的根節點、中間節點以及葉節點，其中葉節點中存儲的指針為空值。下面結合圖h-2d，通過一個簡單的例子介紹生成索引的根節點、中間節點以及葉節點的過程，這裡需要說明，這裡只是一種示例性的介紹，除了這裡介紹的生成索引的根節點、中間節點以及葉節點的方式，還可以採用現有技術中的任何其他方式。同時，如何生成索引的根節點、中間節點以及葉節點不是本發明對現有技術做出的改進。假設所選取的列中有如下值40，59，60，66，70，72，73，75，76，78，80，83，86，90，···首先插入第一個值40生成根節點，然後產生根節點的子節點，在該子節點中，值 40作為其中的一個條目，如圖加所示。然後繼續插入後面一個值59。每個子節點中所能存儲的條目的數量有限，這裡假設該數量為M(M為一個預先定義的值)。這時，首先判斷值59插入到該子節點中是否會導致該子節點存儲的條目數量大於M，本例中值59的插入不會導致該子節點存儲的條目數量大於M，因此直接插入到該子節點中，如圖2b所示。然後，繼續插入後面一個值60。這時，仍需首先判斷值60插入到該子節點中是否會導致該子節點存儲的條目數量大於M，本例中值60的插入會導致該子節點存儲的條目數量大於M,這時，需要把該子節點分裂成兩個含有M/2個條目的節點。具體的做法是，創建一個新的節點，將原來節點後一半的值拷貝到新創建的節點。將新創建的節點的地址和含有的最小值寫入其父親節點。如圖2c所示。之後，繼續插入後面的值。如果在插入的過程中，把子節點分裂之後將新創建的節點所含有的最小值寫入其父親節點後，其父親節點條目的數量也大於M，則按照相似的方法分裂該父親節點，直到沒有節點需要分裂。如果根節點需要分裂，則需要加入一個節點作為該根節點的新的根節點(該根節點將作為新的根節點的子節點)。在將所有的值插入之後索引的結構如圖2d所示。以上示例性的介紹了生成索引的根節點、中間節點以及葉節點的過程。再次說明， 上面的介紹僅僅是示例性的，可以採用任何其他的方式來生成索引的根節點、中間節點以及葉節點。與現有技術不同的，根據本公開的一個實施例，生成的索引的葉節點中存儲的指針為空值(NULL)。至此，根據本公開一個實施例的方法用於為資料庫創建索引的方法100結束。圖1中還顯示了可選步驟108。在步驟108，如果有中間結果生成，則根據中間結果向葉節點中存儲的指針賦值，其中被賦值的葉節點中存儲的指針指向存儲中間結果的數據頁。資料庫管理系統在進行資料庫查詢時會將獲得中間結果複製到內存或其他臨時的存儲位置中。這時，如果有中間結果的產生，根據中間結果向葉節點中存儲的指針賦值，其中被賦值的葉節點中存儲的指針指向存儲中間結果的數據頁，即中間結果的物理存儲位置， 具體可能是存儲中間結果的內存，或者是其他臨時的存儲位置。具體地，從作為創建索引的依據的至少一列中確定需要利用中間結果進行下一步運算所涉及的列，並根據中間結果向所確定的列對應的索引的葉節點中存儲的指針賦值。仍以前面提到的查詢為例，其中表Tl有兩個索引在第一列(coll)上的索引Tl_ il以及在第二列(col2)上的索引Tl_i2 Select^from Tl, T2 where Tl. coll = Τ2· coll and Tl. col2 > = 60 and Tl. col2 =60 and Tl. col2 < 90，對第二列(col2) 上的索引Tl_i2進行掃描，以獲得中間結果並將中間結果複製到內存或其他臨時的存儲位置中。這時，中間結果對應於表Tl中由第二列索引的第60行到第90行的內容。根據本發明的一個實施例，首先從作為創建索引的依據的至少一列中確定需要利用中間結果進行下一步運算所涉及的列。在該查詢中，作為創建索引的依據的列是第一列(coll)和第二列 (col2)；資料庫管理系統需要利用該中間結果的第一列與表T2的第一列進行匹配以得到查詢結果。也就是說，需要利用中間結果進行下一步運算所涉及的列是第一列。然後，根據中間結果向所確定的列對應的索引的葉節點中存儲的指針賦值。對該查詢來說，就是向第一列(coll)對應的索引Tl_il』的葉節點中存儲的指針賦值。這時，被賦值的葉節點中存儲的指針指向存儲中間結果的數據頁，即中間結果(表Tl中由第二列索引的第60行到第 90行的內容)在內存或其他臨時的存儲位置中的物理存儲位置。經過上述賦值，根據前述方法創建的索引的葉節點中存儲的指針指向了存儲中間結果的數據頁，因此，可以利用經過賦值的索引對中間結果進行後續操作。現有技術中對於中間結果，已經存在的索引會變得無效。與之相比，根據本公開的方法，創建的索引的葉節點中存儲的指針經過賦值，指向了存儲中間結果的數據頁。因此， 中間結果可以用於進行後續的運算，從而大大提高了數據查詢的效率。
圖1中還顯示了可選步驟110。在步驟110，響應於利用中間結果進行運算的完成，將葉節點中存儲的指針重置為空值。這些運算包括合併(join)、過濾(filter)、排序 (order by)或分組(group by)等操作。當使用根據本公開的方法創建的索引利用中間結果進行上述運算完成之後，將葉節點中存儲的指針重置為空值。之後，如果再次生成中間結果，可以再次根據中間結果向已經重置指針的葉節點中存儲的指針再次賦值，即該索引可以被重複使用。現在參考圖3，其中顯示了根據本公開一個實施例的用於為資料庫創建索引的系統 300。如圖3所示，用於為資料庫創建索引的系統300包括選取部件302，被配置用於選取資料庫表的一列或多列作為創建索引的依據；產生部件304，被配置用於根據該一列或多列產生索引的根節點、中間節點以及葉節點，其中葉節點中存儲的指針為空。圖3還顯示了可選部件指針賦值部件306，，被配置用於如果有中間結果生成，則根據中間結果向葉節點中存儲的指針賦值，其中被賦值的葉節點中存儲的指針指向存儲中間結果的數據頁， 其中優選地，僅在中間結果對應的葉節點中插入指針；以及指針重置部件308，，被配置為用於響應於利用中間結果進行運算的完成，將葉級節點中存儲的指針重置為空值；其中運算包括合併、過濾、排序或分組操作。以上結合具體實施例描述了本公開的基本原理，但是，需要指出的是，對本領域的普通技術人員而言，能夠理解本公開的方法和裝置的全部或者任何步驟或者部件，可以在任何計算裝置(包括處理器、存儲介質等)或者計算裝置的網絡中，以硬體、固件、軟體或者它們的組合加以實現，這是本領域普通技術人員在閱讀了本公開的說明的情況下運用他們的基本編程技能就能實現的。因此，本公開的目的還可以通過在任何計算裝置上運行一個程序或者一組程序來實現。所述計算裝置可以是公知的通用裝置。因此，本公開的目的也可以僅僅通過提供包含實現所述方法或者裝置的程序代碼的程序產品來實現。也就是說，這樣的程序產品也構成本公開，並且存儲有這樣的程序產品的存儲介質也構成本公開。顯然，所述存儲介質可以是任何公知的存儲介質或者將來所開發出來的任何存儲介質。還需要指出的是，在本公開的裝置和方法中，顯然，各部件或各步驟是可以分解和 /或重新組合的。這些分解和/或重新組合應視為本公開的等效方案。並且，執行上述系列處理的步驟可以自然地按照說明的順序按時間順序執行，但是並不需要一定按照時間順序執行。某些步驟可以並行或彼此獨立地執行。雖然已經詳細說明了本公開及其優點，但是應當理解在不脫離由所附的權利要求所限定的本公開的精神和範圍的情況下可以進行各種改變、替代和變換。而且，本申請的術語「包括」、「包含」或者其任何其他變體意在涵蓋非排他性的包含，從而使得包括一系列要素的過程、方法、物品或者裝置不僅包括那些要素，而且還包括沒有明確列出的其他要素， 或者是還包括為這種過程、方法、物品或者裝置所固有的要素。在沒有更多限制的情況下，
由語句「包括一個......」限定的要素，並不排除在包括所述要素的過程、方法、物品或者裝
置中還存在另外的相同要素。
權利要求
1.一種用於為資料庫創建索引的方法，包括 選取資料庫表的至少一列作為創建索引的依據；根據該至少一列產生至少一個樹結構的索引，其中該至少一個索引的葉節點中存儲的指針為空值。
2.根據權利要求1的方法，還包括如果有中間結果生成，則根據中間結果向葉節點中存儲的指針賦值，其中被賦值的葉節點中存儲的指針指向存儲中間結果的數據頁。
3.根據權利要求2的方法，其中根據中間結果向葉節點中存儲的指針賦值包括 從作為創建索引的依據的至少一列中確定需要利用中間結果進行下一步運算所涉及的列；以及根據中間結果向所確定的列對應的索引的葉節點中存儲的指針賦值。
4.根據權利要求2的方法，還包括響應於利用中間結果進行運算的完成，將葉節點中存儲的指針重置為空值。
5.根據權利要求4的方法，其中 運算包括合併、過濾、排序或分組操作。
6.一種用於為資料庫創建索引的系統，包括選取部件，被配置用於選取資料庫表的至少一列作為創建索引的依據； 產生部件，被配置用於根據該至少一列產生至少一個樹結構的索引，其中該至少一個的葉節點中存儲的指針為空。
7.根據權利要求6的系統，還包括指針賦值部件，被配置用於如果有中間結果生成，則根據中間結果向葉節點中存儲的指針賦值，其中被賦值的葉節點中存儲的指針指向存儲中間結果的數據頁。
8.根據權利要求7的系統，其中產生部件用於從作為創建索引的依據的至少一列中確定需要利用中間結果進行下一步運算所涉及的列；以及根據中間結果向所確定的列對應的索引的葉節點中存儲的指針賦值。
9.根據權利要求7的系統，還包括指針重置部件，被配置為用於響應於利用中間結果進行運算的完成，將葉節點中存儲的指針重置為空值。
10.根據權利要求9的系統，其中 運算包括合併、過濾、排序或分組操作。
全文摘要
本公開公開了一種用於為資料庫創建索引的方法和系統，其中方法包括選取資料庫表的至少一列作為創建索引的依據；根據該至少一列產生至少一個樹結構的索引，其中該至少一個索引的葉節點中存儲的指針為空值。創建的索引可以重複使用，而且能夠使中間結果得到有效利用，進而能夠提高資料庫操作的效率。
文檔編號G06F17/30GK102207935SQ20101013697
公開日2011年10月5日 申請日期2010年3月30日 優先權日2010年3月30日
發明者張廣舟, 李海峰, 陳奇 申請人:國際商業機器公司