嵌入式內(nèi)存數(shù)據(jù)庫存儲與索引算法研究.pdf

1、嵌入式內(nèi)存數(shù)據(jù)庫(Embedded Main-Memory Database,EMMDB)是一種能夠構(gòu)建及應(yīng)用于嵌入式系統(tǒng)或者設(shè)備之上的,采用內(nèi)存數(shù)據(jù)庫(Main-Memory Database,MMDB)結(jié)構(gòu)組織形式的小型數(shù)據(jù)庫。它可以看作是嵌入式數(shù)據(jù)庫(Embedded Database,EBDB)與MMDB性能上的融合,具有傳統(tǒng)數(shù)據(jù)庫無可比擬的優(yōu)勢和廣闊的應(yīng)用前景。
　　 數(shù)據(jù)的存儲和索引是EMMDB系統(tǒng)的核心技術(shù)之一,對

2、其性能的優(yōu)劣起著決定性的作用。本論文即對這兩類技術(shù)的原理及發(fā)展趨勢進行了深入的分析和研究。首先,根據(jù)傳統(tǒng)的區(qū).段式、散列、T樹和B-樹算法,實現(xiàn)數(shù)據(jù)存儲和索引的各功能模塊,將其應(yīng)用在模擬Linux嵌入式系統(tǒng)開發(fā)平臺的環(huán)境上測試并分析其性能。其次,針對EMMDB系統(tǒng)的性能要求,分別提出存儲與索引的改進算法。一是在傳統(tǒng)區(qū)-段式存儲算法的基礎(chǔ)上,結(jié)合類可擴散列思想提出的類可擴散列區(qū)-段式算法(EHAS)。該算法在段實存數(shù)據(jù)頁內(nèi)采用類可擴散列方

3、法進行記錄數(shù)據(jù)的定位,以記錄的一個主鍵字段值取模得到定位關(guān)鍵值和三元組。二是在傳統(tǒng)T樹索引算法的基礎(chǔ)上,結(jié)合B-樹非葉子節(jié)點作多路分支目錄的思想,提出具有優(yōu)先匹配目錄的T樹算法(PMCT-tree)。該算法將T樹劃分為若干有父親孩子關(guān)系的塊,再提取各T樹塊閾值構(gòu)造優(yōu)先匹配目錄(PMC),進而創(chuàng)建T樹與PMC目錄的關(guān)聯(lián)關(guān)系構(gòu)造索引。通過索引查詢時先在PMC中定位到塊再在該T樹塊中查找。
　　 通過在Windows XP SP3上應(yīng)