一種索引方法
2023-07-29 10:55:31 5
專利名稱：一種索引方法
技術領域：
本發明涉及數據處理技術領域，特別涉及一種索引方法。
背景技術：
隨著網際網路的高速發展，人們的信息來源得到了極大的豐富，信息獲取方式也隨之而改變，這給人類帶來機遇的同時也帶來挑戰，在Web信息成幾何基數增長的前提下，如何能夠快速準確的進行數據搜索，搜索到需要的東西，是數據處理技術領域研究的方向之
ο在數據搜索中，搜尋引擎sp i der得到越來越多的應用，sp i der是搜尋引擎的一個自動程序，其作用是抓取網際網路上的網頁，建立索引資料庫，使用戶能在搜尋引擎中搜索到相關網站的網頁。在具體實施過程中，spider每天要抓取大量網站連結，在抓取之前都需要獲取待抓取網站的IP位址以及robots等信息，這些信息不可能實時的從網際網路上查詢，而只能通過內部的域名伺服器DNS查詢。但是，由於DNS中存儲的數據量在不斷的增加，因此查詢速度也會隨之變慢，不能滿足快速查詢的需求。而且，對DNS中的數據進行更新時，也會增加DNS的工作量，這也影響了查詢的速度。同樣，在實時網頁資料庫以及其他關鍵字-數據值(Key-value)資料庫中也會遇到類似的問題。如何能夠更好的對數據進行查詢以及更新，滿足高性能的讀寫服務，是數據處理技術領域研究的方向之一。
發明內容
本發明所要解決的技術問題是提供一種索引方法，以節省索引的空間，提高內存的使用效率。本發明為解決技術問題而採用的技術方案是提供一種索引方法，包括a.對接收的關鍵字進行哈希運算，以從哈希桶表中確定對應的哈希桶，並從所述哈希桶中獲得哈希節點指針；b.利用所述哈希節點指針的前預定位從標識信息列表中確定對應的哈希節點數據塊識別信息；c.利用所述哈希節點指針的後預定位作為偏移量，從所述哈希節點數據塊識別信息對應的哈希節點數據塊中獲取對應的哈希節點。根據本發明之一優選實施例，所述哈希節點指針為4個字節，所述前預定位為所述哈希節點指針的前9位，所述後預定位為所述哈希節點指針的後23位。根據本發明之一優選實施例，所述哈希節點包括所述關鍵字、數據塊識別信息、數據項長度信息以及數據項偏移信息。根據本發明之一優選實施例，所述哈希節點進一步包括下一哈希節點指針，其中空閒的哈希節點通過所述下一哈希節點指針串成一個回收鍊表。根據本發明之一優選實施例，所述哈希節點為20個字節，其中所述關鍵字為8個字節、所述數據塊識別信息為2個字節、所述數據項長度信息為2個字節、所述數據項偏移信息為4個字節以及所述下一哈希節點指針為4個字節。根據本發明之一優選實施例，所述索引方法進一步包括d.根據所述數據塊識別信息查詢與所述數據塊識別信息對應的數據塊信息，所述數據塊信息包括數據塊狀態、內存指針以及固態存儲器文件描述符；e.根據所述數據塊狀態判斷對應數據塊位於內存還是位於固態存儲器。根據本發明之一優選實施例，所述索引方法進一步包括f.若所述數據塊位於所述內存，則根據所述內存指針、所述數據項偏移信息以及所述數據項長度信息讀取所述對應數據項。根據本發明之一優選實施例，所述索引方法進一步包括f.若所述數據塊位於所述固態存儲器，則根據所述固態存儲器文件描述符、所述數據項偏移信息以及所述數據項長度信息讀取所述對應數據項。由以上技術方案可以看出，本發明的索引方法通過間接哈希尋址節省了索引的空間，提高了內存的使用效率。
圖1是本發明實施例中的資料庫控制方法的流程示意圖；圖2是本發明實施例中的資料庫的存儲介質及存儲內容的示意圖；圖3是本發明實施例中的第一索引及數據塊的數據結構示意圖；圖4是本發明實施例中的第二索引的數據結構示意圖；圖5是本發明實施例中的哈希容器的結構示意圖；圖6是本發明實施例中的數據塊生命周期管理過程的示意圖；圖7是本發明實施例中的資料庫讀取操作的流程示意圖；圖8是本發明實施例中的資料庫寫入操作的流程示意圖；圖9是圖8中的步驟S809的具體流程示意圖；圖10是本發明實施例的資料庫導出操作的流程示意圖；圖11是本發明實施例中的資料庫控制裝置的結構示意圖。
具體實施例方式下面結合附圖和實施例對本發明進行詳細說明。請參閱圖1，圖1是本發明實施例中的資料庫控制方法的流程示意圖。在本實施例中，資料庫的控制方法主要包括以下幾個步驟步驟S101，接收操作信息。步驟S102，根據操作信息在位於內存的索引中查詢對應數據塊的索引信息。步驟S103，根據操作信息及索引信息對對應數據塊進行相應操作。在本發明中，操作信息可以包括具體操作指令以及待處理數據項或者待處理數據項的關鍵字。具體操作指令可以包括讀取操作指令、寫入操作指令、導出操作指令等，各種操作信息對應的具體操作過程將在下文中描述。請參閱圖2，圖2是本發明實施例中的資料庫的存儲介質及存儲內容的示意圖。在本實施例中，資料庫的存儲介質包括內存以及固態存儲器。存儲內容包括索引和數據塊。其中，數據塊根據不同狀態選擇性位於內存及固態存儲器中。具體來說，當數據塊位於內存中時可稱為內存數據塊，當數據塊位於固態存儲器中時可稱為固態存儲器數據塊。其中，索引設置在內存內，索引包括第一索引和第二索引。請參閱圖3-4，圖3是本發明實施例中的第一索引及數據塊的數據結構示意圖。圖 4是本發明實施例中的第二索引的數據結構示意圖。請參閱圖3，在本實施例中，第一索引用於記錄關鍵字與對應數據項的位置信息的映射關係。位置信息主要包括如下信息數據塊識別信息、數據項偏移信息以及數據項長度 fn息ο其中，數據塊識別信息用於記錄對應數據項所屬的數據塊的ID，數據項偏移信息用於記錄對應數據項在數據塊中的偏移量，數據項長度信息用於記錄對應數據項的長度。請參閱圖3，第二索引完成從位置信息中的數據塊識別信息到數據塊信息的映射。 請參閱圖4，在本實施例中，數據塊信息主要包括數據塊識別信息、數據塊長度信息、數據項總數、有效數據項個數、數據項有效位圖、數據塊狀態、內存數據塊容量、內存指針、固態存儲器文件描述符以及引用計數。其中，數據塊識別信息用於記錄數據塊的ID，在本實施例中，每個數據塊分配一個唯一的ID。數據塊長度信息用於記錄數據塊的大小。數據項總數用於記錄數據塊內的數據項的總個數。有效數據項個數用於記錄數據塊內的有效數據項的個數，即數據項總數減去被標記刪除的數據項的個數。數據項有效位圖用於記錄數據項的有效狀態，其中，每一位 (bit)代表一個數據項，若置1表示有效，置0表示被標記刪除。數據塊狀態用於記錄數據塊的狀態，主要用於判斷對應數據塊是位於內存中還是位於固態存儲器中，下文中將詳細描述各種數據塊狀態。內存數據塊容量用於記錄內存數據塊中已存儲的數據項的大小，主要用於與數據塊長度信息配合來判斷內存數據塊是否已滿。內存指針用於記錄數據塊在內存中的存儲位置，當數據塊不位於內存中時，則該值無效。固態存儲器文件描述符用於記錄數據塊在固態存儲器中的存儲位置，當數據塊不位於固態存儲器中時，則該值無效。引用計數用於記錄數據塊的引用狀態，用於管理數據塊的生存周期。在上述信息中，數據塊識別信息、數據塊長度信息、數據項總數、有效數據項個數、 數據項有效位圖為數據塊的核心數據項，稱為數據塊的元信息。請繼續參閱圖3，在數據塊中存儲多個數據項，每一數據項內存儲有如下內容數據項序號、關鍵字長度、數據值長度、關鍵字以及數據值。其中，數據項序號為數據項在數據塊中的序號，用於查找數據項有效位圖。關鍵字長度用於記錄關鍵字的長度。數據值長度用於記錄數據值的長度。關鍵字為表示關鍵字的二進位串。數據值為表示數據值的二進位串。在本發明中，第一索引和第二索引可通過本領域各種算法實現，例如哈希算法。本發明一優選實施例提供了一種間接尋址的哈希容器，節省了索引的空間，提高了內存的使用效率。下面將以第一索引為例，進行詳細描述。請參閱圖5，在本實施例中，第一索引包括一哈希桶表，該哈希桶表包括多個哈希桶。每一個哈希桶內存儲一哈希節點指針。在本實施例中，哈希節點指針為預定字節(例如，4位元組)，其中前預定位(例如，前9位)用於標識哈希節點所在的哈希節點數據塊，後CN 102541968 A預定位(例如，後23位)用於標識哈希節點在哈希節點數據塊內部的偏移。具體來說，所有的哈希節點數據塊的識別信息被記錄在標識信息列表中，並可根據哈希節點指針的前預定位從標識信息列表的對應位置查詢到對應的識別信息。在本實施例中，標識信息列表所能存儲的識別信息的最大數量為29 = 512。此外，哈希節點存儲在對應的哈希節點數據塊內，每個哈希節點佔用預定字節 (例如，20位元組)，分別包括關鍵字(例如，8個字節)、數據塊識別信息(例如，2個字節)、 數據項長度信息(例如，2個字節)、數據項偏移信息(例如，4個字節)以及下一哈希節點指針(例如，4個字節)。在上述哈希容器的使用過程中，首先對接收的關鍵字進行哈希運算從哈希桶表中確定對應的哈希桶，並從哈希桶中獲得哈希節點指針。隨後，利用哈希節點指針的前預定位從標識信息列表中確定對應的哈希節點數據塊的識別信息，並根據哈希節點指針的後預定位作為偏移量從識別信息對應的哈希節點數據塊中獲取對應的哈希節點，進而獲取與該關鍵字相關的數據項位置信息，例如數據塊識別信息、數據項偏移信息以及數據項長度信息。在本實施例中，每個哈希節點數據塊內能夠存儲的哈希節點的最大數量為223 = 8388608個，因此每個哈希容器可以支持的最大數據量為512X8388608 = 42億，很好的滿足了域名伺服器(Domain Name Server, DNS)的需求。此外，在該哈希容器中，空閒哈希節點用空閒鍊表維護。當數據被刪除時，對應的哈希節點也會被回收。空閒哈希節點通過哈希節點中的下一哈希節點指針來串成一個回收鍊表。當接收到新的數據時，優先使用回收鍊表中的指針。因此，哈希節點數據塊中的哈希節點數據總是緊湊的，在站點數量為3億的情況下，佔用的內存為300MX20bytes = 6Gbytes。請參閱圖6，圖6為本發明實施例中的數據塊生命周期管理過程的示意圖。在本實施例中，首先，在內存中創建數據塊。在創建數據塊後，為該數據塊分配唯一的數據塊識別信息(ID)，並將該數據塊的數據塊狀態標記為「內存」。隨後，更新第二索弓丨，以記錄該數據塊的數據塊信息，例如數據塊識別信息、數據塊長度信息、數據塊狀態以及內存指針等。其中，資料庫在任一時刻最多只有一個數據塊處於「內存」狀態。標記為「內存」的數據塊可接收待寫入數據項，並將該數據項追加到數據塊末端。 隨後，更新第二索引，以記錄有效數據項個數、數據項有效位圖、內存數據塊容量等。同時， 根據待寫入數據項的關鍵字及存儲位置更新第一索引，在第一索引中記錄該關鍵字與數據塊識別信息、數據項偏移信息以及數據項長度信息的映射關係，以便後續可根據該關鍵字查詢到對應的數據項。數據項一旦寫入數據塊後，就不可以更改，僅允許對該數據項進行讀取和標記刪除。當對該數據項進行標記刪除時，在第二索引中對該數據塊的數據塊信息的數據項有效位圖中的對應位進行標記，例如將對應位置0。當數據項不斷寫入數據塊後，可通過內存數據塊容量與數據塊長度信息的比較結果來判斷該數據塊是否寫滿。若數據塊寫滿，將該數據塊的數據塊狀態標記為「寫入」，並更新第二索引，以記錄數據項總數。隨後，將該數據塊寫入到固態存儲器中。優選地，在寫入過程中，將內存中該數據塊的數據項以受控的速率(例如，5MB/S)寫入到固態存儲器中，有效地防止了對讀取性能造成過大影響。同時，在內存中重新創建數據塊狀態標記為「內存」 的新數據塊，以接收後續寫入的數據項。
在「寫入」狀態的該數據塊的數據項全部寫入到固態存儲器後，將該數據塊的數據塊狀態標記為「固態存儲」，並釋放該數據塊原先佔用的內存緩衝空間。隨後，更新第二索弓丨，以記錄該數據塊的數據塊信息，例如固態存儲器文件描述符。如果處於「內存」狀態和「寫入」狀態的數據塊中的空洞太多，也就是說，數據塊中的有效數據項的個數低於閾值，則將該數據塊的數據塊狀態標記為「重建」。隨後，將標記為 「重建」的數據塊內的有效數據項轉存到標記為「內存」的新數據塊中，以實現對「重建」的數據塊內的無效數據項的清除及重建。在重建完成後，將標記為「重建」的數據塊的數據塊狀態標記為「刪除」。此時，根據該數據塊的引用計數判斷是否有其他線程引用該數據塊，如果沒有其他線程引用該數據塊，則刪除該數據塊。如果有其他線程引用該數據塊，則保留該數據塊，直到其他線程使用完成後，通過引用解除操作釋放該引用計數，再將該數據塊進行刪除。如果處於「固態存儲」狀態的數據塊中的空洞太多，則將該數據塊的數據塊狀態標記為「讀取」，並將該數據塊讀取到內存中。在讀取完成後，將該數據塊的數據塊狀態標記為 「重建」，並將該數據塊的有效數據項轉存到標記為「內存」的數據塊中，以實現對「重建」的數據塊內的無效數據項的清除及重建。在重建完成後，將標記為「重建」的數據塊的數據塊狀態標記為「刪除」。此時，根據該數據塊的引用計數判斷是否有其他線程引用該數據塊，如果沒有其他線程引用該數據塊，則刪除該數據塊。具體來說，如果數據塊狀態為「內存」、「寫入」以及「重建」，則表示該數據塊位於內存中。如果數據塊狀態為「固態存儲」以及「讀取」，則表示該數據塊位於固態存儲器中。透過上述操作，可有效管理數據塊生命周期。下面將結合具體實施例，描述本發明的各種操作過程。請參閱圖7，圖7為本發明實施例中的資料庫讀取操作的流程示意圖。在步驟S701中，接收讀取操作指令以及待讀取數據項的關鍵字。在步驟S702中，利用該關鍵字從第一索引查詢對應的位置信息。若未查詢到，則進行步驟S708 ；若查詢到，則進行步驟S703。在本實施例中，位置信息包括數據塊識別信息、數據項偏移信息以及數據項長度信息。具體查詢過程在上文中已經進行詳細描述，在此不再贅述。在步驟S703中，利用該位置信息中的數據塊識別信息從第二索引查詢對應的數據塊信息。在本實施例中，數據塊信息包括數據塊狀態、內存指針以及固態存儲器文件描述符等。在步驟S704中，根據數據塊狀態判定對應數據塊是位於內存中還是位於固態存儲器，若對應數據塊位於內存中，則進行步驟S705，若對應數據塊位於固態存儲器中，則進行步驟S706。如上文所描述的，如果數據塊狀態為「內存」、「寫入」以及「重建」，則表示該數據塊位於內存中。如果數據塊狀態為「固態存儲」以及「讀取」，則表示該數據塊位於固態存儲器中。在步驟S705中，根據內存指針、數據項偏移信息以及數據項長度信息在內存中讀取對應數據項。在步驟S706中，根據固態存儲器文件描述符、數據項偏移信息以及數據項長度信息在固態存儲器中讀取對應數據項。在步驟S707中，判斷對應數據項的關鍵字與待讀取數據項的關鍵字是否一致，若不一致，則進行步驟S708 ；若一致，則進行步驟S709。在步驟S708中，判定待讀取數據項不存在。在步驟S709中，判定讀取成功，並將對應數據項的數據值作為待讀取數據項的數據值。請參閱圖8，圖8為本發明實施例的資料庫寫入操作的流程示意圖。在步驟S801中，接收寫入操作指令以及待寫入數據項的關鍵字及數據值。在步驟S802中，利用該關鍵字從第一索引查詢對應的位置信息。若查詢到，則進行步驟S803 ；若沒有查詢到，則進行步驟S809。在本實施例中，位置信息包括數據塊識別信息、數據項偏移信息以及數據項長度信息。具體查詢過程在上文中已經進行詳細描述，在此不再贅述。在步驟S803中，利用該位置信息中的數據塊識別信息從第二索引查詢對應的數據塊信息。在本實施例中，數據塊信息包括數據塊狀態、內存指針以及固態存儲器文件描述符等。在步驟S804中，根據數據塊狀態判定對應數據塊位於內存中還是位於固態存儲器中，若對應數據塊位於內存中，則進行步驟S805，若對應數據塊位於固態存儲器中，則進行步驟S806。如上文所描述的，如果數據塊狀態為「內存」、「寫入」以及「重建」，則表示該數據塊位於內存中。如果數據塊狀態為「固態存儲」以及「讀取」，則表示該數據塊位於固態存儲器中。在步驟S805中，根據內存指針、數據項偏移信息以及數據項長度信息在內存中讀取對應數據項。在步驟S806中，根據固態存儲器文件描述符、數據項偏移信息以及數據項長度信息在固態存儲器中讀取對應數據項；在步驟S807中，判斷對應的數據項的數據值與待寫入數據項的數據值是否一致 若一致，則寫入成功；若不一致，則進行步驟S808 ；在步驟S808中，在對應數據項所屬數據塊的數據項有效位圖中將該對應數據項標識刪除。具體來說，在數據項有效位圖中將對應位置0。在步驟S809中，將待寫入數據項寫入位於內存中的用於接收待寫入數據項的數據塊內，即處於「內存」狀態的數據塊。隨後，更新第一索引及第二索引以記錄上述寫入過程。請參閱圖9，圖9是圖8中的步驟S809的具體流程示意圖。在步驟S901中，判斷內存中的處於「內存」狀態的數據塊是否已經寫滿，若未寫滿，則進行步驟S902，若寫滿，則進行步驟S903。具體來說，可通過數據塊長度信息與內存數據塊容量之間的比較結果來確定該數據塊是否寫滿。在步驟S902中，直接將待寫入數據項寫入到數據塊的末端，並更新第一索引及第
二索引。在步驟S903中，將該數據塊的數據塊狀態標記為「寫入」狀態。隨後，進入步驟S904和步驟S905。在步驟S904中，將該數據塊寫入固態存儲器，同時進一步更新第一索引及第二索引。在寫入完成後，將該數據塊的數據塊狀態改為「固態存儲」狀態，同時在內存中釋放該數據塊。在步驟S905中，創建標記為「內存」狀態的新數據塊，並將待寫入數據項寫入到新數據塊的末端，並更新第一索引及第二索引。通過上述方式，步驟S904和步驟S905可以並行進行，由此實現了讀寫分離。此外，處於「寫入」狀態的數據塊中的數據項以受控的速率寫入固態存儲器，譬如受控的速率為5MB/S。本發明通過設置受控的速率，有效地防止了寫入數據時對讀取性能造成的影響。請參閱圖10，圖10為本發明實施例的資料庫導出操作的流程示意圖。在步驟S1001中，接收導出操作指令。在步驟S1002中，對內存和固態存儲器進行加鎖，其中，在加鎖狀態下，禁止對內存和固態存儲器進行修改。在步驟S1003中，從內存的第二索引中複製待導出數據塊對應的元信息。在本實施例中，待導出數據塊可以是全部數據塊或者預定數量的數據塊。如上文所述的，元信息包括數據塊識別信息、數據塊長度信息、數據項總數、有效數據項個數以及數據項有效位圖。在步驟S1004中，對待導出數據塊的引用計數進行引用標記操作，以避免待導出數據塊被刪除。例如，對引用計數加一或加特定步長。在步驟S1005中，對內存和固態存儲器進行解鎖，其中，在解鎖狀態下，允許對內存和固態存儲器進行修改。由於元信息的複製時間很短，數據塊的後續導出可在後臺進行， 避免了影響數據塊的讀取及寫入操作。在步驟S1006中，將元信息寫入元信息文件。在步驟S1007中，根據元信息從內存或固態存儲器上讀取待導出數據塊，並根據待導出數據塊的關鍵字生成導出索引。在步驟S1008中，將導出索引寫入導出索引文件。在步驟S1009中，將待導出數據塊寫入數據塊文件。在本實施例中，元信息文件、 導出索引文件以及數據塊文件可在接到導出操作指令時創建，也可以在其他任意適當時刻創建。在步驟S1010中，對待導出數據塊的引用計數進行引用解除操作。例如，對引用計數減一或減特定步長。此時，如果數據塊已經處於「刪除」狀態，且沒有其他線程引用該數據塊，則刪除該數據塊。請參閱圖11，圖11為本發明實施例的資料庫控制裝置的結構示意圖。該控制裝置包括操作信息接收模塊1101、索引信息查詢模塊1102以及數據塊處理模塊1103。其中，操作信息接收模塊1101用於接收上述操作信息。索引信息查詢模塊1102用於根據上述操作信息在位於內存的索引中查詢對應數據塊的索引信息。在本實施例中，對應數據塊包括多個數據項，每一數據項包括關鍵字與數據值，並且對應數據塊可選擇性位於內存及固態存儲器中。數據塊處理模塊1103用於根據上述操作信息及索引信息對對應數據塊進行相應操作。
在具體實施過程中，索引包括上述的第一索引和第二索引。索引信息查詢模塊 1102根據第一索引查詢與關鍵字對應的位置信息，位置信息包括數據塊識別信息、數據項偏移信息以及數據項長度信息。索引信息查詢模塊1102進一步根據第二索引查詢與數據塊識別信息對應的數據塊信息，數據塊信息包括數據塊狀態、內存指針以及固態存儲器文件描述符等。關於資料庫控制裝置的詳細工作過程請參閱上文的描述，此處不再贅述。由以上技術方案可以看出，本發明的資料庫的控制方法及裝置以數據塊形式對多個數據項進行存儲，並根據不同狀態將數據塊選擇性存儲於內存及固態存儲中，進一步配合內存索引，可支持高性能讀寫操作，滿足了對數據的高性能隨機查詢與更新需求。在上述實施例中，僅對本發明進行了示範性描述，但是本領域技術人員在閱讀本專利申請後可以在不脫離本發明的精神和範圍的情況下對本發明進行各種修改。
權利要求
1.一種索引方法，其特徵在於，所述索引方法包括a.對接收的關鍵字進行哈希運算，以從哈希桶表中確定對應的哈希桶，並從所述哈希桶中獲得哈希節點指針；b.利用所述哈希節點指針的前預定位從標識信息列表中確定對應的哈希節點數據塊識別信息；c.利用所述哈希節點指針的後預定位作為偏移量，從所述哈希節點數據塊識別信息對應的哈希節點數據塊中獲取對應的哈希節點。
2.如權利要求1所述的方法，其特徵在於，所述哈希節點指針為4個字節，所述前預定位為所述哈希節點指針的前9位，所述後預定位為所述哈希節點指針的後23位。
3.如權利要求1所述的方法，其特徵在於，所述哈希節點包括所述關鍵字、數據塊識別信息、數據項長度信息以及數據項偏移信息。
4.如權利要求3所述的方法，其特徵在於，所述哈希節點進一步包括下一哈希節點指針，其中空閒的哈希節點通過所述下一哈希節點指針串成一個回收鍊表。
5.如權利要求4所述的方法，其特徵在於，所述哈希節點為20個字節，其中所述關鍵字為8個字節、所述數據塊識別信息為2個字節、所述數據項長度信息為2個字節、所述數據項偏移信息為4個字節以及所述下一哈希節點指針為4個字節。
6.如權利要求3所述的方法，其特徵在於，所述索引方法進一步包括d.根據所述數據塊識別信息查詢與所述數據塊識別信息對應的數據塊信息，所述數據塊信息包括數據塊狀態、內存指針以及固態存儲器文件描述符；e.根據所述數據塊狀態判斷對應數據塊位於內存還是位於固態存儲器。
7.如權利要求6所述的方法，其特徵在於，所述索引方法進一步包括f.若所述數據塊位於所述內存，則根據所述內存指針、所述數據項偏移信息以及所述數據項長度信息讀取所述對應數據項。
8.如權利要求6所述的方法，其特徵在於，所述索引方法進一步包括f.若所述數據塊位於所述固態存儲器，則根據所述固態存儲器文件描述符、所述數據項偏移信息以及所述數據項長度信息讀取所述對應數據項。
全文摘要
本發明提供了一種索引方法，包括對接收的關鍵字進行哈希運算，以從哈希桶表中確定對應的哈希桶，並從哈希桶中獲得哈希節點指針；利用哈希節點指針的前預定位從標識信息列表中確定對應的哈希節點數據塊識別信息；利用哈希節點指針的後預定位作為偏移量，從哈希節點數據塊識別信息對應的哈希節點數據塊中獲取對應的哈希節點。通過上述方式，本發明提供了一種間接尋址的哈希索引方法，節省了索引的空間，提高了內存的使用效率。
文檔編號G06F17/30GK102541968SQ201110036319
公開日2012年7月4日 申請日期2010年12月31日 優先權日2010年12月31日
發明者蔣錦鵬 申請人:百度在線網絡技術(北京)有限公司