一種嵌入式系統的數據存放及其查找方法
2023-10-08 13:42:54 2
專利名稱：一種嵌入式系統的數據存放及其查找方法
技術領域：
本發明涉及一種嵌入式系統的數據處理技術，特別涉及一種嵌入式系統的數據存放及其查找方法。
背景技術：
目前，很多嵌入式系統引入了嵌入式資料庫。嵌入式資料庫對嵌入式產品有著十分重要的意義，其能夠滿足嵌入式系統對數據處理和數據交換等要求，它和嵌入式作業系統有機地結合在一起，為應用開發人員提供有效的數據管理手段，同時提供各種定製條件和方法。
數據的存儲與索引是嵌入式資料庫的核心技術，也是決定資料庫存儲效率的關鍵技術，一個快速、靈活、高效的數據存儲和索引方法是資料庫研發中最為基本又最為重要的環節之一，其質量的優劣直接決定了數據的存取速度和查詢速度等主要技術指標；同時，存儲與索引兩者之間又是互相依賴的，通過一對匹配的索引和存儲技術間共同協調工作，才能有效地完成數據的存儲與查詢。嵌入式資料庫中的數據一般都採用二進位進行存儲，這樣保證了嵌入式資料庫的平臺無關性，同時有利於提高查找速度。
現有大型資料庫系統的資料庫存儲和索引技術，如IBM的DB2，Microsoft的SQL Server等，採用複雜的多級索引和動態散列結構對數據進行處理，並採用並行分布式系統對數據資料進行管理，可在很大程度上提高數據的存取速度和效率，但必須建立在高速系統、大容量硬碟、內存及高速的並行機制基礎上，受這些條件的限制，顯然不能將這些成熟的數據存放與索引技術平滑地移植到象嵌入式這樣的低性能、單一節點的設備所使用的資料庫中。
現有的嵌入式設備由於自身特點的不同對嵌入式資料庫進行數據處理的要求也有所不同有的嵌入式設備如PDA、手機等存儲空間小，對數據的並發操作要求低；而有的嵌入式設備，如Handle PC、終端機、機頂盒等具有相對較大的磁碟空間，要求對數據具有相當大的並發操作能力，又同時希望有足夠的索引以提高數據查找速度。
對於存儲空間小，對數據的並發操作要求低的嵌入式系統，可以採用全散列技術將記錄和索引存放在同一個數據文件中，它將記錄中的數據以域(即欄位)為單位進行拆分，將這個記錄的每一個域都散列存放在這個數據文件的相應索引中，實際上這個數據文件不存在記錄的實體，而是每個域的索引數據的組合，由於每個域上都存在索引，通過查找每個索引中該記錄的相應域的數值，然後進行數據組裝從而得到完整的記錄數據。這種技術由於表單各域都有相應的索引，各個域的數據都存放在相應的索引中，而不存在數據的實體，在很大程度上節省了磁碟佔用空間，同時，由於數據完全散列的存放，使得用戶可以方便的在表單的任何域上做查詢操作而不影響查詢效率。但由於所有的表單操作都是在一個數據文件中進行，使得對這種表單的數據並發性操作受到了一定程度的影響。
可見，全散列技術由於並發性受到了影響而並不適用於具有相對較大的磁碟空間，要求對數據具有相當大的並發操作能力，又同時希望有足夠的索引以提高數據查找速度的嵌入式系統。目前對於這類嵌入式系統還沒有較好的數據存儲和查找的方法來解決並發性和提高數據查找速度的問題。
發明內容
有鑑於此，本發明的目的在於提供一種嵌入式系統的數據存放及其查找方法，具有相當大的並發操作能力，同時又能夠提高嵌入式系統數據查找的速度和效率。
為達到上述目的，本發明的技術方案具體是這樣實現的一種嵌入式系統的數據存放及其查找方法，其特徵在於，該方法包括
數據存放過程，其包括建立表單，將記錄存放在數據文件中；和為表單中用戶所指定的一個或多個域建立一個或多個域索引文件，將索引信息寫入域索引文件，並將表單的數據文件和域索引文件進行綁定；如果用戶沒有指定域則建立簡單索引文件，將索引信息寫入簡單索引文件；數據查找過程，其通過在域索引文件中查找數據的索引信息，或沒有域索引文件時在簡單索引文件中查找數據的索引信息來進行數據查找。
該方法中，寫入域索引文件的索引信息可以包含每條記錄在該域的內容、記錄在數據文件中的具體位置和該記錄的大小；寫入簡單索引文件的索引信息可以包含每條記錄在數據文件中的具體位置和該記錄的大小。
該方法步驟2)所述的建立域索引文件的過程可以為對用戶所指定的各個域的數據分別通過哈希運算得到哈希結果值，將哈希結果值填入索引文件中的哈希表，根據哈希表將索引信息填入索引文件中的B+樹。步驟3)所述的在域索引文件中查找數據的索引信息的過程可以為根據欲查找數據的一個或多個域比較條件，先進行哈希運算得到各個條件的哈希值，再根據各個域索引文件中的哈希表，到各個域索引文件中的B+樹中查找各個域的索引信息。
步驟2)所述的將表單的數據文件和域索引文件進行綁定的方法可以為將該表單的數據文件和域索引文件存放在同一目錄中。
步驟3)所述的在簡單索引文件中查找數據的索引信息的可以過程為遍歷簡單索引文件查找該條記錄的索引信息。
該方法可以進一步包括如果表單建立了域索引文件，則將簡單索引文件刪除。
該方法還可以進一步包括，刪除記錄的過程為從域索引文件或簡單索引文件中查找到該記錄的索引信息並標記刪除。域索引文件中標記刪除的索引信息，可以在添加新記錄時，用新記錄的索引信息代替。簡單索引文件中標記刪除的索引信息，用不能重用標記代替。
該方法還可以進一步包括在刪除域的索引時，先判斷該域所在的表單是否還有其他的域索引文件，如果有則直接刪除該域的域索引文件；如果沒有則建立簡單索引文件，根據該域的域索引文件遍歷整個表單，將索引信息寫入簡單索引文件，再刪除該域的域索引文件。
該方法還可以進一步包括在對表單的結構進行修改時，建立一個與修改後的表單結構相同的臨時表單，遍歷整個原表單，將原表單的所有記錄插入臨時表單，再將原表單用臨時表單替換。
因此，本發明的這種嵌入式系統的數據存放及其查找方法，具有相當大的並發操作能力，同時又能夠提高嵌入式系統數據查找的速度和效率。本發明是一種以索引文件為基本單位的數據多索引技術，它使得嵌入式資料庫實現了數據多索引交叉查找數據技術，優化提高了嵌入式資料庫數據查找速度及效率，減少了因數據查找而帶來的CPU計算負擔和內存負擔，提高了嵌入式資料庫在嵌入式設備的適用性。
圖1為本發明方案一個較佳實施例的建立第一個域索引文件的過程示意圖；圖2為圖1所示實施例中建立另一個域索引文件的過程示意圖；圖3為圖1所示實施例的表單索引結構示意圖；圖4為圖1所示實施例進行數據查找並刪除的過程示意圖；圖5為圖1所示實施例進行添加記錄的過程示意圖；圖6為圖1所示實施例進行添加域的過程示意圖。
具體實施例方式
為使本發明的目的、技術方案和優點更加清楚明白，下面結合實施例和附圖，對本發明進一步詳細說明。
本發明是為了適應具有相對較大的磁碟空間，要求對數據具有相當大的並發操作能力，又同時希望有足夠的索引以提高數據查找速度的嵌入式系統，發明的一種多索引技術。多索引技術的基本方法是將記錄的數據和索引分開在不同的文件中進行存儲，用戶可以靈活的指定想要建立索引的域，即一個表單由一個數據文件和若干個索引文件組成，由於數據實體和索引文件分開，使得一條記錄的某些數據在數據文件和索引文件中重複出現，雖然加大了數據的存儲冗餘量，但提高了數據的查詢效率。又由於數據和索引存放在不同的文件中，從而減少了並發操作時的衝突，提高了並發操作資料庫的效率。
本發明的實施方法包括以下步驟第一步建立表單，將記錄以二進位形式存放在數據文件中。嵌入式資料庫中的數據一般都採用二進位進行存儲，這樣保證了嵌入式資料庫的平臺無關性，同時有利於提高查找速度。
第二步為表單中用戶所指定的一個或多個域建立一個或多個域索引文件，將索引信息寫入域索引文件，並將表單的數據文件和域索引文件進行綁定；如果用戶沒有指定域則建立簡單索引文件，將索引信息寫入簡單索引文件。
在用戶剛建立表單並在這個表單中建立了幾個域時，因為並沒有建立任何索引，所以系統自動在這個表單中建立一個預設的不依賴於任何域的簡單索引文件。因為數據文件中的記錄是以二進位存放，所以用一個索引對數據文件中的記錄加以區分。
此時，用戶可以指定域建立域索引文件，參見圖1，本發明方案一個較佳實施例的建立第一個域索引文件的過程示意圖。
表單在沒有建立域索引文件時，系統自動建立簡單索引文件。如圖1所示，簡單索引文件101中包含了每條記錄的索引信息及被刪除的索引信息等所有索引信息102；如果用戶想在一個沒有索引的表單的域1上建立索引，則執行步驟103，嵌入式資料庫根據簡單索引文件中的索引信息遍歷整個表單，取出所有的記錄，再通過哈希運算得到哈希結果值，將哈希結果值填入域索引文件中的哈希表，根據哈希表將索引信息填入索引文件中的B+樹，即將每條記錄在域1的索引數據連同索引信息一起寫入索引文件，這樣完成步驟104，建立了域1的域索引文件。然後，將域1的域索引文件存放在該表單數據文件所在的目錄中。最後，刪除已經不再有用的簡單索引文件，因為嵌入式資料庫不再維護這個簡單索引文件。簡單索引是當一個表單用戶沒有顯式的建立索引時建立起來的索引，他不與任何域進行捆綁，同時，它的存在與一般索引文件的存在是互斥的，如果用戶在表單某一個域上建立了索引，則這個簡單索引將被刪除，如果這個表單不存在任何索引，則系統會自動建立簡單索引文件。
表一為簡單索引文件內容表。如表一所示，簡單索引文件僅僅包含這個表單中所有記錄在數據文件的具體位置以及大小的信息，新的記錄插入表單時，它在數據文件中的具體位置信息和數據大小被寫入簡單索引文件的末尾，一條記錄被刪除後，為保證記錄插入表單的時序性，這條記錄在簡單索引文件中所佔用的空間將被不能重用標記-1代替而不能重用。
表一域索引文件中的索引數據是指哈希值、索引信息在B+樹中的位置等，域索引文件中的索引信息則包含每條記錄在該域的內容、記錄在數據文件中的具體位置和該記錄的大小。
用戶還可以指定其他多個域建立域索引文件，參見圖2，圖2為圖1所示實施例中建立另一個域索引文件的過程示意圖。如圖2所示，表單已經在域1上存在索引，若用戶要在域3上創建新的索引，則執行步驟201，資料庫遍歷已存在的域1的域索引文件，然後執行步驟202，通過哈希運算得到新的索引數據連同索引信息一起填充到域3的索引文件中，這樣完成步驟203，建立了域3的域索引文件。然後，將域3的域索引文件存放在該表單數據文件所在的目錄中。如果用戶還需要為其他域建立索引文件，方法同上。
本實施例為表單建立了3個域索引文件，其索引結構參見圖3，圖3為圖1所示實施例的表單索引結構示意圖。如圖3所示，該表單包含5個域域1-域5，其中域1建立了域索引文件301、域3建立了域索引文件302、域5建立了域索引文件303，域2、域4沒有索引。域索引文件301、302和303是根據各個域的數據信息建立的，其包含各個域通過哈希算法計算得到的索引數據和與該域的數據一一對應的索引信息。
第三步表單建立了索引結構後就可以通過在域索引文件中查找數據的索引信息，或沒有域索引文件時在簡單索引文件中查找數據的索引信息來進行數據查找。在有域索引文件，對記錄進行查找時，本發明的多索引記錄存儲方式使得用戶可以進行選擇查找，即用戶只需指定某些域的比較條件對滿足這些比較條件的記錄進行查找。參見圖4，圖4為圖1所示實施例進行數據查找並刪除的過程示意圖。如圖4所示，如用戶希望刪除域1符合條件1，域2符合條件2，域3符合條件3的某些記錄。如圖中1、2所示用戶在域1和域3上都建立了索引，因此首先執行步驟401和402資料庫根據域1和域3的索引，通過計算條件1和條件3的哈希值，根據哈希表找出同時滿足這兩個條件的記錄鏈3；再執行步驟403在這個記錄鏈中進行查找，找出滿足域2符合條件2的這些記錄；對於滿足3個條件的記錄4，執行步驟404將這些記錄在所有索引文件中進行標識，標識它們已被刪除，這樣就完成了用戶提交的記錄條件刪除命令；如圖中5、6、7所示被標記刪除的各域的索引信息包含該記錄在該域的數據內容、記錄所在數據文件的具體位置數據長度等。
本發明並不將索引信息和數據文件的實際內容刪除，這是因為對記錄的查詢等所有操作都是首先查找索引進行的，而在索引中不存在該記錄的索引信息，就無法找到該記錄，就好像這條記錄根本不存在一樣，達到了和刪除記錄同樣的效果。由於不需要刪除整條記錄，提高了刪除記錄的效率，而且這種方法不必釋放這條記錄所佔用的磁碟空間，這些磁碟空間還可以在增加新記錄時被重新利用而不會廢置，不會浪費磁碟空間。同時，這樣還保證了在需要撤消刪除操作時，數據仍然保留，不會造成數據丟失。
在簡單索引文件中查找數據的索引信息來進行數據查找的方法很簡單，只需遍歷整個表單查找該條記錄的索引信息，根據索引信息提供的記錄在數據文件中的位置和記錄的大小，就可以在數據文件中查找到該記錄。
當有新的記錄寫入表單時，如果沒有建立域索引文件只需將新記錄寫入數據文件的末尾，並將數據文件中的具體位置信息的數據大小寫入簡單索引文件的末尾即可。如果表單已建立域索引文件，其寫入過程參見圖5，圖5為圖1所示實施例進行添加記錄的過程示意圖。如圖5所示，首先執行步驟501，資料庫遍歷已建立的域索引文件，接著執行步驟502，判斷是否有標記刪除的信息，如果沒有標記刪除的索引信息，則進入步驟505，將新記錄寫入數據文件末尾並通過哈希運算得到哈希結果值，到索引文件中的哈希表中查找哈希結果值，根據哈希表將索引信息添加到B+樹中；如果有標記刪除的索引信息，則執行步驟503，將新記錄的索引信息與被標記刪除的索引信息進行比較；如果新記錄的索引信息與被標記刪除的索引信息中數據的大小相同，則執行步驟504，通過哈希運算得到新記錄的哈希結果值，將哈希結果值到索引文件中的哈希表中查找，根據哈希表將索引信息添加到B+樹中，並將新記錄的索引信息代替標記刪除的索引信息，取消刪除標記，同時按索引信息中該記錄在數據文件中的地址，將新記錄的數據寫入到數據文件中。如果新記錄的索引信息與被標記刪除的索引信息中數據的大小不同，則執行步驟505。
在表單的結構進行修改時，如建立/刪除/修改域時，將會影響到整個表單的所有記錄在數據文件中的位置等信息，為保證每個索引文件都能正確的反映出表單記錄的索引信息，資料庫建立一個臨時的表單，這個臨時表單的結構形式與建立/刪除/修改域後這個表的結構相同。例如，用戶在本實施例的這個表單中建立一個新域——域6，參見圖6，圖6為圖1所示實施例進行添加域的過程示意圖。如圖6所示，首先步驟601，建立一個包含域6的臨時表單；然後執行步驟602，遍歷整個表單，將原表單中所有記錄插入臨時表單，由於插入記錄時這些記錄在臨時表單中的索引信息會與記錄保持一致，因此達到了修改表單結構的目的，同時又不會因為操作過程中的錯誤而影響到原表單的數據，最後，執行步驟603，將原表單用臨時表單替換，完成表單結構修改操作。
圖6中還示出了臨時表單的結構，其不僅包含了原表單的5個域及其域1、3、5的索引信息，還包含了新建的域6。
由此可見，本發明的這種嵌入式系統的數據存放及其查找方法，具有相當大的並發操作能力，同時又能夠提高嵌入式系統數據查找的速度和效率。是一種以索引文件為基本單位的數據多索引技術，它使得嵌入式資料庫實現了數據多索引交叉查找數據技術，優化提高了嵌入式資料庫數據查找速度及效率，減少了因數據查找而帶來的CPU計算負擔和內存負擔，提高了嵌入式資料庫在嵌入式設備的適用性。同時，由於這種方法的平臺無關性和語言無關性，可以方便地移植到各種嵌入式平臺和應用程式中，有著廣泛的應用前景。
權利要求
1.一種嵌入式系統的數據存放及其查找方法，其特徵在於，該方法包括數據存放過程，其包括建立表單，將記錄存放在數據文件中；和為表單中用戶所指定的一個或多個域建立一個或多個域索引文件，將索引信息寫入域索引文件，並將表單的數據文件和域索引文件進行綁定；如果用戶沒有指定域則建立簡單索引文件，將索引信息寫入簡單索引文件；數據查找過程，其通過在域索引文件中查找數據的索引信息，或沒有域索引文件時在簡單索引文件中查找數據的索引信息來進行數據查找。
2.如權利要求1所述的嵌入式系統的數據存放及其查找方法，其特徵在於寫入域索引文件的索引信息包含每條記錄在該域的內容、記錄在數據文件中的具體位置和該記錄的大小。
3.如權利要求1所述的嵌入式系統的數據存放及其查找方法，其特徵在於寫入簡單索引文件的索引信息包含每條記錄在數據文件中的具體位置和該記錄的大小。
4.如權利要求1所述的嵌入式系統的數據存放及其查找方法，其特徵在於，步驟2)所述的建立域索引文件的過程為對用戶所指定的各個域的數據分別通過哈希運算得到哈希結果值，將哈希結果值填入索引文件中的哈希表，根據哈希表將索引信息填入索引文件中的B+樹；步驟3)所述的在域索引文件中查找數據的索引信息的過程為根據欲查找數據的一個或多個域比較條件，先進行哈希運算得到各個比較條件的哈希值，再根據各個域索引文件中的哈希表，到各個域索引文件中的B+樹中查找各個域的索引信息。
5.如權利要求1所述的嵌入式系統的數據存放及其查找方法，其特徵在於，步驟2)所述的將表單的數據文件和域索引文件進行綁定的方法為將該表單的數據文件和域索引文件存放在同一目錄中。
6.如權利要求1所述的嵌入式系統的數據存放及其查找方法，其特徵在於，步驟3)所述的在簡單索引文件中查找數據的索引信息的過程為遍歷簡單索引文件查找該條記錄的索引信息。
7.如權利要求1所述的嵌入式系統的數據存放及其查找方法，其特徵在於，該方法進一步包括如果表單建立了域索引文件，則將簡單索引文件刪除。
8.如權利要求1所述的嵌入式系統的數據存放及其查找方法，其特徵在於，該方法進一步包括，刪除記錄的過程為從域索引文件或簡單索引文件中查找到該記錄的索引信息並標記刪除。
9.如權利要求8所述的嵌入式系統的數據存放及其查找方法，其特徵在於，該方法進一步包括域索引文件中標記刪除的索引信息，在添加新記錄時，用新記錄的索引信息代替標記刪除的索引信息。
10.如權利要求8所述的嵌入式系統的數據存放及其查找方法，其特徵在於，該方法進一步包括簡單索引文件中標記刪除的索引信息，用不能重用標記代替。
11.如權利要求1所述的嵌入式系統的數據存放及其查找方法，其特徵在於，該方法進一步包括在刪除域的索引時，先判斷該域所在的表單是否還有其他的域索引文件，如果有則直接刪除該域的域索引文件；如果沒有則建立簡單索引文件，根據該域的域索引文件遍歷整個表單，將索引信息寫入簡單索引文件，再刪除該域的域索引文件。
12.如權利要求1所述的嵌入式系統的數據存放及其查找方法，其特徵在於，該方法進一步包括在對表單的結構進行修改時，建立一個與修改後的表單結構相同的臨時表單，遍歷整個原表單，將原表單的所有記錄插入臨時表單，再將原表單用臨時表單替換。
全文摘要
本發明公開了一種嵌入式系統的數據存放及其查找方法，數據存放過程包括建立表單，將記錄存放在數據文件中；和為表單中用戶所指定的一個或多個域建立一個或多個域索引文件，將索引信息寫入域索引文件，並將表單的數據文件和域索引文件進行綁定；如果用戶沒有指定域則建立簡單索引文件，將索引信息寫入簡單索引文件；查找過程為通過在域索引文件中查找數據的索引信息，或沒有域索引文件時在簡單索引文件中查找數據的索引信息來進行數據查找。本發明方法具有相當大的並發操作能力，能夠提高嵌入式系統數據查找的速度和效率，且具有平臺無關性和語言無關性，可以方便地移植到各種嵌入式平臺和應用程式中，有著廣泛的應用前景。
文檔編號G06F17/30GK1492363SQ02145960
公開日2004年4月28日 申請日期2002年10月25日 優先權日2002年10月25日
發明者丁剛, 楊柏梁, 孫雅莎, 丁 剛 申請人:聯想(北京)有限公司