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

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

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

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