[發明專利]建立數據索引的方法、利用該索引查詢數據的方法和系統

在審

• 申請號: 201010261159.0
• 申請日: 2010-08-24
• 公開（公告）號: CN102375852A
• 公開（公告）日: 2012-03-14
• 發明（設計）人: 錢嶺;齊驥;郭磊濤;周大;羅治國;孫少陵;張松波;張衛平
• 申請（專利權）人: 中國移動通信集團公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京英賽嘉華知識產權代理有限責任公司 11204
• 代理人: 余朦;王艷春

技術領域

本申請涉及一種在數據庫中建立數據索引的方法、以及利用該索引查詢數據的方法。本申請還涉及一種數據庫查詢系統。

背景技術

數據庫系統的邏輯結構中，主要包括上層的結構化查詢語言(SQL)層和底層的存儲引擎層。其中SQL層主要負責各種數據庫操作的流程和處理。存儲引擎層實現底層的數據存取的實際操作，包括數據的組織、存儲、索引等。在數據的組織和存儲方面，一般將數據通過操作系統的文件系統存儲在磁盤上的文件中。為了有效地管理存儲空間和便于存取，一般將這些存儲空間分成多個存儲頁(Page)，包括數據頁和索引頁，一個數據頁一般可以存儲多條數據記錄(行)。

在數據庫表中的數據量很多時，采用簡單的掃描匹配方式所獲得的性能往往無法滿足用戶的查詢要求，而影響查詢性能的主要因素是查詢操作須訪問的數據量和磁盤I/O量。在數據庫實現中，索引是常用的優化查詢性能的重要技術手段。通常狀況下，由于索引記錄僅包含索引鍵值以及很短的指針，索引實體比真實的數據要小很多。一個索引頁可以存儲數量更多的索引記錄，這意味著在索引中查找時在I/O上占很大的優勢。而且索引可以組織成支持快速查找的數據結構，如B-TREE查找樹、HASH表等典型的數據結構。在查詢時，根據查詢條件，首先從索引中查找得到數據記錄的存儲位置，再從這些存儲位置定位讀取出數據記錄，可以大大減少查詢時須訪問的數據量和磁盤I/O量，因此提高查詢性能。數據庫系統中常用的索引類型如B-TREE索引、HASH索引等，分別適用于不同的場合，它們的原理基本上都是通過查詢的索引鍵值來快速定位數據記錄的存儲位置。

一條索引記錄中包含的基本信息包括：索引鍵值(即定義索引時指定的所有字段的值)+邏輯指針(指向數據記錄的位置)。在使用數據庫時，用戶可以根據查詢需求，在數據表的某個或某幾個列上建立適當的索引。在數據庫中，對于在數據表中出現的每個索引鍵值，在索引中建立該鍵值對應的每條數據記錄的邏輯指針(這里用RID表示，可以表示為對應數據頁的ID+記錄偏移量)的列表。這樣，只要在索引中快速查找到匹配的索引鍵值，就可以獲得和該鍵值對應的數據記錄的邏輯指針列表。

以電信業務中的CDR數據表為例，一條CDR記錄中一般包含用戶號碼(UserId)、時間標簽(Timestamp)、對方號碼(PeerId)等參數。一個CDR表的數據量一般非常大，例如有幾億條記錄。常用的查詢之一是查詢某個用戶的CDR記錄，這就需要對用戶號碼(UserId)字段建立索引。圖1示出了為某CDR數據表的用戶號碼(UserId)字段建立的一個普通的B+TREE索引結構及其對應的數據結構的一部分。這是一個密集索引，在數據頁150的上一級索引頁110中為每一條數據記錄建立了一條索引記錄。索引的葉子結點中包含索引鍵值及指向數據頁中數據記錄的邏輯指針，其記錄數量與數據表數據記錄數量一致。索引頁100中的索引記錄組成B+TREE結構。例如查找用戶號碼13500002的記錄，首先從根索引頁1001查到下一級索引頁1007，再到葉子索引頁1132，最后得到該用戶號碼對應的RID只有一個<1409，2>，即數據頁1409中偏移量為2的記錄。

如果在圖1的索引結構中查找用戶號碼13600001的記錄，則會按照相似的流程定位到葉子索引頁1153，因為用戶號碼13600001在數據頁1428中有400條數據記錄，相應地在索引頁1153中也有400條索引記錄。在實際的CDR數據集中，這種高密度的數據記錄出現的可能性比較大。這樣由多條索引記錄逐條定位和隨機讀取數據記錄的效率可能比在指定數據頁中順序掃描還慢。

因此，需要本領域中需要迫切需要能夠解決上述技術問題的數據庫檢索方案。

發明內容

一方面，本申請公開了一種在數據庫中查詢數據的方法，其中，所述數據庫包括用來存儲數據的多個單位存儲空間，所述方法包括：

接收數據查詢指令并確定所述數據查詢指令中包括的索引鍵值；

確定所述索引鍵值是用于近似索引還是精確索引；

如果確定的結果是所述索引鍵值是用于近似索引，則通過所述索引鍵值，從所述近似索引在單位存儲空間中標識的位置開始掃描查詢數據記錄，

如果確定的結果是所述索引鍵值是用于精確索引，則通過所述索引鍵值在所述單位存儲空間中標識的位置處查詢數據記錄。

另一方面，本申請還公開了一種數據庫查詢系統，包括：