《一種索引建立方法及系統、檢索方法及系統》是東軟集團股份有限公司於2013年9月9日申請的專利，該專利的公布號為CN103488709A，授權公布日為2014年1月1日，發明人是李東鴿、陳廷斌。
《一種索引建立方法及系統、檢索方法及系統》實施例提供一種索引建立方法及系統、檢索方法及系統，所述索引建立方法包括：採集伺服器將採集的真實數據存儲，根據真實數據的存儲位置生成索引數據；所述索引數據包括關鍵值；將索引數據按照關鍵值順序存入當前緩衝塊；將緩衝塊中的索引數據按照關鍵值順序連續的排列到索引塊中；將索引塊依次排列作為索引檔案；所述檢索方法包括：獲悉目標數據的關鍵值；以目標數據的關鍵值比較索引檔案中各索引塊的關鍵值範圍，確定一個關鍵值範圍涵蓋目標數據關鍵值的索引塊為目標索引塊；在目標索引塊中搜尋得到與目標數據關鍵值相等的索引數據，將該索引數據作為目標索引數據；從目標索引數據中提取目標數據的存儲位置，並從該存儲位置讀取目標數據。
2020年7月14日，《一種索引建立方法及系統、檢索方法及系統》獲得第二十一屆中國專利獎優秀獎。
（概述圖為《一種索引建立方法及系統、檢索方法及系統》摘要附圖）
基本介紹
- 中文名：一種索引建立方法及系統、檢索方法及系統
- 申請人：東軟集團股份有限公司
- 申請日：2013年9月9日
- 申請號：2013104062746
- 公布日：2014年1月1日
- 公布號：CN103488709A
- 發明人：李東鴿、陳廷斌
- 地址：遼寧省瀋陽市渾南新區新秀街2號
- Int. Cl.：G06F17/30(2006.01)I
- 代理機構：北京集佳智慧財產權代理有限公司
- 代理人：王寶筠
- 類別：發明專利
專利背景,發明內容,專利目的,技術方案,有益效果,附圖說明,技術領域,權利要求,實施方式,榮譽表彰,
專利背景
數據採集過程可以概括為將數據從源伺服器採集到目標伺服器的過程，而對於現階段大規模的數據採集，往往需要一個專門的採集伺服器來完成這一過程。這也就必然導致了採集伺服器中數據流量極為龐大。於是在分散式多表關聯採集、變化數據比對、業務代碼替換等存在數據查詢和檢索需求場景下，能夠快速的查詢和檢索匹配數據便成為一項亟待解決的新問題。
在2013年之前的技術中，一般採用快取技術實現快速的查詢和檢索，也就是將查詢頻率較高的數據快取在記憶體中以便快速檢索。不過採集伺服器的數據流往往達到上百GB甚至更高的級別，遠遠大於現階段伺服器的記憶體容量。所以能夠快取在記憶體中的數據僅僅為一小部分；絕大部分必須存儲在採集伺服器的硬碟中。
如果需要檢索存儲在硬碟中的數據，則採集伺服器中數據必然要在檢索過程中進行頻繁的記憶體/硬碟切換，速度非常緩慢；甚至相比於從存在索引的源伺服器中直接進行檢索，檢索採集伺服器硬碟的過程還要更慢。可見利用快取技術在採集伺服器中進行檢索的技術方案由於速度慢、效率低，很難滿足實際使用的需求。
發明內容
專利目的
《一種索引建立方法及系統、檢索方法及系統》的目的在於提供一種索引建立方法及系統、檢索方法及系統，所述方法通過為採集伺服器硬碟中的真實數據建立索引以實現高效快速的檢索。
技術方案
一種索引建立方法，所述方法包括：採集伺服器將採集的真實數據存儲，並根據真實數據的存儲位置生成索引數據；所述索引數據包括關鍵值；將索引數據按照關鍵值順序存入當前緩衝塊；將緩衝塊中的索引數據按照關鍵值順序連續的排列到索引塊中；將索引塊依次排列作為索引檔案。
所述索引數據包括：真實數據的存儲位置、長度、壓縮狀態信息以及關鍵值；所述關鍵值為利用哈希算法對真實數據的特徵值進行計算得到的哈希值。
所述將採集的真實數據存儲具體為：採集一個真實數據，判斷該真實數據的體積是否超過壓縮閾值，若超過則對真實數據進行壓縮；將未經壓縮的或壓縮後的真實數據存入當前數據塊。
所述緩衝塊具體包括：緩衝塊狀態、緩衝塊體積、索引數據、最大關鍵值和最小關鍵值。
所述緩衝塊中的索引數據按照關鍵值順序連續的排列到索引塊中具體為：設定索引塊數量，並分配當前索引塊，重複的歷便所有緩衝塊當前的最大關鍵值或最小關鍵值；提取當前所有緩衝塊中最大的最大關鍵值或最小的最小關鍵值對應的索引數據，並寫入當前索引塊中首位，若首位占用則寫入到前一次寫入的索引數據之後；修改被提取索引數據的緩衝塊的最大關鍵值或最小關鍵值；直到所有索引數據均被寫入索引塊中停止寫入。
所述設定索引塊數量具體為：設定比較最佳化公式，所述比較最佳化公式為
；t為檢索比較次數，n為索引數據的總數，b為索引塊的總數，t、n、b均為自然數；當b=b’使t為最小值，則b’為索引塊參考數量；將索引塊參考數量設定為索引塊數量。
所述索引數據按關鍵值順序連續排列作為索引檔案具體為：將索引塊依次排列作為索引檔案。
所述方法還包括：採集伺服器將索引檔案快取至記憶體，並備份至硬碟。
一種索引建立系統，所述系統具體包括：數據存儲模組，用於將採集的真實數據存儲；生成模組，用於根據真實數據的存儲位置生成索引數據；所述索引數據包括關鍵值；緩衝模組，用於將索引數據按照關鍵值順序存入當前緩衝塊；索引製作模組，用於將緩衝塊中的索引數據按照關鍵值順序連續的排列到索引塊中，將索引塊依次排列作為索引檔案。
一種檢索方法，所述方法包括以下步驟：獲悉目標數據的關鍵值；以目標數據的關鍵值比較索引檔案中各索引塊的關鍵值範圍，確定一個關鍵值範圍涵蓋目標數據關鍵值的索引塊為目標索引塊；在目標索引塊中搜尋得到與目標數據關鍵值相等的索引數據，將該索引數據作為目標索引數據；從目標索引數據中提取目標數據的存儲位置，並從該存儲位置讀取目標數據。
一種檢索系統，所述系統具體包括：關鍵值模組，用於獲悉目標數據的關鍵值；索引塊比較模組，用於以目標數據的關鍵值比較索引檔案中各索引塊的關鍵值範圍，確定一個關鍵值範圍涵蓋目標數據關鍵值的索引塊為目標索引塊；索引數據比較模組，用於在目標索引塊中搜尋得到與目標數據關鍵值相等的索引數據，將該索引數據作為目標索引數據；數據讀取模組，用於從目標索引數據中提取目標數據的存儲位置，並從該存儲位置讀取目標數據。
有益效果
《一種索引建立方法及系統、檢索方法及系統》存在的有益效果是：通過為真實數據建立索引檔案，再通過對應的檢索方法實現基於索引檔案快速完成對於真實數據的檢索；由於索引檔案本身體積小，針對性強的特點，所以讀取並利用索引檔案進行檢索相比於直接從硬碟中搜尋真實檔案，在效率上有著本質上的提高，充分的滿足使用需求，避免了2013年之前的技術中直接從硬碟搜尋真實數據速度慢、效率低的缺陷；另外，通過將索引檔案保存在記憶體中可實現在檢索過程中高效快速讀取索引檔案進行檢索；所述方法還計算得到索引塊的最優數量，進一步的減少了檢索過程中的比較次數，提高了檢索的速度。
附圖說明
圖1為《一種索引建立方法及系統、檢索方法及系統》實施例所述索引建立方法流程圖；
圖2為《一種索引建立方法及系統、檢索方法及系統》實施例所述真實數據分塊存儲方法流程圖；
圖3～4為《一種索引建立方法及系統、檢索方法及系統》實施例所述緩衝塊示意圖；
圖5為《一種索引建立方法及系統、檢索方法及系統》實施例所述索引塊示意圖；
圖6為《一種索引建立方法及系統、檢索方法及系統》實施例所述索引建立系統結構示意圖；
圖7為《一種索引建立方法及系統、檢索方法及系統》實施例所述檢索方法流程圖；
圖8為《一種索引建立方法及系統、檢索方法及系統》實施例所述檢索系統結構示意圖。
技術領域
《一種索引建立方法及系統、檢索方法及系統》涉及數據處理技術領域，特別涉及一種索引建立方法及系統、檢索方法及系統。
權利要求
1.一種索引建立方法，其特徵在於，所述方法包括：採集伺服器將採集的真實數據存儲，並根據真實數據的存儲位置生成索引數據；所述索引數據包括關鍵值；將索引數據按照關鍵值順序存入當前緩衝塊；將緩衝塊中的索引數據按照關鍵值順序連續的排列到索引塊中；將索引塊依次排列作為索引檔案。
2.根據權利要求1所述方法，其特徵在於，所述索引數據包括：真實數據的存儲位置、長度、壓縮狀態信息以及關鍵值；所述關鍵值為利用哈希算法對真實數據的特徵值進行計算得到的哈希值。
3.根據權利要求1所述方法，其特徵在於，所述將採集的真實數據存儲具體為：採集一個真實數據，判斷該真實數據的體積是否超過壓縮閾值，若超過則對真實數據進行壓縮；將未經壓縮的或壓縮後的真實數據存入當前數據塊。
4.根據權利要求1所述方法，其特徵在於，所述緩衝塊具體包括：緩衝塊狀態、緩衝塊體積、索引數據、最大關鍵值和最小關鍵值。
5.根據權利要求4所述方法，其特徵在於，所述緩衝塊中的索引數據按照關鍵值順序連續的排列到索引塊中具體為：設定索引塊數量，並分配當前索引塊，重複的歷便所有緩衝塊當前的最大關鍵值或最小關鍵值；提取當前所有緩衝塊中最大的最大關鍵值或最小的最小關鍵值對應的索引數據，並寫入當前索引塊中首位，若首位占用則寫入到前一次寫入的索引數據之後；修改被提取索引數據的緩衝塊的最大關鍵值或最小關鍵值；直到所有索引數據均被寫入索引塊中停止寫入。
6.根據權利要求5所述方法，其特徵在於，所述設定索引塊數量具體為：設定比較最佳化公式，所述比較最佳化公式為；t為檢索比較次數，n為索引數據的總數，b為索引塊的總數，t、n、b均為自然數；當b=b’使t為最小值，則b’為索引塊參考數量；將索引塊參考數量設定為索引塊數量。
7.根據權利要求1-6任意一項所述方法，其特徵在於，所述索引數據按關鍵值順序連續排列作為索引檔案具體為：將索引塊依次排列作為索引檔案。
8.根據權利要求1-6任意一項所述方法，其特徵在於，所述方法還包括：採集伺服器將索引檔案快取至記憶體，並備份至硬碟。
9.一種索引建立系統，其特徵在於，所述系統具體包括：數據存儲模組，用於將採集的真實數據存儲；生成模組，用於根據真實數據的存儲位置生成索引數據；所述索引數據包括關鍵值；緩衝模組，用於將索引數據按照關鍵值順序存入當前緩衝塊；索引製作模組，用於將緩衝塊中的索引數據按照關鍵值順序連續的排列到索引塊中，將索引塊依次排列作為索引檔案。
10.一種檢索方法，其特徵在於，所述方法包括以下步驟：獲悉目標數據的關鍵值；以目標數據的關鍵值比較索引檔案中各索引塊的關鍵值範圍，確定一個關鍵值範圍涵蓋目標數據關鍵值的索引塊為目標索引塊；在目標索引塊中搜尋得到與目標數據關鍵值相等的索引數據，將該索引數據作為目標索引數據；從目標索引數據中提取目標數據的存儲位置，並從該存儲位置讀取目標數據。
11.一種檢索系統，其特徵在於，所述系統具體包括：關鍵值模組，用於獲悉目標數據的關鍵值；索引塊比較模組，用於以目標數據的關鍵值比較索引檔案中各索引塊的關鍵值範圍，確定一個關鍵值範圍涵蓋目標數據關鍵值的索引塊為目標索引塊；索引數據比較模組，用於在目標索引塊中搜尋得到與目標數據關鍵值相等的索引數據，將該索引數據作為目標索引數據；數據讀取模組，用於從目標索引數據中提取目標數據的存儲位置，並從該存儲位置讀取目標數據。
實施方式
參見圖1所示為《一種索引建立方法及系統、檢索方法及系統》所述索引建立方法的一個具體實施例，該實施例中所述方法具體包括以下步驟：
步驟101、採集伺服器將採集的真實數據存儲。
在建立索引之前，所有的真實數據必須被採集伺服器存儲在自身的硬碟中，以使得每個真實數據都具有一個固定的存儲位置。顯然真實數據準確固定的存儲位置是檢索的基礎，該實施例利用索引檔案進行檢索的意義正是獲悉真實數據準確的存儲位置。
具體的，該實施例中將按照圖2所示方法對真實數據進行分塊存儲，包括以下步驟：
步驟A1、採集一個真實數據，判斷該真實數據的體積是否超過壓縮閾值，若超過則對真實數據進行壓縮。
真實數據的存儲是隨著採集伺服器的數據採集同時進行的，進行存儲的順序也就是採集順序；也就是每採集到一個真實數據，便針對該真實數據執行該實施例所述的存儲流程。
為節省存儲空間，所述存儲流程中的步驟A1主要判斷真實數據是否需要被壓縮。也就是預設一個壓縮閾值，體積大於壓縮閾值的真實數據均需要被壓縮。若真實數據的體積大小超過了壓縮閾值則需先對真實數據進行壓縮再進入步驟A2，否則直接進入步驟A2。該實施例中所述壓縮閾值為1KB。
步驟A2、將未經壓縮的或壓縮後的真實數據存入當前數據塊。
該步驟為真實數據（包括未壓縮和壓縮後的真實數據）實際進行存儲的過程。真實數據的存儲在該實施例中以數據塊作為基本單位，也就是先分配一個數據塊，將陸續採集到的真實數據存儲到該數據塊中，直到該數據塊存滿則再分配另一個數據塊。所謂當前數據塊這一概念指的就是已經被分配、即將或正在被存入真實數據的數據塊。
該步驟中如果要將真實數據存入當前數據塊，首先將判斷是否存在當前數據塊，若存在進而在判斷當前數據塊的剩餘空間是否足夠存儲該真實數據。若存在當前數據塊且當前數據塊中存在足夠的存儲空間，則將該真實數據存入當前數據塊中，否則分配一個新數據塊作為當前數據塊。該實施例中每個數據塊的存儲容量均為10MB。
步驟102、根據真實數據的存儲位置生成真實數據的索引數據，所述索引數據包括關鍵值。
索引數據是該實施例中建立索引檔案最基本的單位。一個索引數據中顯示了一個真實數據的存儲位置。另外，為了索引檔案的排序乃至後續的檢索等其他需要，該實施例中索引檔案中除了包括真實數據的存儲位置之外，還包括真實數據的長度及壓縮狀態信息（所述壓縮狀態信息顯示真實數據在存儲時是否被壓縮）以及關鍵值。
需要說明的是，該實施例中真實數據作為數據檔案，本身即存在一個表明其唯一身份的特徵值。所述索引數據的關鍵值是以哈希算法對真實數據的特徵值計算映射得到的哈希值。索引數據可以用關鍵值表明自身的唯一身份，同時關鍵值和特徵值的映射關係也明確了索引數據與真實數據的對應關係，以便在檢索中將二者匹配對應，某個索引數據必然顯示與其關鍵值相同的真實數據的存儲位置。而且關鍵值也是索引數據排列順序的標準。具體將在該實施例中後續公開。
該實施例中，所述索引數據的數據格式可以參考表1：
表1
其中，key代表關鍵值；position代表真實數據存儲位置；compress代表壓縮狀態信息；valueLength代表真實數據長度。
步驟103、將索引數據按照關鍵值順序存入當前緩衝塊。
顯而易見的是，如需利用索引檔案檢索真實數據的位置進而讀取真實數據，那么索引檔案中的每個索引數據必然需要有序的進行排列，方能夠體現出利用索引檔案進行檢索高效快速的優點。在該實施例中，以關鍵值為標準進行索引數據的排列。
前述已知，關鍵值即真實數據的特徵值的哈希值。該實施例並不對採集伺服器本身做出改變，所以從採集伺服器本身的特性上來講，採集伺服器採集並存儲真實數據具有其特定的方式和次序，並不是按照哈希值的順序依次進行的；進而仿照存儲順序生成的索引數據必然也是亂序的，所以無法直接將其製成按照關鍵值順序連續排列的索引檔案，而是需暫時將索引數據存入緩衝塊當中，以便後續的整體排序和組合。
將索引數據存入緩衝塊的過程類似於將真實數據存入數據塊的過程。也就是先分配一個緩衝塊，將陸續生成的索引數據存儲到該緩衝塊中，直到該緩衝塊存滿則再分配另一個緩衝塊。所謂當前緩衝塊這一概念指的就是已經被分配、即將或正在被存入索引數據的緩衝塊。該實施例中根據使用需求可以設定每個緩衝塊存儲10萬個索引數據。
所謂將索引數據按照關鍵值順序存入指的就是，即便陸續生成的索引數據的關鍵值是亂序的，但是在緩衝塊內部依然需保證其順序。實際上，所述關鍵值以數字表示，而從數據書寫結構上來講，該實施例中將確保緩衝塊內索引數據按照特定順序排列。該實施例中該特定順序具體是從左至右升序排列。
圖3～4為將一個索引數據存入緩衝塊的流程示意圖。圖3～4中每個方格代表一個索引數據，方格中數字則代表該索引數據的關鍵值。圖3中可見若干索引數據已經排列在緩衝塊中，其關鍵值雖不連續，但依舊是按照從左至右升序的規律進行排列。當生成了一個關鍵值為73的索引數據，則按照同樣規律需將其寫入到56和107兩個索引數據中間，即箭頭指向的位置處。
該實施例中可將關鍵值為107的索引數據及其右側全部索引數據統統右移一個位置，使得56和107兩個索引數據中間出現一個空位，然後將關鍵值為73的索引數據寫入該空位中。寫入之後的狀態如圖4所示。
緩衝塊的數據結構如表2所示：
表2
其中，inc表示緩衝塊的狀態，即顯示緩衝塊中已存入多少索引數據，剩餘多少空間；size表示緩衝塊占用的體積；indexs為索引數據的集合，可以認為圖3～4所表示的就是indexs部分；maxKey表示該緩衝塊中最大（即最右側）的關鍵值，圖3～4中為896；minKey表示該緩衝塊中最小（即最左側）的關鍵值，圖3～4中為2。
步驟104、將緩衝塊中的索引數據按照關鍵值順序連續的排列到索引塊中。
當所有的索引數據均已生成，也就是所有真實數據均已存儲的情況之下，則開始將緩衝塊中的索引數據按照關鍵值的順序，以連續排列的方式整理到索引塊當中。
整理方法如下：
設定索引塊數量，並分配當前索引塊，重複的歷便所有緩衝塊當前的最大關鍵值或最小關鍵值；提取當前所有緩衝塊中最大的最大關鍵值或最小的最小關鍵值對應的索引數據，並寫入當前索引塊中首位，若首位占用則寫入到前一次寫入的索引數據之後；修改被提取索引數據的緩衝塊的最大關鍵值或最小關鍵值；直到所有索引數據均被寫入索引塊中停止寫入。
也就是說，首先設定索引塊的數量，並推算出每個索引塊中應儲存的索引數據的數量。假設索引塊的數量為b，而索引數據的總數為n，顯然每個索引塊中索引數據的數量m=n/b（m、n、b均為自然數）。
該實施例中假設關鍵值由數字1起始，那么關鍵值為1的索引數據將作為第1個索引塊中的第1個索引數據。那么必然的，關鍵值為1的索引數據保存在某一個緩衝塊當中，該緩衝塊的minKey為1。或者說假如歷便所有緩衝塊的minKey，必將搜尋到一個minKey為1的緩衝塊，關鍵值為1的索引數據就保存在該緩衝塊當中。
該實施例中首先分配一個預先設定好的索引塊當前索引塊，然後歷便所有緩衝塊的minKey，發現緩衝塊A的minKey為1，則從緩衝塊A中提取關鍵值為1的索引數據，將該索引數據寫入當前索引塊中。同理再找到關鍵值為2的索引數據，將其寫在索引塊中關鍵值為1的索引數據之後；以此類推，實現索引數據在索引塊中連續的排列。
需要說明的是，對於被提取了minKey對應的索引數據的緩衝塊，其當前的minKey必然增大。如圖4所示的緩衝塊，原本minKey為2，但如果關鍵值為2的索引數據被提取，那么其當前的minKey實際上為8。所以相應的還必須設定一個minKey變更的機制，以便該緩衝塊下一次被提取索引數據。就是說，如圖4所示的緩衝塊，當關鍵值為2的索引數據被提取之後，必須立刻將緩衝塊數據結構中minKey一項的數值變更為其實際值8。假如該緩衝塊的minKey始終為2不作調整，則無法通過minKey搜尋到關鍵值為8的索引數據。可見在該實施例中，實時的變更minKey是獲取關鍵值連續的索引數據的必要步驟。
為適應minKey變更的需求，此處對索引數據的數據結構對照表1稍作修改，如表3：
表3
表3相比表1增加了isDelete項，該項代表刪除標識符，刪除標識符可存在0或1中情況，O代表未刪除，1代表已刪除；若一個索引數據已被提取並寫入索引塊，則該索引數據刪除標識符由O變為1；緩衝塊中將不再以刪除標識符為1的索引數據的關鍵值作為minKey，而是將其下一個刪除標識符為O的索引數據的關鍵值變更為minKey。
以此類推，當一個索引塊中已被寫入了m個關鍵值連續的索引數據，則再分配一個索引塊繼前一索引塊之後接著搜尋索引數據並寫入。直到n個索引數據均寫入到索引塊當中，則結束該步驟，也就得到b個已經完成寫入的索引塊。參照圖5為該實施例中已經完成寫入的第一個索引塊，其中按照順序寫入了關鍵值為1～m的共m個索引數據，下一索引塊將從關鍵值為m+1的索引數據繼續寫入。
步驟104中以歷便minKey為例實現了按照關鍵值順序將索引數據寫入索引塊，同理還可以採用歷便maxKey的方式，依然能夠達到相同的效果，該實施例中不再重複敘述。
索引塊的數據結構依然可以參考表2所示，或者也可以採取類似的結構。不過為在檢索過程中準確的定位出某個索引數據所在的索引塊，索引塊同樣需要標明自身的maxKey和minKey，以便明確該索引塊覆蓋的關鍵值範圍。
需要強調的是，該實施例中所述“關鍵值的連續”未必等同於數學概念上自然數的連續。也可能在某些情況下，將有若干不存在的關鍵值數值，這並不影響所謂關鍵值的連續。例如，正常來講某三個連續的關鍵值應該是55、56、57；但可能由於某些原因，使得採集伺服器中原本不存在關鍵值為56的真實數據，那么也就必然不存在關鍵值為56的索引數據；則在這種情況下，該位置連續的三個關鍵值就是55、57、58；不過只要數學上缺失的關鍵值並沒有在索引檔案中出現，即認為此處是連續的。
該實施例中還需要說明的是，索引塊的數量b可以由操作人員自行設定，不過在該實施例中為了進一步的提高檢索效率，將按照以下最佳化算法來確定：
基於檢索過程的比較次數計算，可得到如下比較最佳化公式：（公式1）；其中，t代表檢索比較次數，n、b與前述一致，n代表索引數據的總數，b代表索引塊的總數，t、n、b均為自然數。相關的檢索步驟涉及二分檢索方法，公式1的推導也與所述二分檢索法有關，其原理將在後續實施例中具體的公開，此處不作贅述。
針對公式1來講，提高檢索效率便是儘可能的降低檢索比較次數，也就是期望t能夠達到最小值。公式1中n為常數，b是取值範圍在1～n中任意自然數的變數。也就是說索引塊的數量最少為1個，最多與索引數據的數量相等，即n個；不過此間眾多數值當中，將有b=b’使得t達到最小值，那么b’也就是b的最優值，也成為索引塊參考數量，該實施例中將索引塊參考數量設定為索引塊數量。
在計算過程中，可以採用窮舉的方式，將b=1～n共n個自然數解依次代入到公式1中，從而發現使t達到最小值的最優解b’，也可以根據公式1繪製函式曲線，選取函式曲線上距離t的最小值最近的整點作為b’。
步驟105、將索引塊依次排列作為索引檔案。
索引塊按照寫入的順序，同樣也就是涵蓋的關鍵值從小到大的順序組合為一個整體的數據檔案，即是最終的索引檔案。
步驟106、採集伺服器將索引檔案快取至記憶體，並備份至硬碟。
在得到索引檔案之後，該實施例中需要將所述索引檔案快取在記憶體中，以便在檢索過程中可以直接讀取，從而快速的找到某個真實數據的存儲位置。一般而言索引檔案體積較小，並不會占用大量的記憶體空間，所以利用索引檔案檢索真實數據存儲位置的方案具有良好的使用價值。而為了提高索引檔案的安全性，該實施例中還將另外備份一份索引檔案並將其保存在採集伺服器的硬碟當中。如果出現記憶體中索引檔案被損壞的情況，即可將硬碟中備份的索引檔案快速的裝載到記憶體，以避免重新製作索引檔案的過程。
對應圖1所示的方法實施例，該實施例中進一步公開一種索引建立系統，圖1所示實施例中所述的索引建立方法將基於該實施例所述系統得以實施。二者技術方案在本質上一致，圖1所示實施例中的各項說明同樣適用於該實施例中。參見圖6所示，所述系統具體包括：
數據存儲模組，用於將採集的真實數據存儲；生成模組，用於根據真實數據的存儲位置生成索引數據；所述索引數據包括關鍵值；緩衝模組，用於將索引數據按照關鍵值順序存入當前緩衝塊；索引製作模組，用於將緩衝塊中的索引數據按照關鍵值順序連續的排列到索引塊中，將索引塊依次排列作為索引檔案。
通過圖1所示的索引建立方法建立了索引檔案之後，相應的還需要一種檢索方法與之配合，方可以實現對於真實數據的檢索。參見圖7所示為一種檢索方法的具體實施例，該實施例中所述方法針對前述的索引檔案進行檢索，具體包括以下步驟：
步驟701、獲悉目標數據的關鍵值。
該實施例中，所謂目標數據也就是待檢索的真實數據。換言之，所述檢索過程的目的就在於獲得目標數據在硬碟中的存儲位置，並進一步的讀取該目標數據。由於在《一種索引建立方法及系統、檢索方法及系統》中索引數據是按照關鍵值的順序進行排列，那么對應的檢索也同樣必須是針對關鍵值的檢索。
所以，獲悉目標數據的關鍵值即成為了所述檢索方法的首要步驟。在該實施例中對應前述的關鍵值的生成方法，當採集伺服器獲得了一個待檢索的目標數據的相關信息，則利用哈希算法得到該目標數據的關鍵值。
步驟702、以目標數據的關鍵值比較索引檔案中各索引塊的關鍵值範圍，確定一個關鍵值範圍涵蓋目標數據關鍵值的索引塊為目標索引塊。
基於前述實施例，所述索引檔案包括一個或多個索引塊，每個索引塊中包括若干連續排列的索引檔案，索引塊中索引檔案關鍵值的集合也就是索引塊的關鍵值範圍。由於索引數據已經按照關鍵值連續的排列，索引塊可以標明自身的minKey和maxKey，那么minKey到maxKey區間內的關鍵值均在該索引塊的關鍵值範圍之內。
對於目標數據的檢索，需要首先確定與其關鍵值相同的索引數據位於哪個索引塊中。該實施例中的具體方式就是用目標數據的關鍵值依次與各索引塊的關鍵值範圍比較，必定可以發現某一個索引塊的關鍵值範圍覆蓋了目標數據的關鍵值。那么與目標數據關鍵值相同的索引數據一定存在於該索引塊中，進而將該索引塊作為目標索引塊以執行後續檢索流程。
例如，某個索引檔案中共包括4個索引塊，關鍵值範圍分別是：索引塊1（1～100）、索引塊2（101～200），索引塊3（201～300），索引塊4（301～400）。當目標數據的關鍵值為226，那么依次比較可發現，索引塊3（201～300）的關鍵值範圍覆蓋了目標數據的關鍵值226，將索引塊3作為目標索引塊。
否則若所有索引塊的關鍵值範圍均未能覆蓋目標數據的關鍵值，則說明索引檔案中不存在與該目標數據關鍵值相同的索引檔案，也就是說明該目標數據沒有保存在採集伺服器當中，即檢索失敗。同樣參照上述實例，假如目標數據的關鍵值為524，則超出了索引檔案整體覆蓋的關鍵值範圍，說明索引檔案中不存在關鍵值為524的索引數據。
步驟703、在目標索引塊中搜尋得到與目標數據關鍵值相等的索引數據，將該索引數據作為目標索引數據。
既定目標索引塊之後，則歷便目標索引塊中索引數據必然能夠發現一個索引數據的關鍵值與目標數據相等，則該索引數據就是該次檢索的目標索引數據，目標索引數據中記錄了目標數據在採集伺服器硬碟中存儲的位置。
需要說明的是，在該步驟中，從目標索引塊中搜尋到目標索引數據的具體方式可以採用二分檢索法。所謂二分檢索法是現階段廣泛採用的一種可以提高檢索效率的檢索方法，但根據其特性必須建立在索引檔案有序排列的基礎之上，該實施例中便具備套用條件。二分檢索法的原理為已經為該領域技術人員所公知，此處不再給出具體的定義，僅從以下實例中給予體現：
按前述實例，當目標數據的關鍵值為226，索引塊3（201～300）被確定為目標索引塊，則按照二分檢索法的檢索過程如下；
先取目標索引塊關鍵值範圍的中間值即250，並以中間值為限將原關鍵值範圍劃分為（201～250）和（250～300）兩部分。比較目標數據的關鍵值與該中間值有226＜250，則推斷目標索引數據位於關鍵值範圍劃分後的前一部分（201～250）當中，由此保留了索引塊中一半的索引數據進一步檢索，另一半直接捨去。進而再取（201～250）的中間值225，並將（201～250）的範圍劃分為（201～225）和（225～250）兩部分；再次得到226＞225，則推斷目標索引數據位於再次劃分後的後一部分（225～250）當中。以此類推，不斷的選取範圍內中間值進行比較，就可以每次保留原範圍中一半的索引數據進行下一次的比較檢索，直到發現目標索引數據。如假設目標數據的關鍵值為225，那么在第2次比較時有225=225，即說明發現了目標索引數據。
步驟702～步驟703為通過數值比較找到目標索引數據的過程，也是檢索過程的核心步驟。而這一過程中的比較次數同樣對檢索的效率有著重要的影響所謂比較次數包括兩部分，一為發現目標索引塊的過程，二為發現目標索引數據的過程。可以想像，兩個過程的比較次數應該是此消彼長的。參考圖1所示實施例中的描述，索引塊的數量為b，索引數據的總數為n，顯然每個索引塊中索引數據的數量m=n/b。也就是說當索引數據的總數一定，那么如果索引塊數量較少則每個索引塊中的索引數據數量就必然較多。這樣發現目標索引塊需要的比較次數必然較少，但是在目標索引塊中發現目標索引數據所需的比較次數便較多；反之同理。
《一種索引建立方法及系統、檢索方法及系統》中便設計了如下的最佳化算法，以將發現目標索引數據的比較次數降到最低限度。
通過數學原理可以得到，當索引塊數量為b，那么通過比較發現目標索引塊的比較次數也最多為b。當目標索引塊中索引數據的數量為m，則在目標索引塊中發現目標索引數據的比較次數k最多為：
；則有總比較次數
，即得到前述公式1。
通過公式1可以進行最佳化計算，得到b=b’使得t達到最小值，從而找到最優的索引塊數量以及每個索引塊包括的索引數據數量。以上說明從檢索過程的角度出發，描述了推導得出公式1的原理；利用公式1進行最佳化計算的具體方式在前述實施例中已經給出了明確的說明，此處不再贅述。
步驟704、從目標索引數據中提取目標數據的存儲位置，並從該存儲位置讀取目標數據。
顯然，目標數據（待檢索的真實數據）的關鍵值與目標索引數據一致，則說明目標索引數據中記錄的真實數據存儲位置即目標數據所在的位置。獲悉該存儲位置之後，進一步從該位置中讀取目標數據，便實現了檢索的最終目的，完成了檢索過程。
對應圖7所示的方法實施例，該實施例中進一步公開一種檢索系統，圖7所示實施例中所述的檢索方法將基於該實施例所述系統得以實施。二者技術方案在本質上一致，圖7所示實施例中的各項說明同樣適用於該實施例中。參見圖8所示，所述系統具體包括：
關鍵值模組，用於獲悉目標數據的關鍵值；索引塊比較模組，用於以目標數據的關鍵值比較索引檔案中各索引塊的關鍵值範圍，確定一個關鍵值範圍涵蓋目標數據關鍵值的索引塊為目標索引塊；索引數據比較模組，用於在目標索引塊中搜尋得到與目標數據關鍵值相等的索引數據，將該索引數據作為目標索引數據；數據讀取模組，用於從目標索引數據中提取目標數據的存儲位置，並從該存儲位置讀取目標數據。
榮譽表彰
2020年7月14日，《一種索引建立方法及系統、檢索方法及系統》獲得第二十一屆中國專利獎優秀獎。
