嵌入式數(shù)據(jù)庫索引機(jī)制研究與實(shí)現(xiàn).pdf

1、隨著3G技術(shù)的逐漸成熟，B3G技術(shù)開始研發(fā)，無線傳輸能力越來越強(qiáng)。用戶可利用智能手機(jī)、PDA等移動(dòng)設(shè)備，通過無線技術(shù)連接到網(wǎng)絡(luò)，可隨時(shí)隨地的利用移動(dòng)設(shè)備來存取網(wǎng)絡(luò)中的資源。在許多嵌入式設(shè)備中，使用嵌入式數(shù)據(jù)庫管理系統(tǒng)來管理大量的數(shù)據(jù)信息。然而在嵌入式系統(tǒng)中，存儲(chǔ)容量都非常有限。如何充分利用這些有限的存儲(chǔ)空間，提高嵌入式數(shù)據(jù)庫的存儲(chǔ)空間利用率一直是倍受關(guān)注的研究課題。 目前，絕大多數(shù)嵌入式數(shù)據(jù)庫系統(tǒng)都使用B+樹索引機(jī)制。它的優(yōu)點(diǎn)是

2、效率高，能同時(shí)進(jìn)行隨機(jī)查找和順序查找，且能動(dòng)態(tài)維持平衡。然而根據(jù)研究表明B+樹索引機(jī)制平均空間利用率僅達(dá)到50％左右，這對(duì)存儲(chǔ)空間有限的嵌入式設(shè)備而言，B+樹索引機(jī)制存在浪費(fèi)存儲(chǔ)空間的缺點(diǎn)。 溢出技術(shù)思想就是當(dāng)結(jié)點(diǎn)發(fā)生分裂時(shí)，使用一個(gè)附加“溢出頁”來暫存溢出的關(guān)鍵字，從而達(dá)到延緩結(jié)點(diǎn)分裂、提高存儲(chǔ)空間利用率的目的。研究表明溢出技術(shù)比B+樹索引機(jī)制增加了20％-30％的存儲(chǔ)空間利用率。 本文的主要任務(wù)是研究和實(shí)現(xiàn)一個(gè)具有較

3、高存儲(chǔ)空間利用率的，面向嵌入式數(shù)據(jù)庫的索引機(jī)制。筆者首先介紹嵌入式數(shù)據(jù)庫中比較有代表意義的索引機(jī)制以及它們的優(yōu)缺點(diǎn)，再分析了B+樹索引機(jī)制的實(shí)現(xiàn)思想及其優(yōu)缺點(diǎn)，并結(jié)合溢出技術(shù)實(shí)現(xiàn)了一種改進(jìn)的索引機(jī)制-B＃樹索引機(jī)制；編寫程序?qū)崿F(xiàn)B＃樹索引機(jī)制，并替換開放源碼的嵌入式數(shù)據(jù)庫SOLite中B+樹索引機(jī)制，通過反復(fù)調(diào)試，將這個(gè)軟件系統(tǒng)移植到廣州致遠(yuǎn)公司的MAGICARM2410開發(fā)板上；最后，搭建軟件測(cè)試環(huán)境平臺(tái)，用腳本語言tcl編寫測(cè)試程序

4、進(jìn)行了五組測(cè)試實(shí)驗(yàn)，分別對(duì)B+樹和B＃樹索引機(jī)制在相同條件下的消耗時(shí)間和空間利用率兩個(gè)方面進(jìn)行測(cè)試和比較，并分析兩種索引機(jī)制測(cè)試結(jié)果出現(xiàn)差異的原因，從而得到實(shí)驗(yàn)結(jié)論：B＃樹索引機(jī)制能在多消耗少量時(shí)間基礎(chǔ)上，較大提高了嵌入式數(shù)據(jù)庫的存儲(chǔ)空間利用率，甚至在數(shù)據(jù)庫表中插入記錄較少記錄的時(shí)，它消耗的時(shí)間跟B+樹索引機(jī)制相當(dāng)，而此時(shí)嵌入式數(shù)據(jù)庫的存儲(chǔ)空間利用率最多能達(dá)到76％。這對(duì)實(shí)時(shí)性要求不高的嵌入式數(shù)據(jù)庫系統(tǒng)(如智能手機(jī)等移動(dòng)設(shè)備中利用嵌入式