1、嵌入式內(nèi)存數(shù)據(jù)庫的存儲和索引算法研究*宋 玲1+, 楊雪君2, 馬 蘭11. 廣西大學(xué) 計算機與電子信息學(xué)院, 南寧 530004 2. 廣西壯族自治區(qū)電子產(chǎn)品監(jiān)督檢驗所, 南寧 530031Research on Data Organization and Index of EMMDB*SONG Ling1+, YANG Xuejun2, MA Lan11. College of Computer and Electronic Information, Guangxi University, Nanning 530004, ChinaSONG Ling, YANG Xuejun, MA La

2、n. Research on data organization and index of EMMDB. Journal of Fron-tiers of Computer Science and Technology, 2010, 4(8: 742-748.Abstract: This paper proposes the EHAS(quasi-extendible hashing area-segment and the PMCT-tree algorithms, which are more efficient ones on data organization and index of

3、 embedded main-memory database (EMMDB. The EHAS is a storage algorithm which combines quasi-extendible hashing and is based on area-segment method. It lo-cates and stores records with corresponding unique triples, each of which has three parts separately as an area sign, a segment sign and a storage

4、 address sign. The PMCT-tree has a priority match catalog (PMC more than typical T-tree. The PMC is composed of some edges thresholds, which are extracted from T-tree nodes. Experimental re-sults indicate that the EHAS algorithm accelerates storage response time and its average querying time complex

5、ity can reach a constant level under certain conditions; and the PMCT-tree algorithm is good on effectiveness and querying response time.Key words: embedded main-memory database (EMMDB; T-tree; index; quasi-extendible hashing; area-segment method*The National Science and Technology Innovation Projec

6、ts for SMEs Foundation of China under Grant No. 07C26224501847 (國家科技型中小企業(yè)技術(shù)創(chuàng)新基金; the Guangxi Scientific Research and Technological Development Projects Foundation under Grant No. 09321073 (廣西科學(xué)研究與技術(shù)開發(fā)計劃項目. Received 2010-05, Accepted 2010-07.宋 玲 等：嵌入式內(nèi)存數(shù)據(jù)庫的存儲和索引算法研究摘 要: 提出了用于嵌入式內(nèi)存數(shù)據(jù)庫的更高效的數(shù)據(jù)存儲算法(EHAS和

7、索引算法(PMCT-tree。EHAS 算法是基于區(qū)-段式, 結(jié)合類可擴散列的思想, 將記錄以唯一對應(yīng)的三元組作為區(qū)標(biāo)號、段標(biāo)號、地址標(biāo)號來定位存儲的算法。PMCT-tree 比典型的T 樹增加了一種多路分支目錄(PMC, 它是由T 樹節(jié)點中抽取出的部分邊緣閾值構(gòu)成的。測試結(jié)果表明, EHAS算法加快了存儲響應(yīng)時間, 且在一定條件下其平均查詢時間復(fù)雜度可達到常數(shù)級; PMCT-tree算法在有效性和查詢響應(yīng)時間上性能良好。 關(guān)鍵詞: 嵌入式內(nèi)存數(shù)據(jù)庫; T樹; 索引; 類可擴散列; 區(qū)-段式 文獻標(biāo)識碼：A 中圖分類號：TP3111 引言嵌入式內(nèi)存數(shù)據(jù)庫(embedded main-memor

8、y database, EMMDB的核心數(shù)據(jù)處理組織結(jié)構(gòu)是依據(jù)內(nèi)存數(shù)據(jù)庫(main-memory database, MMDB的設(shè)計, 即主要有區(qū)-段式、影子內(nèi)存式的數(shù)據(jù)組織形式和T 樹、B-樹和散列等的索引方法。MMDB 與傳統(tǒng)數(shù)據(jù)庫的主要區(qū)別在于其被承載的硬件載體非磁盤而是有較高速處理能力且地址線性的內(nèi)存1。EMMDB 的設(shè)計除了體積小巧, 要求高速的數(shù)據(jù)處理性能之外, 在數(shù)據(jù)庫系統(tǒng)穩(wěn)定性、準(zhǔn)確性、實時性、跨平臺、硬件兼容性等也有著更高的或者特殊的要求, 主要面向工業(yè)控制、消費類電子、軍事等領(lǐng)域2。其中EMMDB 的數(shù)據(jù)處理算法, 包括數(shù)據(jù)存儲組織形式和索引, 又是影響到整體數(shù)據(jù)庫性能的關(guān)

9、鍵技術(shù)之一。目 前, 數(shù)據(jù)組織大多采用區(qū)-段式方法, 但僅對數(shù)據(jù)做簡單存入而未考慮數(shù)據(jù)之間的關(guān)聯(lián)性和初步整理的工作。MMDB 的索引主要采用T 樹, 目前的改進研究主要集中在減少平衡調(diào)整次數(shù)上, 即對T 樹自身結(jié)構(gòu)和訪問策略做適當(dāng)?shù)母倪M。本文對MMDB 的傳統(tǒng)算法區(qū)-段式和T 樹進行改進和擴展, 提出了類可擴散列區(qū)-段式存儲算法(EHAS和具有優(yōu)先匹配目錄的T 樹(priority match cata-log T-tree, PMCT-tree算法, 并在Linux 2.4內(nèi)核的模擬嵌入式系統(tǒng)開發(fā)平臺環(huán)境中對算法達到的內(nèi)存空間利用率、數(shù)據(jù)存儲及查詢平均響應(yīng)時間進行了研究和分析。2 類可擴散列

10、區(qū)-段式存儲算法(EHAS 2.1 問題描述目前大多數(shù)MMDB 的數(shù)據(jù)存儲組織方式有兩種：區(qū)-段式和影子內(nèi)存式3。區(qū)-段式是將使用的內(nèi)存空間劃分為多個可不連續(xù)的段空間, 段內(nèi)則是一片連續(xù)的內(nèi)存區(qū)域, 多段構(gòu)成一個區(qū)空間。區(qū)或段都由其各自的標(biāo)號導(dǎo)向, 即存儲一條表記錄需要指定其區(qū)標(biāo)號、段標(biāo)號和段內(nèi)實存地址號; 影子內(nèi)存式是針對當(dāng)多事務(wù)共享數(shù)據(jù)庫的情況時, 依據(jù)優(yōu)先權(quán)或搶占式機制4, 分配事務(wù)占用內(nèi)存空間的方法。在嵌入式系統(tǒng)中, 由于大多事務(wù)操作所需要的資源不太多并且操作本身也不復(fù)雜, 所以目前本文只考慮一項事務(wù)請求時在同一時間無其他事務(wù)搶占數(shù)據(jù)庫的情況, 即單個事務(wù)獨占數(shù)據(jù)庫的情形, 因此EHA

11、S 算法主要針對區(qū)-段式, 融合類可擴散列的思想作改進和擴展。可擴散列能解決傳統(tǒng)數(shù)據(jù)庫向內(nèi)存讀入數(shù)據(jù)量太大以至于一次裝不進內(nèi)存的情況5, 適用于對數(shù)據(jù)的快速分類與定位。在插入與查找數(shù)據(jù)的時候, 以數(shù)據(jù)的前幾位比特確定其位置, 這幾個比特稱為根。如用D 代表根所使用的比特數(shù), 則其指定的桶內(nèi)數(shù)據(jù)項數(shù)為2D 5。隨著數(shù)據(jù)加入增多, 部分桶內(nèi)項會填滿, 當(dāng)再次向滿項桶加入新項時, 需要將該桶分裂, 重新生成目錄, 即此時D 增大。EHAS 算法實現(xiàn)向區(qū)-段式結(jié)構(gòu)存儲組織表記錄時, 即融合了類似可擴散列的根定位思744 Journal of Frontiers of Computer Science

12、and Technology 計算機科學(xué)與探索 2010, 4(8想?；诒碛涗浀年P(guān)鍵字不相同的特點, 分別取其中幾組比特的組合作為定位該記錄的三元組(區(qū)標(biāo)號AID, 段標(biāo)號SID, 段內(nèi)地址號DID, 依此找到段實存空間內(nèi)位置后存入記錄, 對于沖突的記錄以鏈?zhǔn)巾摯鎯?。一個16位的關(guān)鍵值其三元組位拆分情況如圖1所示。保存的量。(2 將KIDS 按圖1所示的比特位分割取值, 計算得到區(qū)標(biāo)號AID 、段標(biāo)號SID 、段內(nèi)地址號DID 。SID TABLE、按此三元組依次從AID TABLE、DID TABLE中查找到定位位置DID i 。(3 若DID i 為空, 存入記錄, 轉(zhuǎn)至第(5步。 (4

13、 若DID i 已有記錄即發(fā)生沖突時, 將記錄存儲到DID TABLE的CONTROL INFO域中沖突頁指針指向的沖突鏈表頁中。(5 存入記錄成功時, 更新區(qū)、段、實存數(shù)據(jù)頁內(nèi)各種控制及標(biāo)志信息, 一次存儲操作完畢, 成功返回; 否則, 警告出錯提示, 返回本次操作前的狀態(tài)。Fig.1 16 bit key value splitting into a triple structure diagram圖1 16 bit 關(guān)鍵值拆分三元組標(biāo)號結(jié)構(gòu)圖2.2 EHAS算法步驟EHAS 算法將段與其對應(yīng)記錄實存空間分離, 三元組中各元比特位數(shù)為固定值, 分別設(shè)AID 為4位、SID 為4位、DID

14、為8位, 記錄實存空間大小為固定值, 結(jié)構(gòu)如圖2所示。2.3 EHAS算法特點EHAS 算法的最大特點是把類可擴散列算法的分組、分層次、一次定位的思想應(yīng)用于區(qū)-段式存儲中, 尤其適用于表記錄形式整齊且主鍵在一定值范圍內(nèi)隨機性強、分布較均勻的情況。該存儲算法操作的前提是要指定表記錄的主鍵, 否則將以其存入的序號作為主鍵求得關(guān)鍵值。采用以記錄主鍵值取模得到的關(guān)鍵值拆分成為定位記錄唯一標(biāo)記ID 的三元組。為解決散列的沖突問 題, 采用鏈地址表法, 在每段的實存數(shù)據(jù)頁中設(shè)置一個指針域, 使其指向一個沖突鏈表頁。EHAS 算法的另一特點是用作存儲的同時也給出了快速索引的一種方法, 利用了散列定位能夠?qū)?shù)

15、據(jù)適當(dāng)分類分塊并用于索引的特性, 彌補了區(qū)-段式方法未做數(shù)據(jù)初步整理的不足。存入記錄依據(jù)的是聚合度較低的主鍵作關(guān)鍵值, 那么依據(jù)此關(guān)鍵值索引記錄時即通過與存儲操作相同的計算來定位和查找。Fig.2 EHAS structure chart 圖2 類可擴散列區(qū)-段結(jié)構(gòu)圖按記錄主鍵關(guān)鍵值存儲組織數(shù)據(jù)的步驟如下： (1 由記錄主鍵值與一個大素數(shù)求模, 該大素數(shù)需根據(jù)表記錄字節(jié)長度和段內(nèi)實際存儲空間大小選取。模后的值即經(jīng)過位壓縮得到一個16位的關(guān)鍵值KIDS, 這樣求得關(guān)鍵值用來增強記 錄之間的定位差異性即降低聚合, 從而減少沖突的發(fā)生。這個關(guān)鍵值是第(2步定位存儲位置, 也是第(4步解決記錄沖突時鏈

16、接到?jīng)_突鏈上所需3 具有優(yōu)先匹配目錄的T 樹算法(PMCT-tree 3.1 問題描述目前普遍認為最適用于MMDB 的索引結(jié)構(gòu)是T 樹6及其演化樹T*樹7等, 有些EBDB 也使用B-樹及其演化樹B+樹算法作為索引結(jié)構(gòu)的組織方式, 如SQLite 。B-樹及B+樹長期以來被普遍認為是最適用于傳統(tǒng)磁盤數(shù)據(jù)庫的索引結(jié)構(gòu), 因 為它的最大特點是能夠以較低的深度容納大量的數(shù)據(jù), 根及所有非葉子節(jié)點起到多路分支目錄的作用, 所有的實際數(shù)據(jù)記錄都存儲在葉子節(jié)點上4。T 樹的所有節(jié)點內(nèi)都保存有關(guān)鍵字及指針, 用來指向?qū)嶋H記錄數(shù)據(jù), 因此T 樹就比B-樹節(jié)省了大多數(shù)非葉節(jié)點所占用的空間。近年來已有針對減少T

17、樹的平衡調(diào)整次數(shù)的研究, 做出了一些在T 樹節(jié)點結(jié)構(gòu)和算法上的改進, 從而在一定程度上加快因插入和刪除關(guān)鍵值而創(chuàng)建及維護索引時的響應(yīng)時間。而創(chuàng)建索引后, 它的作用將是為快速查詢數(shù)據(jù)服務(wù)。T 樹的算法是, 從根開始自頂向下依次找其子樹, 直到被查數(shù)據(jù)K value 被界定到某一節(jié)點中, 要求K value 值小于等于該節(jié)點的最大值, 且大于等于最小Fig.4 T-tree block and PMC node diagram圖4 T樹塊與PMC 節(jié)點關(guān)系圖小關(guān)系。查詢時間復(fù)雜度為O (log(M +1P , P 大于值。遍歷比較的深度是從根到該節(jié)點之間。本等于N /M 。文所提出的PMCT-tr

18、ee 算法即主要對這個查找定一般地, 索引操作包含查詢、插入、刪除、位的過程進行改進。主要思想是將T 樹分塊并從更新四種, 其中查詢操作是任何一項的必要基礎(chǔ)各塊中提取閾值并構(gòu)造出一組多路分支樹形結(jié)和前提, 也是整個算法中較復(fù)雜且關(guān)鍵的部分。構(gòu) 優(yōu)先匹配目錄PMC(priority match catalog,因此以查詢操作為例, 結(jié)合圖4說明PMCT-tree其節(jié)點結(jié)構(gòu)如圖3所示。將PMC 和T 樹相結(jié)合算法查詢步驟如下：共同作為索引的整體。T 樹塊與PMC 節(jié)點關(guān)系如(1 對已創(chuàng)建的PMC 目錄, 從根塊開始與待圖4所示。查關(guān)鍵字K value 匹配。 若K value 大于該塊中的最大鍵值

19、nodes-MaxMK, 則跳至該塊中子樹塊指針序列所指定的最右子樹pfmarri , 其指向的塊BBi 所包含的所有鍵值均大于nodesMaxMK 。匹配K value 和 BB i 塊, 轉(zhuǎn)自步驟開始。Fig.3 PMC node structure chart圖3 PMC節(jié)點結(jié)構(gòu)圖3.2 PMCT-tree算法PMCT-tree 索引的創(chuàng)建是在已建立的T 樹索引基礎(chǔ)上, 設(shè)T 樹共有N 個節(jié)點, 將T 樹分成P 塊, 設(shè)每塊至多包含M 個節(jié)點, M 值與T 樹深度緊密相關(guān), 若初始值設(shè)為3, 即深度為2的T 樹節(jié)點數(shù)目的最大值。提取各T 樹塊的邊界閾值及子塊信息構(gòu)造PMC, 則PMC 目

20、錄為M +1分支共有P 個節(jié)點的樹, 節(jié)點間保持T 樹中祖先-子樹的大 若K value 小于該塊中的最小鍵值nodes-MinMK, 則跳至該塊最左子樹pfmarr0, 其指向的塊BB0所包含的所有鍵值均小于nodesMinMK 。匹配K value 和BB0塊, 轉(zhuǎn)自步驟開始。 K value 值在該塊中介于nodesMinMK 和nodesMaxMK 之間。若該塊無子樹存在, 說明K value 值界定在該塊范圍內(nèi), 由該塊的T 樹根節(jié)點pnodeAds 開始, 轉(zhuǎn)至步驟(2, 查找T 樹塊中K value 。 K value 值在該塊中介于nodesMinMK 和nodesMaxMK

21、之間, 該塊有子樹存在, 設(shè)有746Journal of Frontiers of Computer Science and Technology 計算機科學(xué)與探索 2010, 4(8sumSP 個, 各子樹的最小鍵值保存在數(shù)組序 錄, 控制T 樹和PMC 目錄深度之間的平衡。 列branchKey 中。由branchKey0到branchKey sumSP-1, 二分法找到branchKeyi , 使其滿足K value 大于branchKeyi , 且小于branchKeyi +1。再比較K value 與branchKeyi 對應(yīng)的PMC 目錄pfmarri 的最大值nodesMaxMK

22、, 若Kvalue 小于nodesMaxMK, 說明K value 值界定在目錄pfmarri 中, 匹配K value 和pfmarri 塊, 轉(zhuǎn)自步驟開始; 否則說明K value 值界定在本步驟開始時查找的塊中, 由該塊的T 樹根節(jié)點pnode Ads開始, 轉(zhuǎn)至步驟(2, 查找T 樹塊中K value 。(2 由步驟(1中確定的T 樹節(jié)點pnode Ads 開始, 依據(jù)傳統(tǒng)T 樹方法查詢K value 可能被包含的節(jié)點和具體坐標(biāo)iloc 。但只需從pnode Ads開始向下檢索深度限定為1log(M +1之間即可, T樹塊查詢時間復(fù)雜度為O (log(M +1。若K value 與il

23、oc 所指向的數(shù)據(jù)記錄匹配, 則本次查找成功完畢; 否則, 說明K value 在整個數(shù)據(jù)表中都是不存在的, 返回查找失敗。由于PMC 是多分支樹形結(jié)構(gòu), 它的規(guī)模過大會對算法造成負擔(dān), 因此維護PMC 目錄做適 當(dāng)?shù)母虏僮魇潜３制漭^高性能的重點之一。隨著T 樹插入鍵值增多, 深度也逐漸增大, 更新PMC 目錄產(chǎn)生的新一層子樹節(jié)點數(shù)以(M +1的指數(shù)級增長, 空間開銷會突然變大很多, 主要表現(xiàn)在葉子節(jié)點內(nèi)許多空指針的空間浪費, 并且分支路數(shù)的龐大會明顯影響快速查找的效率。因此, 更新PMC 目錄的策略應(yīng)是：(1 當(dāng)T 樹深度H 小于3時不必創(chuàng)建PMC 目錄結(jié)構(gòu), 因為此時T 樹節(jié)點和數(shù)據(jù)量都

24、很小, T樹本身O (log N 的時間復(fù)雜度已是很快速的。(2 若設(shè)M 初始值為3, 當(dāng)H 大于3×log(M +1時, 須修改M 的值, 方法為令M =2(log(M +1+1-1, 再遍歷T 樹更新PMC 結(jié)構(gòu)。修改M 值的作用即使T 樹塊增大一層節(jié)點, 從而使M 隨著T 樹深度的增大而增大, 保持PMC 在三層范圍內(nèi)。(3 若數(shù)據(jù)量增多且M 更新過一次后, 需要增大T 樹節(jié)點內(nèi)鍵值數(shù)目, 更新T 樹及PMC 目3.3 PMCT-tree算法特點PMCT-tree 算法的最大特點是把多路分支目錄的思想融合到T 樹中, 將T 樹節(jié)點中的臨界信息提取壓縮, 構(gòu)造出一個層次較小的目錄

25、結(jié)構(gòu), 查詢時先搜索目錄確定關(guān)鍵值被包含的T 樹塊范圍再在對應(yīng)的T 樹塊中匹配。查詢策略是通過減少比較次數(shù), 以達到快速查詢的目的。適用于創(chuàng)建索引數(shù)據(jù)量相對較大, 且對數(shù)據(jù)庫無較頻繁地插入與查詢交替操作的情況。4 實驗結(jié)果分析本文采用NetBeans IDE 6.0、Cygwin 在Win-dows XP SP3上建立模擬Linux 嵌入式系統(tǒng)開發(fā)平臺環(huán)境上實現(xiàn), 將EHAS 與區(qū)-段式(CAS和PMCT- tree算法與T 樹(簡稱OT 做性能比較。實驗包括：分析內(nèi)存空間利用率; 存儲算法的平均存儲響應(yīng)時間; 索引算法的平均查詢響應(yīng)時間, 并給出其時間復(fù)雜度。4.1 EHAS算法分析分析比較

26、EHAS 和CAS 算法的性能, 以0條記錄開始, 1 000條記錄為增量, 到4 000條記錄。由于兩種算法都分配了區(qū)、段、實存數(shù)據(jù)空間, 其中區(qū)、段空間大小相當(dāng), 因此實存空間利用率的計算如式(1所示。R ×B R P =N (1G N ×B G 式(1中, P 表示實存空間利用率; R N 為記錄條數(shù); B R 為每條記錄字節(jié)數(shù); G N 為實存數(shù)據(jù)頁數(shù); B G 為每G N 頁字節(jié)數(shù)。性能比較如圖5所示。平均存儲響應(yīng)時間即連續(xù)存儲N 條記錄所需時間的平均值, 如圖6所示。由圖5和圖6可以看出EHAS 算法雖然較CAS 空間利用率略低, 但也保證在80%以上, 且差值

27、并不太大, 這與由存儲鍵值聚合度低的散列存儲性質(zhì)相一致。EHAS 平均存儲響應(yīng)時間比CAS 要快, 原因主要是對實存表的維護中, EHAS比CAS 省去記錄指針定位等輔助操作, 一定程度上以響應(yīng)時間加快補償了空間的損失。重要的是,宋 玲 等：嵌入式內(nèi)存數(shù)據(jù)庫的存儲和索引算法研究 747 Fig.5 Utilization rate comparison of storage space 圖 5 實存空間利用率 Fig.6 Response time comparison of average storage 圖 6 平均存儲響應(yīng)時間 Fig.7 Average querying respons

28、e time 圖 7 查詢平均響應(yīng)時間 Fig.8 Memory space utilization rate 圖 8 內(nèi)存空間利用率 可擴散列也用作一種快速索引結(jié)構(gòu) 8。由于采用 了類可擴散列的思想定位記錄, 對于查詢關(guān)鍵字 與存儲操作使用的字段主鍵相同的情況下, 其查 找成功的平均查詢時間復(fù)雜度為常數(shù)級, 這是由 散列算法定位查詢的性質(zhì)決定的, 是 CAS 算法所 不能擁有的性能, EHAS 即在這方面彌補了 CAS 未對記錄進行初步整理維護的不足。 BCLPN 為每葉節(jié)點內(nèi)分支控制信息字節(jié)數(shù); TNN 為 T 樹節(jié)點頁數(shù); BTN 為每頁字節(jié)數(shù); CN 為 PMC 節(jié)點 數(shù); BC 為每

29、節(jié)點字節(jié)數(shù)。 由圖 7 和圖 8 可以看出, PMCT-tree 算法以一 定程度上的空間損失換得時間效率的提高。由于 PMC 目錄是多路樹形結(jié)構(gòu), 它高度增加節(jié)點個數(shù) 以指數(shù)級增長 , 即 PMC 目錄深度越大對空間的 浪費將越多, 因此算法控制其深度最大為三或四 層 , 同時也說明 PMC 目錄的更新維護對性能提 高十分重要。 另一方面看, PMCT-tree 由于使用了 目錄 , 相當(dāng)于壓縮了 T 樹規(guī)模 , 因此能夠達到加 快查詢響應(yīng)時間的目的, 并且在 EMMDB 系統(tǒng)中, 數(shù)據(jù)處理的算法性能在響應(yīng)時間上的提高是需 要考查的一個重要指標(biāo)。正如空間和時間總是不 能完美平衡 , 必然會顧

30、此失彼 , 為了在時間上增 強性能 , 空間的損失就不可避免 , 由于目前內(nèi)存 容量增大迅速 , 一定程度的空間浪費就在硬件條 件和技術(shù)上都是可以接受的。PMCT-tree 算法查 詢時間復(fù)雜度是 PMC 目錄與 T 樹塊查詢時間復(fù) 雜度的和, 即 O(log(M+1P + logM, 總體上看 PMCTtree 是比 OT 更優(yōu)的算法。 4.2 PMCT-tree 算法分析 比較 PMCT-tree(簡稱 PMCT與 OT 算法的性 能, 以 0 個關(guān)鍵字開始, 500 個為增量, 到 4 000 個關(guān)鍵字。分析兩種索引算法的查詢平均響應(yīng)時 間和內(nèi)存空間利用率, 分別如圖 7 和圖 8 所示

31、。 查詢平均響應(yīng)時間即平均查詢每單個關(guān)鍵字所 需時間的平均值。內(nèi)存空間利用率是指分配的 T 樹節(jié)點和 PMC 目錄節(jié)點中, 存入有效鍵值和分 支子樹及控制信息占所有節(jié)點空間總數(shù)的比例。 內(nèi)存空間利用率的計算如式(2所示： × BTK + CLN × BCLPN T S = 1 NKN (2 TNN × BTN + C N × BC 式(2中, S 表示內(nèi)存空間利用率; TNKN 為 T 樹節(jié)點 空鍵數(shù); BTK 為每鍵字節(jié)數(shù); CLN 為 PMC 葉節(jié)點數(shù); 748 Journal of Frontiers of Computer Science and

32、 Technology 計算機科學(xué)與探索 2010, 4(8 5 結(jié)束語 本文根據(jù) Linux 嵌入式系統(tǒng)應(yīng)用領(lǐng)域特征及 MMDB 區(qū)-段式、 樹算法, 結(jié)合類可擴散列的分 T 組快速定位和 B-樹多路分支目錄查詢等優(yōu)勢, 提 出 EHAS 存儲算法和 PMCT-tree 算法。 實驗表明, 算法性能及穩(wěn)定性較好 , 但仍有許多待改進的空 間。今后將進一步研究 EHAS 算法中類可擴散列 根的動態(tài)維護, 更大程度減少其值的聚合降低沖 突率; 詳細研究 PMCT-tree 算法中 PMC 目錄結(jié)構(gòu) 的簡化和更新策略 , 使其能有效提高空間利用率 ; 將算法移植應(yīng)用到更多的小型嵌入式系統(tǒng)如 uCl

33、inux 等的環(huán)境中, 進行進一步應(yīng)用性研究。 References: 1 Garcia-Molina H, Salem K. Main memory database systems: An overviewJ. IEEE Trans Knowledge Data Engineering, 1992, 4(6: 509516. 2 Wei Hongxing, Chen Weijun. Embedded system designersM. Beijing: Tsinghua University Press, 2006. 3 Huang Lin, Lu Jing, Lin Zhong. Re

34、covery method for main memory database systems based on shadow pagingJ. Computer Engineering and Design, 2008, 29(10: 24702473. 4 Xiao Yingyuan, Liu Yunsheng, Liu Xiaofeng, et al. A crash recovery technique for embedded real-time main memory databaseJ. Computer Science, 2005, 32(8: 7779. 5 Weiss M A

35、. Data structures and algorithm analysis in CM. 2nd ed. Beijing: China Machine Press, 2004: 124125. 6 Lin Peng, Li Hang, Xu Xuezhou. Optimization of T-tree index of main memory database in critical applicationJ. Computer Engineering, 2004, 30(17: 7576. 7 Kong-Rim C, Kyung-Chang K. T*-tree, a main memory database index structure for real time applicationsC/ Proceedings of the 3rd International Workshop on Real-Time Computing Systems Application (RTCSA96. Washington DC: IEEE Computer Society, 1996: 8188. 8 Yuan Peisen, Pi Dechang. Design and implementation of Hash index used in main memo