數據查詢方法和裝置的製作方法

2023-04-27 21:45:31 1

專利名稱：數據查詢方法和裝置的製作方法
技術領域：
本發明屬於數據處理技術，尤其涉及一種數據查詢方法和裝置。
背景技術：
隨著無線傳感器網絡的發展，傳感數據量也急劇增長，把傳感數據在傳感器本地 存儲，實現以數據為中心的傳感器網絡已成為傳感器網絡的一個研究熱點。現有的傳感 器節點的存儲能力有限，如低端的MicaZ節點只有512kByte，高端的Imote2節點也僅有 32MByte存儲，且能量有限，主要是電池供電。因此NAND快閃記憶體以其容量大，體積小，成本低， 能耗低的特點，是現在嵌入式系統大容量存儲擴展的首選，然而NAND快閃記憶體的讀寫擦除及壽 命又有其獨特的特點以頁為單位讀寫；以塊為單位擦除，且每次寫一個用過的頁之前必 須擦除其所在的塊；NAND快閃記憶體的總的擦除次數有限為10000 100000次，因此傳統的數據 索引系統無法在NAND快閃記憶體上有效的工作，這為傳感器存儲擴展提出了挑戰，現有針對NAND 快閃記憶體在嵌入式系統中的應用的研究工作主要集中在(1)能耗優化能耗幾乎所有的快閃記憶體傳感器索引或文件系統都要考慮的問題，現有技術中由微軟 研究院提出的高效節能的傳感器數據索引系統Flash Logger，它為存儲和運算能力有限的 傳感器節點設計了一個新穎的數據結構有效地組織和壓縮了存儲在快閃記憶體中的數據，並且能 夠有效的對壓縮的數據進行索引和查詢。(2)主存空間優化傳感器節點的內存也是一個非常有限的資源，在現有的方法中，只有麻省大學的 Capsule系統和微軟研究院的Flash Logger系統在設計中考慮了節點內存空間的使用優 化問題。Capsule採用了硬體抽象層，隱藏了從應用程式到快閃記憶體之間的數據操作，並使用日 志索引結構設計以及寫入緩存來提高主存使用效率。Flash Logger的主存優化後的代碼 使用大約500行nesC語言構成，共佔用Moteiv公司的Tmote Sky節點大約14KB ROM和 1. 5KB RAM 空間。(3)時序數據優化針對無線傳感網絡時序數據本身的特點，目前僅有Flash Logger提供了簡單的特 定的時間範圍內檢索壓縮過的時序數據的功能，但是，其實驗的結果表明隨著時間窗口的 增量查詢成本明顯增加，所以可以說並沒有針對時序數據進行針對性的優化。然而，在無線傳感器節點利用有限的主存空間支持大容量的NAND快閃記憶體方面的研 究中，針對海量數據進行查詢時對速度，能耗的要求越來越高，目前應用NAND快閃記憶體的傳感 器網絡沒有根據傳感器數據的時序特性來進行數據查詢，也沒有根據NAND快閃記憶體的讀寫擦 除和壽命特徵對數據的查詢系統做進一步地優化。

發明內容
針對現有技術的上述缺陷，本發明實施例提供一種數據查詢方法和裝置。
本發明實施例提供一種數據查詢方法，包括在向存儲模塊的主存中的寫入緩存區寫數據的過程中，獲取所述寫入緩存區寫滿 數據時的時間；將所述寫入緩存區中的數據以頁為單位存儲到所述存儲模塊的NAND快閃記憶體中；接收所述NAND快閃記憶體返回的存儲所述數據的頁地址，建立包括所述時間和所述頁 地址對應關係的時間日誌並存儲在所述存儲模塊，供以時間為索引進行數據查詢。本發明實施例提供一種數據查詢裝置，包括存儲模塊、獲取模塊和處理模塊，其 中，所述存儲模塊包括主存和NAND快閃記憶體，所述主存中包括寫入緩存區和讀取緩存區，其中，所述獲取模塊，用於在向所述寫入緩存區寫數據的過程中，獲取所述寫入緩存區 寫滿數據時的時間；處理模塊，用於將所述寫入緩存區中的數據以頁為單位存儲到所述NAND快閃記憶體中， 並接收所述NAND快閃記憶體返回的存儲所述數據的頁地址，建立包括所述時間和所述頁地址對 應關係的時間日誌，並存儲在所述存儲模塊中；查詢模塊，用於以時間為索引進行數據查詢。本發明實施例提供的數據查詢方法和裝置，通過根據數據的時序性特點，建立包 括寫入緩存區寫滿數據的時間和將寫滿的數據存儲到NAND快閃記憶體中的頁地址對應關係的時 間日誌，實現了對具有時序特性的數據，以時間為索引進行查詢對應的數據，大大提高了數 據查詢的速度。


圖1為本發明數據查詢方法實施例流程圖；圖2為本發明數據查詢方法實施例中以時間為索引進行數據查詢的流程圖；圖3為本發明數據查詢方法實施例中數據查詢過程中時間比較次數和扇出係數 的關係示意圖；圖4為本發明數據查詢方法實施例中級聯樹索引結構示意圖；圖5為本發明數據查詢裝置實施例結構示意圖；圖6為本發明數據查詢裝置另一實施例結構示意圖。
具體實施例方式為使本發明實施例的目的、技術方案和優點更加清楚，下面將結合本發明實施例 中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例是 本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員 在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。本發明針對現有技術中應用NAND快閃記憶體的傳感器網絡並沒有根據傳感器數據的時 序特性來進行數據查詢，也沒有根據NAND快閃記憶體的讀寫擦除和壽命特徵對數據的查詢系統 做進一步地優化等缺陷，提出了一種解決方案即通過根據數據的時序性特點，建立包括寫 入緩存區寫滿數據的時間和將寫入緩存區中寫滿的數據存儲到NAND快閃記憶體中的頁地址對應 關係的時間日誌，實現了對具有時序特性的數據，以時間為索引進行查詢對應的數據，大大 提高了數據查詢的速度。
圖1為本發明數據查詢方法實施例流程圖，如圖1所示，該方法包括步驟100，在向存儲模塊的主存中的寫入緩存區寫數據的過程中，獲取所述寫入緩 存區寫滿數據時的時間；在向存儲模塊的主存中的寫入緩存區寫數據的過程中，每當數據裝滿一個寫入緩 存區，就把寫入緩存區中最後寫入數據的時間提取出來用做整個寫入緩存區所寫入的數據 的標記。步驟101，將所述寫入緩存區中的數據以頁為單位存儲到所述存儲模塊的NAND閃 存中；把寫滿的寫入緩存區中的數據以頁為單位存儲到存儲模塊的NAND快閃記憶體中。步驟102，接收所述NAND快閃記憶體返回的存儲所述數據的頁地址，建立包括所述時間 和所述頁地址對應關係的時間日誌並存儲在所述存儲模塊，供以時間為索引進行數據查 詢。NAND快閃記憶體返回存儲寫入緩存區中數據的頁地址後，建立包括用於標記寫入緩存區 寫滿數據時的時間和存儲寫入緩存區中數據的頁地址對應關係的時間日誌，並將時間日誌 存儲在存儲模塊中，供以時間為索引進行數據查詢，可有效的支持無論是對時間點還是對 時間區間內寫入的數據進行查詢，具體地，當時間日誌存儲在存儲模塊的主存空間裡，以時 間為索引進行數據查詢時，查詢速度非常快，但是佔用的主存空間比較大；當時間日誌存儲 在存儲模塊的NAND快閃記憶體中，以時間為索引進行數據查詢時，每次都要訪問NAND快閃記憶體，查詢 速度較慢，但是節約了有限的主存空間。本實施例提供的數據查詢方法，通過根據數據的時序性特點，建立包括寫入緩存 區寫滿數據的時間和將寫入緩存區中寫滿的數據存儲到NAND快閃記憶體中的頁地址對應關係的 時間日誌，實現了對具有時序特性的數據，以時間為索引進行查詢對應的數據，大大提高了 數據查詢的速度。進一步地，根據NAND快閃記憶體以頁為單位的特殊讀寫特性，根據具體應用的NAND閃 存，將寫入緩存區的容量設置為NAND快閃記憶體的頁容量，在寫入緩存區寫滿數據時，以頁為單 位存儲到存儲模塊的NAND快閃記憶體晶片中，在NAND快閃記憶體中剛好存儲了一頁，提高了 NAND快閃記憶體 存儲空間的利用率。基於上述實施例，圖2為本發明數據查詢方法實施例中以時間為索引進行數據查 詢的流程圖，如圖2所示，具體步驟包括步驟200，接收輸入的查詢時間以獲取在所述查詢時間內存儲到所述存儲模塊中 的數據；輸入查詢時間可以為時間點或者時間段，查詢時間點或者時間段內存儲到存儲模 塊中NAND快閃記憶體中的數據；步驟201，查詢所述主存中的寫入緩存區中存儲的數據所對應的時間，若判斷獲知 不包含所述查詢時間，則根據所述存儲模塊中存儲的所述時間日誌獲取包含所述查詢時間 的時間日誌，並獲取存儲所述數據的頁地址。首先查詢主存中寫入緩存區存儲的數據所對應的時間是否包含輸入的查詢時間， 如果要查詢的數據在寫入緩存區中，則直接讀取到讀取緩存區，如果沒有包含輸入的查詢 時間，則根據存儲模塊中存儲的時間日誌，可以在主存中或者NAND快閃記憶體中獲取包含查詢時間的時間日誌，找到與查詢時間對應的頁地址。步驟202，根據所述頁地址以頁為單位從所述NAND快閃記憶體中讀取所述數據到所述主 存中的讀取緩存區並獲取在所述查詢時間內存儲的數據。根據獲取的頁地址，從NAND快閃記憶體中以頁為單位將數據讀取到主存中的讀取緩存 區並獲取在查詢時間內存儲的數據。本實施例提供的數據查詢方法，通過根據輸入的查詢時間從時間日誌的索引中獲 取對應的時間日誌，從而獲得存儲數據的頁地址，實現了對具有時序特性的數據，以時間為 索引進行查詢對應的數據，大大提高了數據查詢的速度。基於上述實施例，將建立的包括寫入緩存區寫滿數據的時間和將寫入緩存區中寫 滿的數據存儲到NAND快閃記憶體中的頁地址對應關係的時間日誌通過樹結構的方式存儲到存儲 模塊中，具體的樹結構可以為小扇出係數非平衡樹結構、大扇出係數非平衡樹結構、小扇出 係數平衡樹結構或大扇出係數平衡樹結構。進一步地，將時間日誌通過樹結構的方式存儲到存儲模塊的主存中具體包括設置子樹扇出係數和子樹索引數組的長度，構造以時間為索引進行數據查詢的子 樹索引數組，構造的子樹索引數組的層數是根據對子樹索引數組的長度取子樹扇出係數為 底的對數而獲得的，子樹索引數組的底層用於存儲時間日誌，其餘層是根據設置的子樹扇 出係數來存儲底層存儲的時間日誌中所包含的時間，用於將輸入的查詢時間與子樹索引數 組中的時間進行比較，快速、準確的獲取包含查詢時間的時間日誌。構造子樹索引數組的過程中關於子樹扇出係數和子樹索引數組的長度的設置與 以時間為索引進行數據查詢時進行時間比較的次數有關，圖3為本發明數據查詢方法實施 例中數據查詢過程中時間比較次數和扇出係數的關係示意圖，如圖3所示，橫坐標為扇出 係數，縱坐標為平均比較次數，四條曲線分別為子樹索引數組的長度分別為8M，1M，256K和 IK個時間日誌時在不同的扇出係數下所對應的平均比較次數，針對不同的子樹索引數組的 長度，比較次數都隨著子樹扇出係數的增長而明顯增加，如果扇出係數設置過大，則每次比 較都要訪問主存，消耗時間和能量，在設計時儘量選用小扇出係數，而小扇出係數的子樹索 引數組的平衡結構頻繁分裂，索引空間利用率只有50%，由於主存空間資源有限，多採用非 平衡樹的子樹索引數組結構，因此，構造小扇出係數非平衡樹結構的子樹索引數組既保證 每次查找的比較次數少又避免了樹節點頻繁分裂導致主存空間利用率較低的問題。若判斷獲知主存中正在寫入的子樹索引數組的底層中已存儲的時間日誌的個數 沒有達到設置的子樹索引數組的長度，則將新生成的時間日誌繼續存儲到該子樹索引數組 的底層；如果判斷獲知該子樹索引數組的底層已存儲的時間日誌的個數已經達到設置的子 樹索引數組的長度，則在主存中生成新的子樹索引數組以存儲新生成的時間日誌。本實施例提供的數據查詢方法，通過根據數據的時序性特點，建立包括寫入緩存 區寫滿數據的時間和將寫入緩存區中寫滿的數據存儲到NAND快閃記憶體中的頁地址對應關係的 時間日誌，並在主存中以子樹索引數組的方式存儲時間日誌，實現了對具有時序特性的數 據，以時間為索引在主存中通過與子樹索引數組中的時間進行比較後獲得包含查詢時間的 時間日誌，並獲取對應的數據，減少了訪問主存空間的次數，進一步提高了查詢數據的速 度。基於上述實施例，由於主存空間有限，可以採用級聯樹索引結構，進一步地將子樹索引數組的長度設置為NAND快閃記憶體中每塊存儲區所包含的頁數的整數倍，將時間日誌通過 級聯樹索引結構的方式存儲到存儲模塊具體包括設置根樹扇出係數和根樹索引數組的長度構造用於以時間為索引進行子樹日誌 查詢獲取對應的子樹索引數組的根樹索引數組，根樹索引數組的長度為NAND快閃記憶體中的總 頁數除以子樹索引數組的長度而獲得的，根樹索引數組中存儲的子樹日誌的個數達到子樹 索引數組的長度時，NAND快閃記憶體中的存儲空間剛好存滿數據，對根樹索引數組的長度取根樹 扇出係數為底的對數獲取根樹索引數組的層數，根樹索引數組的底層用於存儲子樹日誌， 其餘的層是根據根樹扇出係數來存儲子樹日誌中所包含的時間。在將時間日誌存儲到主存中的子樹索引數組底層的過程中，若判斷獲知主存中正 在寫入的子樹索引數組的底層中已存儲的時間日誌的個數已經達到子樹索引數組的長度 減一，就停止向該子樹索引數組存儲時間日誌，獲取最後一個存儲到該子樹索引數組底層 上的時間日誌中的時間，並將該子樹索弓I數組存儲到存儲模塊的NAND快閃記憶體中，其中，該子 樹索引數組的存儲容量小於或等於NAND快閃記憶體中的頁容量。接收NAND快閃記憶體返回的存儲子樹索引數組的頁地址，根據最後一個存儲到子樹索 引數組中的時間日誌中的時間和NAND快閃記憶體返回的存儲時間日誌的頁地址的對應關係生成 子樹日誌並存儲在主存中的根樹索引數組的底層，供以時間為索引進行子樹日誌查詢。進一步地，為了進一步減少對主存空間的消耗，在存儲子樹索引數組和根數索引 數組時，可以只存儲其葉子層節點即底層數據，也就是在主存中只存儲根樹索引數組中底 層的子樹日誌和正在寫入的子樹索引數組底層的時間日誌，在NAND快閃記憶體中只存儲整個寫 滿的子樹索引數組中底層的時間日誌，在查詢數據時，其餘層上存儲的時間通過底層的時 間日誌和/或子樹日誌，根據子樹扇出係數和/或根樹扇出係數通過樹結構算法來虛擬出 樹狀邏輯結構獲得其餘層的時間，使系統在查詢數據時和在一棵完整的子樹索引數組和/ 或根數索引數組中查詢效率相同，通過虛擬樹狀邏輯結構跟存儲整個完整的樹狀邏輯結構 相比能有效減少主存消耗25%左右(當扇出係數為4時)。圖4為本發明數據查詢方法實施例中級聯樹索引結構示意圖，如圖4所示，系統運 行時存放在主存中的根樹索引數組以及正在寫入的子樹索引數組，將寫滿的子樹索引數組 裡的時間日誌存放在NAND快閃記憶體中相應的子樹索引裡，其中，子樹索引數組的底層存放了時 間日誌，包括了寫入緩存區寫滿數據的時間和頁地址(子樹索引數組底層的箭頭所指，未 示出)的對應關係，其餘層存儲時間日誌中的時間用於獲取與查詢時間對應的數據所存儲 的頁地址，根樹索引數組的底層存放了子樹日誌，包括了存放子樹索引數組的時間和頁地 址(根樹索引數組底層的箭頭所指，未示出)的對應關係，其餘層存儲子樹日誌中的時間用 於獲取查詢與查詢時間對應的時間日誌所存儲的頁地址，具體以4作為子樹索引數組和根 樹索引數組的扇出係數為例，子樹索引數組的底層中每4個時間日誌為一組，將每組中的 最後一個時間日誌中的時間寫入上一層，以此類推，根樹索引數組的底層中每4個子樹日 志為一組，將每組中的最後一個子樹日誌中的時間寫入上一層，以此類推，若查詢時間為3， 與根樹索引數組中存儲的時間從上到下的進行比較，判斷出比20小，則獲取包含時間20的 子樹日誌，根據與20對應的頁地址，從NAND快閃記憶體中獲取對應的存儲時間日誌的子樹索引數 組，在主存中與讀取出的子樹索引數組中存儲的時間從上到下的進行比較，並判斷出3比5 小，找到對應的第1組時間日誌，包含3的時間日誌就在第一組中，快速準確的獲取對應的時間日誌，再根據時間日誌中的頁地址從NAND快閃記憶體中讀取數據。本實施例提供的數據查詢方法，通過根據數據的時序性特點，建立包括寫入緩存 區寫滿數據的時間和將寫入緩存區中寫滿的數據存儲到NAND快閃記憶體中的頁地址對應關係的 時間日誌，並在NAND快閃記憶體存儲寫滿的子樹索引數組中的時間日誌，在主存中存儲正在寫入 時間日誌的子樹索引數組和寫入子樹日誌的根樹索引數組，實現了對具有時序特性的數 據，以時間為索引在主存中通過與根樹索引數組中的時間進行比較後獲得包含查詢時間的 子樹日誌，從NAND快閃記憶體中獲取對應的子樹索引數組中的時間日誌，再通過與子樹索引數組 中的時間進行比較獲取包含查詢時間的時間日誌，並獲取對應的數據，既大大節約了有限 的主存空間資源，又減少了訪問主存空間的次數，大大地提高了查詢數據的速度。基於上述實施例，在將建立的子樹日誌存儲到主存中的根樹索引數組底層的過程 中，若判斷獲知主存中根樹索引數組的底層中已存儲的子樹日誌的個數已經達到設置的根 樹索引數組的長度，則說明NAND快閃記憶體已滿，沒有空間進行數據存儲，根據NAND快閃記憶體的擦出 特點，以塊為單位從NAND快閃記憶體中擦除最早存儲的時間日誌，這些時間日誌是主存中寫滿的 子樹索引數組中的時間日誌，當子樹索引數組底層中存儲的時間日誌的個數達到子樹索引 數組的長度減一，則不再寫入，將這些時間日誌以頁為單位存儲到NAND快閃記憶體中，以及這些 時間日誌裡的頁地址裡所存儲的數據，上述實施例中提到子樹索引數組的長度設置為NAND 快閃記憶體中每塊存儲區所包含的頁數的整數倍，因此以塊為單位進行擦除時會完整的擦除一棵 子樹索引數組中的存儲的時間日誌以及裡面頁地址上存儲的數據。擦除以後的NAND快閃記憶體空間用以存儲寫入緩存區寫滿時所對應的數據，將這些數 據存儲到NAND快閃記憶體中後新生成的時間日誌寫入主存空間裡正在寫入的子樹索引數組的底 層，當子樹索引數組底層中存儲的時間日誌的個數達到子樹索引數組的長度減一時，提取 最後一個寫入的時間日誌中的時間並將寫滿的時間日誌存儲到擦除以後的NAND快閃記憶體空間 裡，並根據存儲時間日誌返回的頁地址在主存空間裡的根樹索引數組底層中找到包含該頁 地址的子樹日誌，更新子樹日誌裡與該頁地址對應的時間。本實施例提供的數據查詢方法，在NAND快閃記憶體沒有空間存儲的情況下，通過擦除 NAND快閃記憶體中最早存入的時間日誌和對應的數據，並根據新存儲的時間日誌的頁地址，應用 新存儲進來的子樹索引數組中最後一個時間日誌中的時間更新根樹索引數組中包含該頁 地址的子樹日誌中的時間，實現了根據NAND快閃記憶體的擦除特性對數據以子樹索弓I數組結構 進行更新，使NAND快閃記憶體進行了循環充分的利用。基於上述實施例，若CPU停止工作，為了防止數據丟失，將主存中根樹索引數組的 底層的子樹日誌和正在寫入的子樹索引數組的底層的時間日誌存儲到NAND快閃記憶體中，當CPU 再次開始工作的時候，先從NAND快閃記憶體中將根樹索引數組的底層的子樹日誌和正在寫入的 子樹索引數組的底層的時間日誌讀取到主存中，再根據數據的時序特性建立索引，並且以 時間為索引進行數據的查詢。本實施例提供的數據查詢方法，通過將主存中根樹索引數組的底層的子樹日誌和 正在寫入的子樹索引數組的底層的時間日誌在CPU停止工作時存儲到NAND快閃記憶體中，更進一 步地保證了數據索引的安全性和以時間為索引進行數據查詢的可靠性。基於上述本發明提供的數據查詢方法實施例中通過存儲模塊中的級聯樹索引結 構，為了更清楚的說明存儲模塊中主存和NAND快閃記憶體具體的存儲數據，見表1和表2所示，其中，表1為本發明數據存儲方法實施例中系統運行時主存空間的劃分，表2為本發明數據存 儲方法實施例中系統運行時NAND快閃記憶體空間的劃分。表 權利要求
1.一種數據查詢方法，其特徵在於，包括在向存儲模塊的主存中的寫入緩存區寫數據的過程中，獲取所述寫入緩存區寫滿數據 時的時間；將所述寫入緩存區中的數據以頁為單位存儲到所述存儲模塊的NAND快閃記憶體中； 接收所述NAND快閃記憶體返回的存儲所述數據的頁地址，建立包括所述時間和所述頁地址 對應關係的時間日誌並存儲在所述存儲模塊，供以時間為索引進行數據查詢。
2.根據權利要求1所述的數據查詢方法，其特徵在於，所述方法還包括 設置所述寫入緩存區的容量為所述NAND快閃記憶體中的頁容量。
3.根據權利要求1或2所述的數據查詢方法，其特徵在於，所述以時間為索引進行數據 查詢包括接收輸入的查詢時間以獲取在所述查詢時間內存儲到所述存儲模塊中的數據； 查詢所述主存中的寫入緩存區中存儲的數據所對應的時間，若判斷獲知不包含所述查 詢時間，則根據所述存儲模塊中存儲的所述時間日誌獲取包含所述查詢時間的時間日誌， 並獲取存儲所述數據的頁地址；根據所述頁地址以頁為單位從所述NAND快閃記憶體中讀取所述數據到所述主存中的讀取緩 存區並獲取在所述查詢時間內存儲的數據。
4.根據權利要求1或2所述的數據查詢方法，其特徵在於，所述建立包括所述時間和所 述頁地址對應關係的時間日誌並存儲包括通過樹結構存儲所述時間日誌，供以時間為索引進行數據查詢，所述樹結構包括小扇 出係數非平衡樹結構、大扇出係數非平衡樹結構、小扇出係數平衡樹結構或大扇出係數平 衡樹結構。
5.根據權利要求4所述的數據查詢方法，其特徵在於，所述通過樹結構存儲所述時間 日誌，供以時間為索引進行數據查詢包括設置子樹扇出係數和子樹索引數組的長度，構造以時間為索引進行數據查詢的子樹索 引數組，對所述子樹索引數組的長度取所述子樹扇出係數為底的對數獲取所述子樹索引數 組的層數，所述子樹索引數組的底層用於存儲所述時間日誌，其餘層是根據所述子樹扇出 係數來存儲所述時間日誌中包含的時間；若判斷獲知所述主存中正在寫入的子樹索引數組的底層中已存儲的時間日誌的個數 達到所述子樹索引數組的長度，則所述子樹索引數組已寫滿，將新生成的時間日誌寫入所 述主存中下一棵子樹索引數組的底層。
6.根據權利要求5所述的數據查詢方法，其特徵在於，所述方法還包括設置所述子樹索引數組的長度為所述NAND快閃記憶體中每塊存儲區所包含的頁數的整數 倍，所述子樹索引數組的存儲容量小於或等於所述頁容量；若判斷獲知所述主存中正在寫入的子樹索引數組的底層中已存儲的時間日誌的個數 已經達到所述子樹索引數組的長度減一，則獲取最後一個存儲的時間日誌中的時間，並將 所述子樹索引數組存儲到所述NAND快閃記憶體中；接收所述NAND快閃記憶體返回的存儲所述子樹索引數組的頁地址，且根據所述時間和所述 頁地址的對應關係生成子樹日誌並存儲在所述主存中的根樹索引數組的底層，供以時間為 索引進行所述子樹日誌查詢，其中，所述根樹索引數組通過設置根樹扇出係數和根樹索引數組的長度進行構造，所述根樹索引數組的長度為所述NAND快閃記憶體中的總頁數除以所述子 樹索引數組的長度而獲得的，對所述根樹索引數組的長度取所述根樹扇出係數為底的對數 獲取所述根樹索引數組的層數，所述根樹索引數組的底層用於存儲所述子樹日誌，其餘的 層是根據所述根樹扇出係數來存儲所述子樹日誌中包含的時間。
7.根據權利要求6所述的數據查詢方法，其特徵在於，所述方法還包括若判斷獲知所述主存中根樹索引數組的底層中已存儲的子樹日誌的個數已經達到所 述根樹索引數組的長度，則以塊為單位擦除所述NAND快閃記憶體中最早存儲的所述時間日誌和 對應的數據，以存儲所述寫入緩存區的數據和所述時間日誌，並根據存儲所述時間日誌返 回的頁地址，應用新存儲到所述NAND快閃記憶體中的子樹索引數組中的最後一個時間日誌中的 時間更新所述子樹日誌中的時間。
8.根據權利要求6所述的數據查詢方法，其特徵在於，所述方法還包括若CPU停止工作，將所述主存中根樹索引數組的底層的子樹日誌和正在寫入的子樹索 弓丨數組的底層的時間日誌存儲到所述NAND快閃記憶體中。
9.一種數據查詢裝置，其特徵在於，包括存儲模塊、獲取模塊、處理模塊和查詢模塊， 其中，所述存儲模塊包括主存和NAND快閃記憶體，所述主存中包括寫入緩存區和讀取緩存區，其 中，所述獲取模塊，用於在向所述寫入緩存區寫數據的過程中，獲取所述寫入緩存區寫滿 數據時的時間；所述處理模塊，用於將所述寫入緩存區中的數據以頁為單位存儲到所述NAND快閃記憶體中， 並接收所述NAND快閃記憶體返回的存儲所述數據的頁地址，建立包括所述時間和所述頁地址對 應關係的時間日誌，並存儲在所述存儲模塊中；所述查詢模塊，用於以時間為索引進行數據查詢。
10.根據權利要求9所述的數據查詢裝置，其特徵在於，所述查詢模塊包括接收單元，用於接收輸入的查詢時間以獲取在所述查詢時間內存儲到所述存儲模塊中 的數據；尋址單元，用於查詢所述主存中的寫入緩存區中存儲的數據所對應的時間，若判斷獲 知不包含所述查詢時間，則根據所述存儲模塊中存儲的所述時間日誌獲取包含所述查詢時 間的時間日誌，並獲取存儲所述數據的頁地址；讀取單元，用於根據所述頁地址以頁為單位從所述NAND快閃記憶體中讀取所述數據到所述 主存中的讀取緩存區並獲取在所述查詢時間內存儲的數據。
全文摘要
本發明提供一種數據查詢方法和裝置。其中該方法包括在向存儲模塊的主存中的寫入緩存區寫數據的過程中，獲取所述寫入緩存區寫滿數據時的時間；將所述寫入緩存區中的數據以頁為單位存儲到所述存儲模塊的NAND快閃記憶體中；接收所述NAND快閃記憶體返回的存儲所述數據的頁地址，建立包括所述時間和所述頁地址對應關係的時間日誌並存儲在所述存儲模塊，供以時間為索引進行數據查詢，通過本發明提供的數據查詢方法和裝置，實現了對具有時序特性的數據，以時間為索引進行查詢對應的數據，大大提高了數據查詢的速度。
文檔編號G06F17/30GK102136005SQ201110077110
公開日2011年7月27日 申請日期2011年3月29日 優先權日2011年3月29日
發明者李歡, 梁棟 申請人:北京航空航天大學