嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)

太原科技大學(xué)碩士學(xué)位論文嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)姓名：解輝申請學(xué)位級別：碩士專業(yè)：計算機(jī)應(yīng)用技術(shù)指導(dǎo)教師：徐玉斌;李建偉20080701嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)中文摘要嵌入式數(shù)據(jù)庫是近些年才興起的一項新的數(shù)據(jù)庫技術(shù)，它以目前成熟的數(shù)據(jù)庫技術(shù)為基礎(chǔ)，針對嵌入式設(shè)備的具體特點(diǎn)，實(shí)現(xiàn)對移動設(shè)備和嵌入式設(shè)備上數(shù)據(jù)的存儲、組織和管理。傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)一般都是運(yùn)行在大型的計算機(jī)設(shè)備上，包括主機(jī)系統(tǒng)和各種各樣的服務(wù)器，隨著計算設(shè)備的日益小型化，數(shù)據(jù)庫的小型化也日益迫切。與大型計算機(jī)設(shè)備相比，這些小型的計算設(shè)備內(nèi)存較小，硬盤也較少，因此簡單地將原來的大型數(shù)據(jù)庫移植到小型設(shè)備上效果并不好，必須依據(jù)這些設(shè)備的特點(diǎn)專門設(shè)計相應(yīng)的數(shù)據(jù)庫系統(tǒng)。針對嵌入式系統(tǒng)的需求，文章主要在兩個方面進(jìn)行了研究。首先，本文在綜合分析當(dāng)前嵌入式數(shù)據(jù)庫系統(tǒng)的主要功能和發(fā)展現(xiàn)狀的基礎(chǔ)上，以實(shí)用、體積小、便于嵌入式應(yīng)用為主要追求目標(biāo)，針對嵌入式設(shè)備的具體特點(diǎn)，完成了詞法分析器、語法分析器以及索引機(jī)制優(yōu)化等方面的研究與設(shè)計，并在Ｌｉｎｕｘ下用Ｃ語言設(shè)計了一款能有效存儲、操作和管理實(shí)時數(shù)據(jù)信息的嵌入式數(shù)據(jù)庫，用以實(shí)現(xiàn)對嵌入式設(shè)備數(shù)據(jù)的統(tǒng)一管理。此數(shù)據(jù)庫具有微小內(nèi)核、系統(tǒng)尺寸可剪裁、良好的跨平臺性以及靈活的應(yīng)用編程接口等特點(diǎn)，支持ＡＣＩＤ事務(wù)，支持ＳＱＬ９２標(biāo)準(zhǔn)子集，無須獨(dú)立運(yùn)行的數(shù)據(jù)庫引擎，由程序直接調(diào)用相應(yīng)的ＡＰＩ函數(shù)就可以實(shí)現(xiàn)對數(shù)據(jù)的存取操作。通過與ＳＱＬＩＴＥ的測試比較可以看出，本文設(shè)計的數(shù)據(jù)庫在操作涉及的數(shù)據(jù)量較小的情況下，插入、查找和刪除性能均有較大提高，比較適合于應(yīng)用到數(shù)據(jù)操作較少的嵌入式設(shè)備。其次，基于ＡＲＭ硬件平臺，采用Ｌｉｎｕｘ操作系統(tǒng)，在已開發(fā)完成的嵌入式數(shù)據(jù)庫進(jìn)行數(shù)據(jù)管理的基礎(chǔ)上，設(shè)計了一個嵌入式實(shí)時數(shù)據(jù)采集系統(tǒng)。此系統(tǒng)很好的解決傳統(tǒng)數(shù)據(jù)采集系統(tǒng)存在的數(shù)據(jù)管理混亂、存儲效率低下等不足，在復(fù)雜環(huán)境下能夠?qū)Χ喾N數(shù)據(jù)信息進(jìn)行實(shí)時采集、高效存儲管理和快速傳輸。關(guān)鍵詞：嵌入式系統(tǒng)；嵌入式數(shù)據(jù)庫；ＡＲＭ；ＬＩＮＵＸＴｈｅＲｅｓｅａｒｃｈａｎｄＤｅｓｉｇｎｏｆＥｍｂｅｄｄｅｄＤａｔａｂａｓｅＧｒａｄｕａｔｅＮａｍｅ：ＸｉｅＨｕｉＭａｊｏｒ：ＣｏｍｐｕｔｅｒＡｐｐｌｉｅｄＴｅｃｈｎｏｌｏｇｙＬｉＪｉａｎ－ｗｅｉＤｉｒｅｃｔｅｄｂｙ：ＸｕＹｕ—ｂｉｎＡＢＳＴＲＡＣＴＥｍｂｅｄｄｅｄＤａｔａｂａｓｅｉｓｒｅｃｅｎｔｙｅａｒｓ．Ｂａｓｅｄｏｎａｎｅｗｔｅｃｈｎｏｌｏｇｙｏｆｄａｔａｍａｎａｇｅｍｅｎｔｒｉｓｉｎｇｉｎｍａｔｕｒｅｄａｔａｂａｓｅｔｅｃｈｎｏｌｏｇｙａｎｄｓｐｅｃｉａｌｅｍｂｅｄｄｅｄｏｎｄｅｖｉｃｅ，ｉｔｉｍｐｌｅｍｅｎｔｓｔｈｅｄａｔａ’Ｓｓｔｏｒａｇｅ，ｏｒｇａｎｉｚａｔｉｏｎａｎｄｍａｎａｇｅｍｅｎｔｍｏｂｉｌｅｄｅｖｉｃｅｓａｎｄｅｍｂｅｄｄｅｄｄｅｖｉｃｅｓ．Ｔｒａｄｉｔｉｏｎａｌｌｙ，ｄａｔａｂａｓｅｓｙｓｔｅｍｓｒｕｎｏｎｌａｒｇｅ—ｓｃａｌｅｃｏｍｐｕｔｅｒｅｑｕｉｐｍｅｎｔｔｈｅｃｏｍｐｕｔｅｒｉｎｃｌｕｄｉｎｇｈｏｓｔｃｏｍｐｕｔｅｒｓｙｓｔｅｍｓａｎｄａｌｌｋｉｎｄｓｏｆｓｅｒｖｅｒｓ．Ａｓｅｑｕｉｐｍｅｎｔｇｏｓｍａｌｌｅｒａｎｄｓｍａｌｌｅｒ，ｔｈｅｄａｔａｂａｓｅ’ＳｍｉｎｉａｔｕｒｉｚａｔｉｏｎｉＳｕｒｇｅｎｔｌｙ．Ｃｏｍｐａｒｅｄｗｉｔｈｌａｒｇｅ．ｓｃａｌｅｃｏｍｐｕｔｅｒｓ，ｔｈｅｓｅｓｍａｌｌ—ｓｃａｌｅｃｏｍｐｕｔａｔｉｏｎａｌｕｎｉｔｓａｒｅｃｈａｒａｃｔｅｒｉｚｅｄｂｙｓｍａｃｋａｓｍｅｍｏ巧ａｎｄｍｉｎｏｒｈａｒｄｗａｒｅｅｖｅｎｔｈｅｙｈａｖｅｎｏｈａｒｄｗａｒｅｓｕｃｈｈａｎｄ．ｈｅｌｄｄｅｖｉｃｅｓａｎｄｉｎｔｅｌｌｉｇｅｎｔｈｏｕｓｅｈｏｌｄｅｌｅｃｔｒｏｎｉｃｓ．Ｓｏ，ｉｔｉＳｎｏｔｆｅａｓｉｂｌｅｔｏｉｕｓｔｔｒａｎｓｐｌａｎｔｌａｒｇｅ．ｓｃａｌｅｄａｔａｂａｓｅｔｏｓｍａｌｌ－ｓｃａｌｅｄｅｖｉｃｅｓ．ｄａｔａｂａｓｅＷｅｍｕｓｔｃｈａｒａｃｔｅｒｓ．ｓｐｅｃｉａｌｌｙｄｅｓｉｇｎｅｄｓｙｓｔｅｍｓｔｏｆｉｔｆｏｒｔｈｅｄｅｖｉｃｅｓ’Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅｄｅｍａｎｄｏｆｔｈｅｅｍｂｅｄｄｅｄｓｙｓｔｅｍｓ，ｔｈｅｐａｐｅｒｗｉｌｌｓｈｏｗｆｕｎｃｔｉｏｎａｎｄｔｈｅｔｈｅｐｒｏｊｅｃｔｉｎｓｔａｔｅｔｗｏｐａｒｔｓ．Ｆｉｒｓｔｌｙ，ｔｈｒｏｕｇｈｏｆａｎａｌｙｚｉｎｇｔｈｅｍａｉｎｓｙｓｔｅｍａｃｔｕａｌｃｕｒｒｅｎｔｅｍｂｅｄｄｅｄｄａｔａｂａｓｅｓｙｎｔｈｅｔｉｃａｌｌｙ，ｔｈｅｅｍｂｅｄｄｅｄｄａｔａｂａｓｅ，ｔｈｅｇｏａｌｏｆｗｈｉｃｈｉｓａｖａｉｌａｂｉｌｉｔｙ，ｓｍａｌｌｓｉｚｅａｎｄｃｏｎｖｅｎｉｅｎｃｅｆｏｒｅｍｂｅｄｄｅｄａｐｐｌｉｃａｔｉｏｎｓｉｓ，ｄｅｓｉｇｎｅｄｒｅｆｅｒｓｔｏａｃｃｉｄｅｎｃｅａｎａｌｙｚｅｒ，ｓｙｎｔａｘａｎａｌｙｚｅｒａｎｄｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｏｆｉｎｄｅｘｍｅｃｈａｎｉｓｍａｎｄＳＯｏｎ．Ａｉｍｉｎｇａｔｔｈｅｃｏｎｃｒｅｔｅｆｅａｔｕｒｅｓｏｆｅｍｂｅｄｄｅｄｄｅｖｉｃｅｓ，ｔｈｅｅｍｂｅｄｄｅｄｄａｔａｂａｓｅｓｙｓｔｅｍｄｅｓｉｇｎｅｄｉｎＬｉｎｕｘ，ｗｈｉｃｈｃｏｕｌｄｓｔｏｒｅ，ｏｐｅｒａｔｅｉｎｆｏｒｍａｔｉｏｎａｐｐｌｉａｎｃｅｓｅｆｆｅｃｔｉｖｅｌｙ．ＩｔｓｕｐｐｏｒｔｓａｎｄｍａｎａｇｅｔｈｅｄａｔａｏｆｔｈｅＡＣＩＤａｆｆａｉｒ，ＳＱＬ９２ＩＩＩｓｔａｎｄａｒｄｓｕｂｓｅｔ，ｉｎｔｅｇｒａｔｅｄｗｉｔｈｉｔｓｃｏｎｃｒｅｔｅａｐｐｌｉｃａｔｉｏｎａｎｄｔｈｅｅｍｂｅｄｄｅｄＬｉｎｕｘａｎｄｄｏｅｓｎ’ｔｎｅｅｄｕｎａｔｔａｃｈｅｄｒｕｎｎｉｎｇｅｎｇｉｎｅ，ｔｈｅｐｒｏｇｒａｍｃａｌｌｓｉｔｓｒｅｌｅｖａｎｔＡＰＩｆｕｎｃｔｉｏｎｔｏｒｅａｌｉｚｅｔｈｅａｃｃｅｓｓｏｐｅｒａｔｉｏｎ．ＴｈｒｏｕｇｈｃｏｍｐａｒｉｎｇｗｉｔｈｔｈｅＳＱＬＩＴＥ，ｔｈｅｄａｔａｂａｓｅ’ｓｐｅｒｆｏｒｍａｎｃｅｈａｓｉｍｐｒｏｖｅｄｇｒｅａｔｌｖｗｈｉｌｅｉｎｖｏｌｖｉｎｇｒｅｌａｔｉｖｅｌｙｓｍａｌｌａｍｏｕｎｔｏｆｄａｔａ，ｗｈｉｃｈｉｓｆｉｔｆ．ｏｒｔｈｅｅｍｂｅｄｄｅｄｄｅｖｉｃｅｓｗｈｉｃｈｔｒｅａｔｌｅｓｓｄａｔａ．Ｓｅｃｏｎｄｌｙ，ｔｈｅａｒｔｉｃｌｅｂａｓｅｄｏｎＡＲＭａｎｄＬｉｎｕｘｏｐｅｒａｔｉｏｎｓｙｓｔｅｍ，ｕｓｉｎｇｔｈｅｅｍｂｅｄｄｅｄｄａｔａｂａｓｅｄｅｓｉｇｎｅｄｉｎｔｈｅｆｉｒｓｔｐａｒｔｔｏｍａｎａｇｅｔｈｅｒｅａｌ＿ｄａｔａｓｙｓｔｅｍｃａｎｔｏｄｅｓｉｇｎａｒｅａｌ—ｔｉｍｅｄａｔａａｃｑｕｉｓｉｔｉｏｎｓｙｓｔｅｍ．Ｔｈｅａｓｃｏｎｑｕｅｒｔｈｅｄｅｆｅｃｔｉｎｔｒａｄｉｔｉｏｎａｌｄａｔａａｃｑｕｉｓｉｔｉｏｎｓｙｓｔｅｍ．ｓｕｃｈｄａｔａｍａｎａｇｅｍｅｎｔｃｈａｏｓａｎｄ１０Ｗｓｔｏｒａｇｅｅｆｆｉｃｉｅｎｃｙ，ａｎｄｈａｖｅａｇｏｏｄｉｎｐｅｒｆｏｒｍａｎｃｅｏｆｅｆｆｉｃｉｅｎｔｓｔｏｒａｇｅａｎｄｒａｐｉｄｃｏｍｐｌｅｘｅｎｖｉｒｏｎｍｅｎｔ．ｔｒａｎｓｍｉｓｓｉｏｎｗｈｉｌｅｂｅｉｎｇＫｅｙｗｏｒｄｓ：ＥｍｂｅｄｄｅｄＳｙｓｔｅｍ；ＥｍｂｅｄｄｅｄＤａｔａｂａｓｅ；ＡＲＭ；ＬｉｎｕｘＩＶ承水諾話書吊本人鄭重聲明：所呈交的學(xué)位論文，是在導(dǎo)師指導(dǎo)下獨(dú)立完成的，學(xué)位論文的知識產(chǎn)權(quán)屬于太原科技大學(xué)。如果今后以其他單位名義發(fā)表與在讀期間學(xué)位論文相關(guān)的內(nèi)容，將承擔(dān)法律責(zé)任。除文中已經(jīng)注明引用的文獻(xiàn)資料外，本學(xué)位論文不包括任何其他個人或集體已經(jīng)發(fā)表或撰寫過的成果。學(xué)位論文作者（簽章）：２００年月日第一章緒論第一章緒論１．１研究背景及意義隨著計算環(huán)境的發(fā)展，數(shù)據(jù)庫系統(tǒng)也從集中式、分布式發(fā)展到今天的嵌入式數(shù)據(jù)庫系統(tǒng)。與通用的桌面系統(tǒng)不同，由于嵌入式系統(tǒng)沒有充足的內(nèi)存和磁盤資源，因此，不論是嵌入式的操作系統(tǒng)還是數(shù)據(jù)庫管理系統(tǒng)，都要占用最小的內(nèi)存和磁盤空間。若采用大型的商用數(shù)據(jù)庫管理系統(tǒng)，則不可避免的占用大量的內(nèi)存和磁盤空間，同時會產(chǎn)生大量的冗余數(shù)據(jù)，因此，它不能應(yīng)用于嵌入式系統(tǒng)的數(shù)據(jù)管理。長期以來，商業(yè)數(shù)據(jù)庫行業(yè)都在不停的追逐高性能的事務(wù)處理以及復(fù)雜的查詢處理能力，并制定了相應(yīng)的行業(yè)標(biāo)準(zhǔn)。但是對嵌入式數(shù)據(jù)庫系統(tǒng)來說，嵌入式應(yīng)用系統(tǒng)之間差別很大，因此它們對嵌入式數(shù)據(jù)庫系統(tǒng)的要求較高，這主要表現(xiàn)在：易于維護(hù)、高度可靠性和小巧性。嵌入式系統(tǒng)內(nèi)存較小，ＣＰＵ速度慢，因此，在嵌入式數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)的結(jié)構(gòu)和算法以及數(shù)據(jù)查詢處理算法非常關(guān)鍵，必須采用合適的策略和特殊的數(shù)據(jù)結(jié)構(gòu)、算法才能滿足用戶的需求…。１．２國內(nèi)外研究現(xiàn)狀嵌入式數(shù)據(jù)庫（ＥＤＢ）在移動計算平臺、家庭信息環(huán)境、通訊計算平臺、電子商務(wù)平臺等領(lǐng)域得到廣泛的應(yīng)用。正是基于這一事實(shí)，各國研究機(jī)構(gòu)紛紛展開了對嵌入式數(shù)據(jù)庫的研究，各大數(shù)據(jù)庫廠商也將開發(fā)相應(yīng)主打數(shù)據(jù)庫系統(tǒng)的嵌入式數(shù)據(jù)庫系統(tǒng)作為一個重要的發(fā)展方向。在國外，ＩＢＭ公司在ＤＢ２通用數(shù)據(jù)庫中推出了ＩＢＭＤＢ２Ｓａｔｅｌｌｉｔｅ和Ｅｖｅｒｙｐｌａｃｅ版本，它所提供的移動計算功能使移動辦公用戶獲得了與企業(yè)數(shù)據(jù)保持同步的能力。同時Ｉｎｆｏｒｍｉｘ公司也由旗下的Ｃｌｏｕｄｓｃａｐｅ公司推出了其移動解決方案旗艦產(chǎn)品的最新版本Ｃｌｏｕｄｓｃａｐｅ３．０，可以對包括從服務(wù)器到筆記本電腦，甚至到輕型信息設(shè)備，進(jìn)行數(shù)據(jù)管理。而作為移動計算的市場領(lǐng)先者Ｓｙｂａｓｅ公司多年前就敏銳地預(yù)見到計算設(shè)備小型化的發(fā)展趨勢，投入了大量的人員和資金對小型數(shù)據(jù)庫進(jìn)行研究與開發(fā)工作，并且在全球最早推出了移動與嵌入數(shù)據(jù)庫產(chǎn)品包－ＳｙｂａｓｅＳｔｕｄｉ０．ＳＯＬＡｎｙｗｈｅｒｅ在國內(nèi)，面對著嵌入式數(shù)據(jù)管理領(lǐng)域新的市場需求，東北大學(xué)軟件中心憑借著多年積累的數(shù)據(jù)庫系統(tǒng)和嵌入式系統(tǒng)的開發(fā)經(jīng)驗，在大型數(shù)據(jù)庫管理系統(tǒng)ＯｐｅｎＢＡＳＥ的基礎(chǔ)上，研制開發(fā)了嵌入式數(shù)據(jù)庫管理系統(tǒng)ＯｐｅｎＢＡＳＥＭｉｎｉ。北京人大金倉信息技術(shù)嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)有限公司也憑借其強(qiáng)大的研發(fā)實(shí)力，推出了具有自主知識版權(quán)的小金靈嵌入式移動關(guān)系數(shù)據(jù)庫系統(tǒng)ＫｉｎｇｂａｓｅＬｉｆｅ鹼１。以上這些嵌入式數(shù)據(jù)庫系統(tǒng)在功能和性能上具有一定的共性，比如說一般對資源要求較低，占用內(nèi)存空間較小，從幾十Ｋ到幾百Ｋ不等，支持Ｃ編程接口和標(biāo)準(zhǔn)ＳＱＬ子集的開發(fā)接口，支持ＯＤＢＣ或ＪＤＢＣ，能與支持其標(biāo)準(zhǔn)的任意數(shù)據(jù)庫交換數(shù)據(jù)，支持雙向數(shù)據(jù)交換能力，實(shí)現(xiàn)了中央數(shù)據(jù)庫與嵌入式數(shù)據(jù)庫間的數(shù)據(jù)雙向流動等。但這些數(shù)據(jù)庫系統(tǒng)也有各自不同的特點(diǎn)，鑒于嵌入式領(lǐng)域的特點(diǎn)，對嵌入式數(shù)據(jù)庫產(chǎn)品還很難形成統(tǒng)一的標(biāo)準(zhǔn)，對嵌入式數(shù)據(jù)庫管理系統(tǒng)的研究，也還有很多工作要做。１．３本文的研究目標(biāo)和研究內(nèi)容目標(biāo)是在研究現(xiàn)有嵌入式數(shù)據(jù)庫的基礎(chǔ)上設(shè)計和實(shí)現(xiàn)一個具有如下特征的嵌入式數(shù)據(jù)庫：１）零配置，程序驅(qū)動。２）實(shí)現(xiàn)部分的ＳＱＬ９２標(biāo)準(zhǔn)。３）數(shù)據(jù)庫完整存儲在磁盤文件中。４）提供簡單明了的ＡＰＩ。本文的研究內(nèi)容主要包括以下幾方面：１．第一章主要介紹了嵌入式數(shù)據(jù)庫系統(tǒng)研究的意義、國內(nèi)外的研究現(xiàn)狀以及本文研究的主要內(nèi)容。２．第二章主要介紹了嵌入式系統(tǒng)，嵌入式操作系統(tǒng)和嵌入式數(shù)據(jù)庫的特點(diǎn)和體系結(jié)構(gòu)。３．第三章對嵌入式數(shù)據(jù)庫進(jìn)行概要設(shè)計和詳細(xì)設(shè)計并初步實(shí)現(xiàn)一個可運(yùn)行的嵌入式數(shù)據(jù)庫。４．第四章基于第三章開發(fā)完成的ＥＤＢ的基礎(chǔ)上，設(shè)計并實(shí)現(xiàn)嵌入式數(shù)據(jù)采集系統(tǒng)。５．第五章對第三章開發(fā)的ＥＤＢ和第四章開發(fā)的數(shù)據(jù)采集系統(tǒng)進(jìn)行測試。６．第六章進(jìn)行總結(jié)與展望。２第二二章嵌入式系統(tǒng)與嵌入式數(shù)據(jù)庫第二章嵌入式系統(tǒng)與嵌入式數(shù)據(jù)庫２．１嵌入式系統(tǒng)２．１．１嵌入式系統(tǒng)的定義嵌入式系統(tǒng)（ＥｍｂｅｄｄｅｄＳｙｓｔｅｍ）是以應(yīng)用為中心，以計算機(jī)技術(shù)為基礎(chǔ)，并且軟硬件可裁剪，適用于應(yīng)用系統(tǒng)對功能、可靠性、成本、體積、功耗有嚴(yán)格要求的專用計算機(jī)系統(tǒng)∞３。它一般由嵌入式微處理器、外圍硬件設(shè)備、嵌入式操作系統(tǒng)以及用戶的應(yīng)用程序等四個部分組成，用于實(shí)現(xiàn)對其他設(shè)備的控制、監(jiān)視或管理等功能。２．１．２嵌入式系統(tǒng)的特點(diǎn)嵌入式系統(tǒng)的核心是嵌入式微處理器，嵌入式微處理器一般具備以下４個特點(diǎn)Ｈ３：（１）對實(shí)時多任務(wù)有很強(qiáng)的支持能力，能完成多任務(wù)并且有較短的中斷響應(yīng)時間，從而使內(nèi)部的代碼和實(shí)時內(nèi)核的執(zhí)行時間減少到最低限度。（２）具有功能很強(qiáng)的存儲區(qū)保護(hù)功能。這是由于嵌入式系統(tǒng)的軟件結(jié)構(gòu)已模塊化，而為了避免在軟件模塊之間出現(xiàn)錯誤的交叉作用，需要設(shè)計強(qiáng)大的存儲區(qū)保護(hù)功能，同時也有利于軟件診斷。（３）可擴(kuò)展的處理器結(jié)構(gòu)，以能最迅速地開展出滿足應(yīng)用的最高性能的嵌入式微處理器。（４）嵌入式微處理器必須功耗很低，尤其是用于便攜式的無線及移動的計算和通信設(shè)備中靠電池供電的嵌入式系統(tǒng)更是如此。２．１．３嵌入式系統(tǒng)的應(yīng)用嵌入式系統(tǒng)的應(yīng)用前景是非常廣泛的，人們將會無時無處不接觸到嵌入式產(chǎn)品，從家里的洗衣機(jī)、電冰箱，到作為交通工具的自行車、小汽車，到辦公室里的遠(yuǎn)程會議系統(tǒng)等等。當(dāng)嵌入式的無線電芯片的價格可被接受時，它的應(yīng)用可能會無所不在。在家中、辦公室、公共場所，人們可能會使用數(shù)十片甚至更多這樣的嵌入式無線電芯片，將一些電子信息設(shè)備甚至電氣設(shè)備構(gòu)成無線網(wǎng)絡(luò)，在車上、旅途中，人們利用這樣的嵌入式無線電芯片可以實(shí)現(xiàn)遠(yuǎn)程辦公、遠(yuǎn)程遙控，真正實(shí)現(xiàn)把網(wǎng)絡(luò)隨身攜帶瞄３。２．２嵌入式操作系統(tǒng)２．２．１嵌入式操作系統(tǒng)的定義嵌入式操作系統(tǒng)是一種支持嵌入式系統(tǒng)應(yīng)用的操作系統(tǒng)軟件，它是嵌入式系統(tǒng)３嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)（包括硬、軟件系統(tǒng)）極為重要的組成部分，通常包括與硬件相關(guān)的底層驅(qū)動軟件、系統(tǒng)內(nèi)核、設(shè)備驅(qū)動接口、通信協(xié)議、圖形界面、標(biāo)準(zhǔn)化瀏覽器等ｂｒｏｗｓｅｒ［６］。嵌入式操作系統(tǒng)具有通用操作系統(tǒng)的基本特點(diǎn)，如能夠有效管理越來越復(fù)雜的系統(tǒng)資源；能夠把硬件虛擬化，使得開發(fā)人員從繁忙的驅(qū)動程序移植和維護(hù)中解脫出來；能夠提供庫函數(shù)、驅(qū)動程序、工具集以及應(yīng)用程序。２．２．２嵌入式操作系統(tǒng)的特點(diǎn)嵌入式操作系統(tǒng)具有以下一些特點(diǎn)哺１：（１）體積小。嵌入式系統(tǒng)有別于一般的計算機(jī)處理系統(tǒng)，它不具備像硬盤那樣大容量的存儲介質(zhì)，而大多使用閃存（ＦｌａｓｈＭｅｍｏｒｙ）作為存儲介質(zhì)。這就要求嵌入式操作系統(tǒng)只能運(yùn)行在有限的內(nèi)存中，不能使用虛擬內(nèi)存，中斷的使用也受到限制。因此，嵌入式操作系統(tǒng)必須結(jié)構(gòu)緊湊，體積微小。（２）實(shí)時性。大多數(shù)嵌入式系統(tǒng)都是實(shí)時系統(tǒng)，而且多是強(qiáng)實(shí)時多任務(wù)系統(tǒng)，要求相應(yīng)的嵌入式操作系統(tǒng)也必須是實(shí)時操作系統(tǒng)（ＲＴＯＳ）。實(shí)時操作系統(tǒng)作為操作系統(tǒng)的一個重要分支已成為研究的一個熱點(diǎn)，主要探討實(shí)時多任務(wù)調(diào)度算法和可調(diào)度性、死鎖解除等問題。（３）特殊的開發(fā)調(diào)試環(huán)境。提供完整的集成開發(fā)環(huán)境是每一個嵌入式系統(tǒng)開發(fā)人員所期待的。一個完整的嵌入式系統(tǒng)的集成開發(fā)環(huán)境一般需要提供的工具是編譯／連接器、內(nèi)核調(diào)試／跟蹤器和集成圖形界面開發(fā)平臺。其中的集成圖形界面開發(fā)平臺包括編輯器、調(diào)試器、軟件仿真器和監(jiān)視器等。２．３嵌入式數(shù)據(jù)庫２．３．１嵌入式數(shù)據(jù)庫定義嵌入式數(shù)據(jù)庫是指運(yùn)行在本機(jī)上、不用啟動服務(wù)端的輕型數(shù)據(jù)庫，它與應(yīng)用程序緊密集成，被應(yīng)用程序所啟動，并伴隨應(yīng)用程序的退出而終止。２．３．２嵌入式數(shù)據(jù)庫的特點(diǎn)嵌入式數(shù)據(jù)庫系統(tǒng)有如下主要特點(diǎn)ｎ’：（１）占用存儲空間小（２）可靠性、可管理性和安全性（３）互操作性和可移植性。２．３．３嵌入式數(shù)據(jù)庫的關(guān)鍵技術(shù)為了使嵌入式系統(tǒng)能更好地發(fā)揮其作用，主要涉及以下幾種關(guān)鍵技術(shù)發(fā)展方向：（１）系統(tǒng)的高可靠性技術(shù)（２）系統(tǒng)整體的微型化（３）數(shù)據(jù)同步／復(fù)制技術(shù)（４）系統(tǒng)可定制能力（５）系統(tǒng)可移植性與多平臺支持（６）網(wǎng)絡(luò)支持與數(shù)據(jù)。４第三章嵌入式數(shù)據(jù)庫的分析與設(shè)計第三章嵌入式數(shù)據(jù)庫的分析與設(shè)計本章將討論如何分析和設(shè)計一個嵌入式數(shù)據(jù)庫系統(tǒng)，包括數(shù)據(jù)庫的功能需求、性能需求、運(yùn)行環(huán)境、開發(fā)環(huán)境、系統(tǒng)架構(gòu)以及各模塊和模塊間的關(guān)系等。３．１嵌入式數(shù)據(jù)庫的體系結(jié)構(gòu)嵌入式ＥＤＢ是指可在嵌入式設(shè)備中獨(dú)立運(yùn)行的一種數(shù)據(jù)庫系統(tǒng)，用以處理大量的、時效性強(qiáng)且有嚴(yán)格時序的數(shù)據(jù)，它以高可靠性、高實(shí)時性和高信息吞吐量為目標(biāo)，其數(shù)據(jù)的正確性不僅依賴于邏輯結(jié)果，而且依賴于邏輯結(jié)果產(chǎn)生的時間隨１，嵌入式系統(tǒng)基本結(jié)構(gòu)如圖３－１所示。圖３－１嵌入式系統(tǒng)基本結(jié)構(gòu)目前嵌入式系統(tǒng)開發(fā)中，在嵌入式數(shù)據(jù)庫問題上的多數(shù)看法是，嵌入式數(shù)據(jù)庫從本質(zhì)上說是一個“內(nèi)存數(shù)據(jù)庫”，是一個由應(yīng)用程序管理的內(nèi)存緩沖池，它在系統(tǒng)中的作用就是一個供多個實(shí)時任務(wù)共同使用的共享數(shù)據(jù)區(qū)。這種數(shù)據(jù)庫實(shí)際上是一個嵌入在用戶應(yīng)用軟件中的與應(yīng)用程序不可分割的部分，其功能主要是數(shù)據(jù)的存和取，不具有獨(dú)立性，不是一個真正意義上的數(shù)據(jù)庫系統(tǒng)睜１。一個完整的嵌入式實(shí)時數(shù)據(jù)庫系統(tǒng)除了包括內(nèi)存數(shù)據(jù)庫外，還應(yīng)當(dāng)含有歷史數(shù)據(jù)庫和數(shù)據(jù)庫管理系統(tǒng)ＤＢＭＳ及提供給用戶的接口函數(shù)，整個數(shù)據(jù)庫可由ＤＢＭＳ完成對數(shù)據(jù)庫的具體配置及各種操作，例如系統(tǒng)運(yùn)行前根據(jù)實(shí)際需要對內(nèi)存數(shù)據(jù)庫中的記錄節(jié)點(diǎn)進(jìn)行增減等配置操作，嵌入式數(shù)據(jù)庫庫的模塊結(jié)構(gòu)如圖３－２所示。５嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)圖３—２嵌入式ＥＤＢ的模塊結(jié)構(gòu)嵌入式數(shù)據(jù)庫的關(guān)鍵是數(shù)據(jù)模型的確立，它決定了數(shù)據(jù)被訪問和操作的方式，應(yīng)６３．２嵌入式數(shù)據(jù)庫的數(shù)據(jù)模型用程序的性能和可靠性也大部分取決于此。目前嵌入式環(huán)境下的數(shù)據(jù)庫系統(tǒng)多數(shù)采用了關(guān)系模型結(jié)構(gòu)，這也是商用數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)模型，該模型結(jié)構(gòu)是利用二維表來實(shí)現(xiàn)數(shù)據(jù)存儲，利用索引訪問和查詢數(shù)據(jù)，這種模型結(jié)構(gòu)是建立在嚴(yán)格的數(shù)學(xué)基礎(chǔ)上的，結(jié)構(gòu)簡單靈活，獨(dú)立性好，但在嵌入式環(huán)境下的內(nèi)存開銷和數(shù)據(jù)冗余較大，用戶必須對其進(jìn)行優(yōu)化，增加了開發(fā)數(shù)據(jù)庫系統(tǒng)的難度；有些嵌入式數(shù)據(jù)庫則采用了網(wǎng)狀模型結(jié)構(gòu)，該模型通過指針來確定數(shù)據(jù)間的顯式連接關(guān)系，它比關(guān)系模型中利用冗余數(shù)據(jù)和索引文件要節(jié)約大量的存儲空間，具有一定的數(shù)據(jù)獨(dú)立性和共享特性，運(yùn)行效率較高，而且由于它避免了索引操作，比關(guān)系型數(shù)據(jù)庫模式要節(jié)省存儲空間，數(shù)據(jù)操作速度也更快ｎ０１。但是這種模型結(jié)構(gòu)比較復(fù)雜，尤其當(dāng)嵌入式系統(tǒng)規(guī)模增大時，其數(shù)據(jù)庫的結(jié)構(gòu)變得非常龐大，可能會影響到系統(tǒng)的實(shí)時性能。圖３—３所示的是在相同數(shù)目的記錄下，關(guān)系模型和網(wǎng)狀模型的系統(tǒng)開銷比較，從圖中可以得知，網(wǎng)狀模型因為避免了索引操作使得其開銷要小于關(guān)系模型ｎｕ。７嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)３．４嵌入式數(shù)據(jù)庫的運(yùn)行過程和開發(fā)過程３．４．１運(yùn)行過程ＥＤＢ的運(yùn)行過程是一個在數(shù)據(jù)庫引擎總控模塊的控制下進(jìn)行的有序協(xié)調(diào)的過程。ＥＤＢ的運(yùn)行過程分為５個步驟ｎ別。（１）數(shù)據(jù)庫系統(tǒng)初始化ＥＤＢ的初始化調(diào)用ＡＰＩ的初始化函數(shù)啟動，初始化數(shù)據(jù)庫系統(tǒng)的全局控制結(jié)構(gòu)，取數(shù)據(jù)庫的運(yùn)行狀態(tài)信息，分配數(shù)據(jù)庫內(nèi)存空間，ＥＤＢ系統(tǒng)初始化時還將對數(shù)據(jù)字典表進(jìn)行確認(rèn)ｎ朝。（２）打開或創(chuàng)建字典表在數(shù)據(jù)庫系統(tǒng)第一次啟動時，即數(shù)據(jù)庫第一次被裝入時，該字典表是不存在的，在這里初始化時將創(chuàng)建字典表，為后續(xù)操作做好準(zhǔn)備。在數(shù)據(jù)庫系統(tǒng)以后的啟動過程中，如果該字典己經(jīng)存在，數(shù)據(jù)庫系統(tǒng)初始化時將確認(rèn)字典表是否已存在，此時如果檢查到字典表不存在，將重新打開一個字典表。（３）數(shù)據(jù)庫具體操作ＥＤＢ系統(tǒng)及其具體的字典表操作初始化后就可以在數(shù)據(jù)庫操作引擎控制下調(diào)用數(shù)據(jù)存取模塊或數(shù)據(jù)庫維護(hù)模塊對數(shù)據(jù)庫進(jìn)行各種操作了。對基本表的主要操作有：創(chuàng)建基本表、插入記錄、刪除記錄、修改記錄、查找、排序、備份和恢復(fù)以及碎片整理等，我們將在第四章對重要功能的操作流程和實(shí)現(xiàn)進(jìn)行詳細(xì)介紹。（４）關(guān)閉字典表關(guān)閉字典表后可以釋放已經(jīng)分配的輸出緩沖區(qū)空間、結(jié)果集結(jié)構(gòu)空間、控制頭結(jié)構(gòu)、列定義信息等內(nèi)部結(jié)構(gòu)變量空間，并可以釋放該字典表占用的類信息結(jié)構(gòu)?！ǎ担╆P(guān)閉數(shù)據(jù)庫系統(tǒng)通過調(diào)用ＡＰＩ的關(guān)閉函數(shù)實(shí)現(xiàn)。主要工作是關(guān)閉數(shù)據(jù)庫，釋放ＥＢＤ系統(tǒng)申請的全局結(jié)構(gòu)變量空間即ＤＢ結(jié)構(gòu)，釋放并分配給ＥＤＢ的空間。實(shí)際運(yùn)行過程中，數(shù)據(jù)庫系統(tǒng)初始化后，若字典表創(chuàng)建成功或己存在的條件下，可對字典表進(jìn)行多次的打開操作和關(guān)閉操作ｎ４１。３．４．２開發(fā)過程ＥＤＢ的開發(fā)過程是按照軟件工程的思想來組織實(shí)施的。開發(fā)過程依次經(jīng)歷了原型階段，需求分析階段，概要設(shè)計階段，詳細(xì)設(shè)計階段，編碼階段，測試階段，以及維護(hù)階段。８第三章嵌入式數(shù)據(jù)庫的分析與設(shè)計在原型階段，主要是在臺式機(jī)上圍繞著ＥＤＢ的一些基本功能，如表創(chuàng)建，記錄的插入、刪除、修改等操作，在ＰＣ機(jī)上予以實(shí)現(xiàn)，以獲得對將要開發(fā)的系統(tǒng)的一個初步的認(rèn)識。實(shí)際開發(fā)的原型是在Ｌｉｎｕｘ環(huán)境下實(shí)現(xiàn)的。在需求分析階段，主要是根據(jù)用戶的要求，進(jìn)一步細(xì)化系統(tǒng)應(yīng)該具有的功能和性能要求，和用戶達(dá)成一致，并為下一步的系統(tǒng)概要設(shè)計打好基礎(chǔ)。在概要設(shè)計階段，基本上確定了系統(tǒng)的體系結(jié)構(gòu)，確定了系統(tǒng)向用戶所提供的ＡＰＩ接口，確定了系統(tǒng)各個組成模塊之間的關(guān)系，確定了系統(tǒng)的一些核心數(shù)據(jù)結(jié)構(gòu)。在詳細(xì)設(shè)計階段，主要是設(shè)計各個模塊具體函數(shù)的偽代碼或流程圖實(shí)現(xiàn)。在編碼階段，主要工作就是編碼并調(diào)試，以實(shí)現(xiàn)系統(tǒng)預(yù)定的功能ｎ朝。在測試階段，測試工作非常重要，除了在系統(tǒng)開發(fā)的各個階段都貫穿了一些測試的內(nèi)容外，還專門安排了一個比較長時間的測試階段。測試階段包含了功能測試，健壯性測試，性能測試等多個測試環(huán)節(jié)，經(jīng)過測試階段，系統(tǒng)的質(zhì)量和穩(wěn)定性都得到了比較大的提高。３．５概要設(shè)計３．５．１功能需求嵌入式數(shù)據(jù)庫系統(tǒng)作為ＤＢｂｌＳ，它應(yīng)當(dāng)具備以下功能：（１）數(shù)據(jù)定義和數(shù)據(jù)存儲這部分內(nèi)容包括元組的表示，屬性的表示，索引的表示，元組和屬性的關(guān)系，各種數(shù)據(jù)類型的表示和存儲，如整型（長整型、短整型）、字符型、實(shí)型、日期類型、時間類型等。數(shù)據(jù)文件表的格式和組織，索引文件表的格式和組織，元數(shù)據(jù)的組織和存儲等等ｎ鍆。（２）數(shù)據(jù)存取能實(shí)現(xiàn)對數(shù)據(jù)庫的基本操作，如建立表，建立索引，刪除表，刪除索引，對元組的檢索和更新操作（插入、刪除、修改），其它的操作還包括排序、壓縮、整理等功能。必須支持ＳＯＬＤＤＬ和ＤＭＬ一個較完備的子集。（３）訪問接口嵌入式數(shù)據(jù)庫系統(tǒng)需要提供共應(yīng)用程序開發(fā)人員使用的訪問接口，而且應(yīng)當(dāng)是符合ＳＯＬ標(biāo)準(zhǔn)的訪問接口。（４）緩沖區(qū)管理為提高系統(tǒng)性能，減少磁盤Ｉ／ｏ操作，對數(shù)據(jù)表文件的讀寫必須提供緩沖機(jī)制，９嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)操作系統(tǒng)的文件系統(tǒng)提供的文件緩沖是遠(yuǎn)為不夠的，嵌入式數(shù)據(jù)庫系統(tǒng)自身應(yīng)該有出色的緩沖區(qū)管理功能ｎ引。（５）內(nèi)存管理占用最少的內(nèi)存資源和內(nèi)存資源可控制是嵌入式數(shù)據(jù)庫的首要目標(biāo)。合適的內(nèi)存管理策略，不僅有助于達(dá)到這個目標(biāo)，而且有助于保護(hù)系統(tǒng)的堆空間，增強(qiáng)系統(tǒng)的可靠性。（６）數(shù)據(jù)庫管理工具嵌入式數(shù)據(jù)庫還需要一組實(shí)用工具，供用戶在線或離線管理數(shù)據(jù)庫，這樣的工具包括數(shù)據(jù)庫元數(shù)據(jù)的報表打印、數(shù)據(jù)庫一致性的檢查、數(shù)據(jù)庫表的數(shù)據(jù)導(dǎo)入導(dǎo)出工具、碎片整理和壓縮等。３．５．２性能需求衡量嵌入式數(shù)據(jù)庫的性能要求有兩個方面，一是作為ＤＢＭＳ系統(tǒng)，其性能如何，數(shù)據(jù)庫中最多數(shù)據(jù)表的個數(shù)，數(shù)據(jù)表的最大文件長度，每個表的最大元組個數(shù)，每元組的最多屬性個數(shù)，每個表上建立的最多索引數(shù)等等，二是作為嵌入式系統(tǒng)軟件，其性能如何，包括內(nèi)存資源占用，ＣＰＵ開銷等。前文我們說過，嵌入式數(shù)據(jù)庫和應(yīng)用密切相關(guān)，所以有些性能指標(biāo)比如響應(yīng)時間或事務(wù)處理平均時間就難以確定，我們只能給出合理的參考值要求（針對特定的硬件平臺）。當(dāng)然，大多數(shù)的指標(biāo)還是可以確定的。其它性能要求還包括對可靠性的要求，嵌入式數(shù)據(jù)庫系統(tǒng)要保證在無人管理的情況下長時間的無故障運(yùn)行ｎ６１。而且，在系統(tǒng)發(fā)生故障不能恢復(fù)的時候，也不可干擾或破壞設(shè)備中其它部件的正常工作。嵌入式數(shù)據(jù)庫系統(tǒng)還應(yīng)當(dāng)具備良好的可伸縮性，根據(jù)不同的應(yīng)用能夠為系統(tǒng)進(jìn)行定制，比如定制所需的子模塊，定制緩沖區(qū)的大小等。嵌入式數(shù)據(jù)庫系統(tǒng)還應(yīng)滿足較好的可移植性，能夠提供開放的接口和其它系統(tǒng)互操作。３．５．３運(yùn)行環(huán)境和開發(fā)環(huán)境ＥＤＢ目前支持的平臺是各種嵌入式Ｌｉｎｕｘ，具體產(chǎn)品包括各種高端的消費(fèi)類電子設(shè)備，需要為ＥＤＢ搭建嵌入式開發(fā)交叉平臺，這個平臺需要的部件包括：主機(jī)（Ｈｏｓｔ）：它是開發(fā)人員的工作機(jī)，一般是桌面系統(tǒng)，分析、設(shè)計和文檔撰寫以及代碼編寫、大部分的調(diào)試工作等都在主機(jī)上完成ｎ７１。目前的主機(jī)是ＲｅｄＨａｔＬｉｎｕｘ７．３，目標(biāo)機(jī)（Ｔａｒｇｅｔ）：它是ＥＤＢ實(shí)際運(yùn)行的平臺，該平臺必須運(yùn)行嵌入式Ｌｉｎｕｘ操作系統(tǒng)。當(dāng)ＥＤＢ系統(tǒng)基本成型后就需要從主機(jī)下載到目標(biāo)機(jī)進(jìn)行進(jìn)一步的調(diào)試，本系統(tǒng)的目標(biāo)機(jī)是基于ＡＲＭ９平臺的嵌入式Ｌｉｎｕｘ系統(tǒng)。１０第三章嵌入式數(shù)據(jù)庫的分析與設(shè)計３．６詳細(xì)設(shè)計嵌入式數(shù)據(jù)庫設(shè)計流程如圖３－４所示，主要包括ＳＱＬ解析、詞法分析、語法分析、ＳＱＬＡＰＩ設(shè)計、事物的調(diào)度和執(zhí)行策略、脫機(jī)移動事物、日志回滾和故障恢復(fù)幾個方面。由于嵌入式數(shù)據(jù)庫系統(tǒng)中的功能較多，中的重要功能設(shè)計和實(shí)現(xiàn)進(jìn)行介紹。限于篇幅，僅對嵌入式數(shù)據(jù)庫系統(tǒng)ＤＤＬ模式文件ＤＭＬ語法ＤＤＬ語法解析模塊解析模塊數(shù)據(jù)定義模塊晶僻荔＿廣Ｉ簇菇“。蘭塑至豎堡苧ｌｌ；苗芝緩沖區(qū)內(nèi)部數(shù)據(jù)結(jié)構(gòu)圖３—４ＥＤＢ的體系結(jié)構(gòu)ＳＱＬＡＰＩ數(shù)據(jù)訪問模塊３．６．１ＳＯＬ解析ＳＱＬ語句中具有獨(dú)立意義的單詞，稱之為單位體，有時也稱為原予。詞法分析的主要目的就是分隔單位體，并將這些單位體按照先后順序插入單位體鏈表。每種單位體的規(guī)則和意義各不相同，比如單引號，在單引號內(nèi)的其他符號都失效，而兩個連續(xù)的單引號才表示一個單引號字符。從功能上分析，單位體可以分成７類：括號、子查詢、數(shù)值運(yùn)算、比較運(yùn)算、邏輯運(yùn)算、變量以及其他控制符號。若從可見性分析，單位體可以分成兩類，即可見單位體和非可見單位體。非可見單位體主要是一些抽象的單位體，比如邏輯單位體。任意一條合法Ｗｈｅｒｅ子句，最后經(jīng)過運(yùn)算必須得到一個唯一的抽象的非可見單位體，即邏輯單位體ｎ８｜。若為１，記錄符合要求，需要寫入結(jié)果集：反之，則不符合要求，需要跳過。則表示當(dāng)前解析ＳＱＬ語句總體目標(biāo)是將ＳＱＬ語句轉(zhuǎn)換成系統(tǒng)可以理解的格式，這就是語法分析的工作。這里所謂系統(tǒng)可以理解的格式，是指按照ＳＱＬ９２標(biāo)準(zhǔn)，判別該ＳＱＬ語句的類型（查詢、刪除、修改記錄等），并根據(jù)不同的類型作不同的語法分析。比如查詢語句，總體而言可以分成三個部分。ｓｅｌｅｃｔ與ｆｒｏｍ之間的部分主要描述結(jié)果集嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)輸出格式，而ｆｒｏｍ與ｗｈｅｒｅ（若無ｗｈｅｒｅ子句，則到ＳＱＬ語句結(jié)尾）之間的部分描述本ＳＱＬ語句所涉及的表，ｗｈｅｒｅ子句則是表示查詢的條件。語法分析的任務(wù)之一就是將這三個部分分開并留給以后的系統(tǒng)使用，這也是語法分析的結(jié)果之一。在語法分析的過程中，系統(tǒng)需要檢查當(dāng)前ＳＱＬ語句的合法性，若不合法則報錯退出，并給出出錯信息。每當(dāng)語法分析程序解析出一條語句時，就向語句執(zhí)行列表中插入一個節(jié)點(diǎn)，這ＴＡＢＬＥ個節(jié)點(diǎn)的內(nèi)容包括了該條語句的類型及相應(yīng)的參數(shù)信息。如識別出是ＣＲＥＡＴ語句，就將插入節(jié)點(diǎn)的ｔｙｐｅ域設(shè)置為ＳＱＬ—ＣＲＥＡＴＥ—ＴＡＢＬＥ（為每一種語句都定義了一個標(biāo)記以標(biāo)識），并將ＣＲＥＡＴＴＡＢＬＥ的相關(guān)參數(shù)信息轉(zhuǎn)換為相應(yīng)的數(shù)據(jù)結(jié)構(gòu)放入節(jié)點(diǎn)的ｓｔｍｔ域中。這樣當(dāng)整個腳本文件解析完畢后，所有的語句就會按順序組成一個語句執(zhí)行列表。執(zhí)行時，遍歷這個語句執(zhí)行列表。通過判斷每個節(jié)點(diǎn)的類型，就能知道所要執(zhí)行的具體函數(shù)。如判斷到該節(jié)點(diǎn)的ｔｙｐｅ為ＳＱＬ—ＣＲＥＡＴＥ～ＴＡＢＬＥ，相應(yīng)的建表函數(shù)為ＥＤＢ＿Ｃｒｅａｔｅ（）。３．６．２語法解析語法解析是數(shù)據(jù)庫實(shí)現(xiàn)要面對的重要問題，此數(shù)據(jù)庫中采用的語法是ＳＱＬ語法，符合采用ＢＮＦ范式。顯然，語法解析屬于編譯的范疇，雖然有關(guān)課程中已經(jīng)詳細(xì)介紹了詞法分析和語法分析的理論，但是離開具體的實(shí)現(xiàn)還是有相當(dāng)?shù)木嚯x，特別是對于ＳＱＬ這樣復(fù)雜龐大的語法，為了構(gòu)建完善且可靠的詞法分析器和語法分析器有一定的難度和工作量?？上驳氖牵冢眨睿椋澜绱嬖谥嚓P(guān)的優(yōu)秀工具，這些工具能夠幫助我們實(shí)現(xiàn)一個專業(yè)的詞法和語法分析器，這便是Ｆｌｅｘ和Ｙａｃｃ。有了這些自動工具，數(shù)據(jù)庫開發(fā)者要做的主要工作便是為ＳＱＬ語法尋找合適的數(shù)據(jù)結(jié)構(gòu)，以及為ｆｌｅｘ和ｙａｃｃ書寫正確的腳本。一般的，樹型的數(shù)據(jù)結(jié)構(gòu)對于表示ＳＱＬ語法是合適的，當(dāng)然考慮到每個語法的特點(diǎn)，我們可能需要為樹做某種程度的變形，而不是標(biāo)準(zhǔn)的樹結(jié)構(gòu)。有了合適的數(shù)據(jù)結(jié)構(gòu)，下一步的工作就是在ｆｌｅｘ和ｙａｃｃ的腳本中指示它們該如何一步一步的生成ＳＱＬ解析樹。３．６．３存儲管理嵌入式數(shù)據(jù)庫的存儲管理有兩個方面，其一是外部存儲管理，即如何組織數(shù)據(jù)文件、索引文件，二是內(nèi)部存儲管理。由于嵌入式系統(tǒng)內(nèi)存資源的緊張，如何使用內(nèi)存資源必然是嵌入式軟件的熱門話題和重要技術(shù)點(diǎn)。對于ＥＤＢ，內(nèi)部存儲管理涉及到兩個關(guān)鍵問題。第一個問題是緩沖區(qū)管理，它也和外部存儲管理密切相關(guān)。緩沖區(qū)機(jī)制是指為１２第三章嵌入式數(shù)據(jù)庫的分析與設(shè)計減少Ｆｌａｓｈ或磁盤Ｉ／０在ＥＤＢ和二級存儲器之間架設(shè)了一塊內(nèi)存空間，其職責(zé)是在查詢處理過程中讓數(shù)據(jù)存取模塊得到所需的元組，數(shù)據(jù)存取模塊通過某種訪問方法從這些緩沖區(qū)讀寫元組，寫入元組也是寫到緩沖區(qū)上，而不需要直接訪問Ｆｌａｓｈ文件或磁盤系統(tǒng)。這種機(jī)制可以大大減少對磁盤的訪問，其原因是很多時候我們要訪問的元組就己經(jīng)在緩沖區(qū)上了。當(dāng)ＥＤＢ初始化時，緩沖區(qū)數(shù)目將是一個可以設(shè)置的參數(shù)，不同的應(yīng)用能夠靈活的設(shè)置緩沖區(qū)的大小。我們?yōu)槊總€關(guān)系都設(shè)置一定大小的緩沖區(qū)（本數(shù)據(jù)庫設(shè)為８Ｋ），由于頁長度固定，這樣此關(guān)系對應(yīng)的緩沖區(qū)能夠裝入８個頁。當(dāng)需要訪問不在緩沖區(qū)中的頁時，需要將緩沖區(qū)中的某個頁寫回Ｆｌａｓｈ或磁盤，并調(diào)入待訪問的頁。這樣，為盡量減少顛簸，本系統(tǒng)采用ＬＲＵ算法。第二個問題涉及到動態(tài)內(nèi)存的申請和釋放。本數(shù)據(jù)庫是用Ｃ／Ｃ＋＋實(shí)現(xiàn)的，不可避免的牽涉到大量的ｍａｌｌｏｃ和ｆｒｅｅ操作，從系統(tǒng)堆中取得或還出內(nèi)存。嵌入式系統(tǒng)中堆是一種需要特別慎重對待的重要系統(tǒng)資源。系統(tǒng)的ｍａｌｌｏｃ允許用戶指定任意大小的區(qū)塊，在系統(tǒng)堆頻繁的分配和釋放動態(tài)內(nèi)存，特別是長度各異的內(nèi)存，容易造成堆支離破碎，甚至可能使系統(tǒng)崩潰。系統(tǒng)堆越雜亂，區(qū)塊大小越是參差不等，找出一個適當(dāng)?shù)目臻e區(qū)塊的時間更長，效率更低，所謂的通用性必然犧牲效率。另外，ＥＤＢ的動態(tài)內(nèi)存占用需要處于可控制的范圍。鑒于這些考慮，本數(shù)據(jù)庫使用了動態(tài)內(nèi)存管理辦法取代了系統(tǒng)的ｍａｌｌｏｃ和ｆｒｅｅ，它就是所謂的預(yù)分配＋內(nèi)存池技術(shù)。其主要思想如下：在ＥＤＢ初始化時，根據(jù)應(yīng)用規(guī)模我們?yōu)椋牛模骂A(yù)先分配一定數(shù)量的內(nèi)存，以后ＥＤＢ所有的動態(tài)內(nèi)存申請都只從這塊內(nèi)存中取得，這樣做一個明顯的好處是基本上不會干擾系統(tǒng)堆。這塊內(nèi)存除非ＥＤＢ系統(tǒng)退出，否則這塊內(nèi)存將一直為ＥＤＢ所占。然后，我們在這塊內(nèi)存上使用內(nèi)存池技術(shù)，即將它分成若干個塊（ｃｈｕｎｋ）‘每個塊由一定數(shù)量的等長的內(nèi)存片斷（ｆｒａｇｍｅｎｔ）組成，比如某個塊，它由２０個片斷組成，每個片斷都是８字節(jié)長，我們稱該塊為“８字節(jié)一塊’’。通過分析ＥＤＢ內(nèi)部各個動態(tài)數(shù)據(jù)結(jié)構(gòu)的長度，以及數(shù)據(jù)庫表的屬性字段長度和元組長度等因素，我們將內(nèi)存池分成如下２０種塊：”８字節(jié)一塊”，’’１６字節(jié)一塊＂，”２４一字節(jié)塊”，依８字節(jié)為步進(jìn)（ｓｔｅｐ）一直到“１２８字節(jié)一塊”，然后是“２５６字節(jié)一塊”，”５１２字節(jié)一塊”，＂１０２４字節(jié)一塊”和“２０４８字節(jié)一塊”。超過２０４８字節(jié)的片斷在嵌入式數(shù)據(jù)庫應(yīng)用中很少出現(xiàn)，我們簡單的將它交由系統(tǒng)堆處理。需要說明的是，這加塊并不是靜態(tài)的在系統(tǒng)初始時被劃分死的，而是在需要它的時候才建立，有些情況下內(nèi)存池中可能就只活躍著２種塊，比如“８字節(jié)一塊＂和“１６字節(jié)一塊”。嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)將塊中的空閑片斷由一個鏈表連接起來，并由一個指針指向表頭，這個鏈表稱為空閑表（ｆｒｅｅｌｉｓｔ）。一共需要２０個空閑表。值得注意的是，在實(shí)現(xiàn)中無須擔(dān)心空閑表會消耗掉可觀的內(nèi)存，我們可以直接在空閑片斷上建立這種鏈表。當(dāng)然，我們需要存儲這２０個空閑表的表頭，空閑表帶來的額外內(nèi)存開銷也僅限于此。圖３—５給出了空閑表和塊的示意圖。圖３—５空閑表和和空閑塊不葸圖圖３－５中４號鏈表表頭指向一個“６４字節(jié)一塊＂，該塊含有４個片斷，某個片斷中含有一個０指針表示鏈表的結(jié)束。當(dāng)ＥＤＢ中的某個模塊提出動態(tài)內(nèi)存申請時，內(nèi)存池將視其大小從特定塊中取出一個合適的空閑片斷交付給該模塊，同時修改空閑鏈表的表頭指針?！昂线m”尊循的原則是：如果申請的長度ｎ在１２８字節(jié)以下的，那么總是交付長度為Ｌ的空閑片斷，Ｌ是８的整數(shù)倍值中大于ｎ的最小數(shù)；若申請的長度大于１２８且小于等于２５６，那么交付２５６字節(jié)的片斷，大于２５６小于等于５１２則交付５１２字節(jié)的片斷，更大長度的依此類推，直至２０４８字節(jié)。３．６．４ＳＱＬ預(yù)處理及簡單優(yōu)化通過上面的算法，可以得到計算機(jī)能夠理解的單位體棧（也稱為單位體鏈表、原子鏈表），這樣就具備了執(zhí)行該ＳＱＬ語句的必要條件。為了提高效率，需要對ＳＱＬ語句做部分預(yù)處理，將冗余信息去除掉。冗余的信息是指可以直接計算出結(jié)果的信息，比如無效括號、子查詢、數(shù)值運(yùn)算、比較運(yùn)算、集合運(yùn)算以及邏輯運(yùn)算等等。具體為：（１）無效括號是指括號內(nèi)只含有一個單位體：這樣就可以把該單位體前后的左括號和右括號刪除；（２）子查詢必須要在掃描之前獲得其結(jié)果，這樣做的好處是避免在掃描每條記錄時再去計算其結(jié)果，其優(yōu)化結(jié)果為一個集合單位體；（３）數(shù)值運(yùn)１４第三章嵌入式數(shù)據(jù)庫的分析與設(shè)計算包括混合運(yùn)算，若這些運(yùn)算符前后不是變量，則可提前計算；比較運(yùn)算主要包括＞、＜、＝、＞＝、＜＝、！＝，同樣，若這些運(yùn)算符前后不是變量的話，則可以立即計算其結(jié)果，并生成一個邏輯單位體，并代替原先單位體；今集合運(yùn)算主要是指ＩＮ，ＡＮＹ，ＡＬＬ，ＮＯＴＩＮ，ＥＸＩＳＴＳ，ＮＯＴＥＸＩＳＴＳ運(yùn)算，其后面一般是一個集合類型的單位體（子查詢的（４）邏輯運(yùn)算主要是結(jié)果就是一個集合單位體），計算結(jié)果也是一個邏輯單位體；ｎｏｔ，ａｎｄ，ｏｒ三種邏輯運(yùn)算符，若其前后為邏輯單位體，則可立即合并。預(yù)處理后的單位體棧，只剩下與變量相關(guān)的單位體系列。這里的變量是指具體某個表的某個屬性．預(yù)處理的算法是基于不斷優(yōu)化的思想，也就是說，設(shè)一個優(yōu)化次數(shù)變量，每次循環(huán)開始時將優(yōu)化次數(shù)Ｐ置０，以后每優(yōu)化一次，該變量加１，到最后判斷該變量是否為０，若為０，則說明已經(jīng)沒有可以再優(yōu)化的單位體系列，也就是說達(dá)到了最優(yōu)化，這時可以退出循環(huán)。之所以采用不斷優(yōu)化的算法，是因為在前一次優(yōu)化的基礎(chǔ)上，有時候還有可能進(jìn)行二次優(yōu)化ｎ９｜。單位體棧（或稱原子鏈表、單位體鏈表）經(jīng)過優(yōu)化后，需要根據(jù)ＳＱＬ語句的類型送交不同的ＳＱＬ執(zhí)行模塊。由于ＥＤＢ系統(tǒng)相對來說是小型系統(tǒng)，數(shù)據(jù)庫原理中的一些更高級的優(yōu)化思想就沒有在系統(tǒng)中過多考慮。３．６．５重要ＳＯＬ語句的設(shè)計前面已經(jīng)提到，基本表是嵌入式數(shù)據(jù)庫系統(tǒng)操作的核心，而基本表的創(chuàng)建和刪除又是嵌入式數(shù)據(jù)庫系統(tǒng)中最基本的操作之一，嵌入式數(shù)據(jù)庫系統(tǒng)的其它操作都必須在創(chuàng)建成功的基本表基礎(chǔ)上進(jìn)行乜０｜?，F(xiàn)對本系統(tǒng)使用的主要數(shù)據(jù)結(jié)構(gòu)描述如下：ｓｔｒｕｃｔＤｂ｛、ｃｈａｒ木ｚＮａｍｅ；／木Ｎａｍｅｏｆｔｈｉｓｄａｔａｂａｓｅ木／Ｂｔｒｅｅ魯ｐＢｔ；｜嶙ＴｈｅＢ★Ｔｒｅｅｓｔｒｕｃｔｕｒｅｆｏｒｔｈｉｓｄａｔａｂａｓｅｆｉｌｅ★｜ＨａｓｈｔｂｌＨａｓｈ；｜嘎Ａｌｌｔａｂｌｅｓｉｎｄｅｘｅｄｂｙｎａｍｅ★ｌＨａｓｈｉｄｘＨａｓｈ；｜’Ａｌｌ（ｎａｍｅｄ）ｉｎｄｉｃｅｓｉｎｄｅｘｅｄｂｙｎａｍｅ’｜ＨａｓｈｔｒｉｇＨａｓｈ；ｌ嚏Ａｌｌｔｒｉｇｇｅｒｓｉｎｄｅｘｅｄｂｙｎａｍｅ★｜ＨａｓｈａＦＫｅｙ；ｕ８ｉｎＴｒａｎｓ；ｕｌ６ｆｌａｇｓ；ｖｏｉｄ毒ｐＡｕｘ；卜Ｆｏｒｅｉｇｎｋｅｙｓｉｎｄｅｘｅｄｂｙｔｏ－ｔａｂｌｅ★｜／木０：ｎｏｔｗｒｉｔａｂｌｅ．１：Ｔｒａｎｓａｃｔｉｏｎ．２－Ｃｈｅｃｋｐｏｉｎｔ木／產(chǎn)Ｆｌａｇｓａｓｓｏｃｉａｔｅｄ、析ｔｈｔｈｉｓｄａｔａｂａｓｅ堆／｝肆Ａｕｘｉｌｉａｒｙｄａｔａ．ＵｓｕａｌｌｙＮＵＬＬ彝｝ｆｒｅｅｐＡｕｘ木／ｖｏｉｄ（木ｘＦｒｅｅＡｕｘ）（ｖｏｉｄ棗）；／幸Ｒｏｕｔｉｎｅｔｏ）；ｌ５嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)ｓｔｒｕｃｔＴａｂｌｅ｛凈Ｎａｍｅｏｆｔｈｅｔａｂｌｅ★｜ｃｈａｒ＊ｚＮａｍｅ；ｉｎｔｎＣｏｌ；｜’Ｎｕｍｂｅｒｏｆｃｏｌｕｍｎｓｉｎｔｈｉｓｔａｂｌｅ＾｜Ｃｏｌｕｍｎ＊ａＣｏｌ；ｉｎｔｉＰＫｅｙ；凈Ｉｎｆｏｒｍａｔｉｏｎａｂｏｕｔｅａｃｈｃｏｌｍｎｎ＇｜嚴(yán)Ｉｆｎｏｔｌｅｓｓｔｈｅｎ０，ｕｓｅａＣｏｌ［ｉＰＫｅｙ】ａｓｔｈｅｐｒｉｍａｒ），ｋｅｙ宰／Ｉｎｄｅｘ卑ｐＩｎｄｅｘ；｜毒ＬｉｓｔｏｆＳＱＬｉｎｄｅｘｅｓｏｎｔｈｉｓｔａｂｌｅ．’｛ｈａｔｔｎｕｍ；嚴(yán)ＲｏｏｔＢＴｒｅｅｎｏｄｅｆｏｒｔｈｉｓｔａｂｌｅ（ｓｅｅｎｏｔｅａｂｏｖｅ）棗／Ｓｅｌｅｃｔ＊ｐＳｅｌｅｃｔ；降ＮＵＬＬｆｏｒｔａｂｌｅｓ．Ｐｏｉｎｔｓｔｏｄｅｆｍｉｆｉｏｎｉｆａｖｉｅｗ．★｜ｕ８ｈａｓＰｒｉｍＫｅｙ；ｌ’Ｔｒｅｅｉｆｔｈｅｒｅｅｘｉｓｔｓｕ８ａｐｒｉｍａｒｙｋｅｙ＾ＩｋｅｙＣｏｎｆ；｜★ＷｈａｔｔｏｄｏｉｎｃａｓｅｏｆｕｎｉｑｕｅｎｅｓｓｃｏｎｆｌｉｃｔｏｎｉＰＫｅｙ★｜ｏｎＴｒｉｇｇｅｒ★ｐＴｒｉｇｇｅｒ；｜是ＬｉｓｔｏｆＳＱＬｔｒｉｇｇｅｒｓｔｈｉｓｔａｂｌｅ＾｜ｔｈｉｓｔａｂｌｅ‘ｌＦＫｅｙ★ｐＦＫｅｙ；｜嚕Ｌｉｎｋｅｄｌｉｓｔｏｆａｌｌｆｏｒｅｉｇｎｋｅｙｓｉｎ＞；ｓｔｒｕｃｔ?Ｉｎｄｅｘ｛ｃｈａｒ＊ｚＮａｍｅ；ｉｎｔ卜Ｎａｍｅｏｆｔｈｉｓｉｎｄｅｘ★｜ｔｈｅｔａｂｌｅｕｓｅｄｂｙｔｈｉｓｉｎｄｅｘ★｜ｎＣｏｌｕｍｎ；ｌ蠢ＮｕｍｂｅｒｏｆｃｏｌｕｍｎｓｉｎＳＱＬｔａｂｌｅｂｅｉｎｇｃｏｎｔａｉｎｉｎｇｉｎｔ＊ａｉＣｏｌｕｍｎ；｜肆ＷｈｉｃｈＴａｂｌｅ★ｐＴａｂｌｅ；｜嶙Ｔｈｅｈａｔｃｏｌｕｍｎｓａｒｅｕｓｅｄｂｙｔｈｉｓｉｎｄｅｘ．１ｓｔｉｓ０★｜ｉｎｄｅｘｅｄ＾｜ｍｕｍ；｜鼻Ｐａｇｅｒｏｏｔｏｆｔｈｉｓｉｎｄｅｘｉｎｄａｔａｂａｓｅｆｉｌｅ囊｜ｂｙｕ８ａｕｔｏＩｎｄｅｘ；嚴(yán)Ｔｒｕｅｉｆｉｓａｕｔｏｍａｔｉｃａｌｌｙｃｒｅａｔｅｄ（ｅｘ：ＵＮＩＱＵＥ）幸／Ｉｎｄｅｘ＊ｐＮｅｘｔ；“產(chǎn)Ｔｈｅｎｅｘｔｉｎｄｅｘａｓｓｏｃｉａｔｅｄｗｉｔｈｔｈｅｓａｍｅｔａｂｌｅ宰／。）；ｓｔｒｕｃｔ一Ｔｏｋｅｎ｛嚴(yán)Ｔｅｘｔｏｆｔｈｅｔｏｋｅｎ．ＮｏｔＮＵＬＬ－ｔｅｒｍｉｎａｔｅｄｔ宰／ｃｏｎｓｔｃｈａｒ木ｚ：）；（１）創(chuàng)建基本表創(chuàng)建基本表通過ＡＰＩ調(diào)用ｃｒｅａｔｅｔａｂｌｅ實(shí)現(xiàn)。由使用者輸入基本表名和該基本表的屬性列定義，在接口處理層將用戶的輸入轉(zhuǎn)變?yōu)椋牛模孪到y(tǒng)能識別和操作的創(chuàng)建表結(jié)構(gòu)。當(dāng)遇到ＣＲＥＡＴＥ，ＴＡＢＬＥ和表名以后，ＣｒｅａｔｅＴａｂｌｅ函數(shù)被調(diào)用。此函數(shù)首先用新建表的表名與字典記錄表中的表名比較，如果新建表表名已經(jīng)存在，則提示錯誤退１６第三章嵌入式數(shù)據(jù)庫的分析與設(shè)計出，否則分配并初始化表結(jié)構(gòu)，最后產(chǎn)生打開主表的操作碼，具體操作如圖３—６所不ｏ在事弗中捕八一條記錄＇ｌｌ結(jié)束圖３－６基本表創(chuàng)建流程圖基本表創(chuàng)建源代碼：ｓｔａｔｉｃｉｎｔＣｒｅａｔｅＴａｂｌｅ（Ｂｔｒｅｅ木ｐＢｔ，ｉｎｔ木ｐｉＴａｂｌｅ）｛ＭｅｍＰａｇｅ奉ｐＲｏｏｔ；ＰｇｎｏｐｇｎｏＲｏｏｔ；ｉｎｔｒｅ；ｒｃ＝ａｌｌｏｃａｔｅＰａｇｅ（ｐＢｔ，＆ｐＲｏｏｔ，＆ｐｇｎｏＲｏｏｔ，０）；ｉｆ（ｒｅ）ｒｅｔｕｒｎｒｃ；ｚｅｒｏＰａｇｅ（ｐＢｔ，ｐＲｏｏｔ）；ｐａｇｅｒｕｎｒｅｆ（ｐＲｏｏｔ）；木ｐｉＴａｂｌｅ＝（ｉｎｔ）ｐｇｎｏＲｏｏｔ；ｒｅｔｕｒｎ０Ｋ；）１７嵌入式數(shù)據(jù)厙的設(shè)計與買現(xiàn)（２）刪除基本表調(diào)用ｄｅｌｅｔｅＴａｂｌｅ函數(shù)來刪除基本表?；静僮鬟^程是：首先從字典表中查找要刪除的表名，若是表名不存在，則提示錯誤退出，否則清空表中的記錄，然后刪除表結(jié)構(gòu)和與此表相關(guān)的索引結(jié)構(gòu)，最后在字典表中刪除包含此表名的記錄以及與此表相關(guān)的索引名記錄，具體流程如圖３－７所示。Ｉ在事弗表審刪除包耆此表信息記錄ｊＲｌ索弓Ｉ記暈◆ｌ基本表刪除源代碼：ｖｏｉｄ紂柬｜圖３－７基本表刪除流程圖ＤｅｌｅｔｅＴａｂｌｅ（ＤＢ木ｄｂ，Ｔａｂｌｅ宰ｐＴａｂｌｅ）｛ｈａｔｉ；Ｉｎｄｅｘ水ｐｌｎｄｅｘ．木ｐＮｅｘｔ；ＦＫｅｙ木ｐＦＫｅｙ，宰ｐＮｅｘｔＦＫｅｙ；ｉｆ（ｐＴａｂｌｅ一－－－０）ｒｅｔｕｒｎ；產(chǎn)Ｄｅｌｅｔｅａｌｌｉｎｄｉｃｅｓａｓｓｏｃｉａｔｅｄｗｉｔｈｔｈｉｓｔａｂｌｅ’ｌｆｏｒ（ｐＩｎｄｅｘ＝ｐＴａｂｌｅ－＞ｐｌｎｄｅｘ；ｐＩｎｄｅｘ；ｐＩｎｄｅｘ鄧Ｎｅｘｔ）第三章嵌入式數(shù)據(jù)庫的分析與設(shè)計｛ｐＮｅｘｔ＝ｐｌｎｄｅｘ－＞ｐＮｅｘｔ；ａｓｓｅｒｔ（ｐＩｎｄｅｘ－＞ｉＤｂ－－－－ｐＴａｂｌｅ一＞ｉＤｂｌｌ（ｐＴａｂｌｅ一＞ｉＤａ０＆＆ｐｌｎｄｅｘ一＞ｉＤｂ—１））；Ｄｅｌｅｔｅｌｎｄｅｘ（ｄｂ，ｐＩｎｄｅｘ）；）ｆｏｒ（ｐＦＫｅｙ＝ｐＴａｂｌｅ－＞ｐＦＫｅｙ；ｐＦＫｅｙ；ｐＦＫｅｙ＝ｐＮｅｘｔＦＫｅｙ）｛ｐＮｅｘｔＦＫｅｙ２ｐＦＫｅｙ－＞ｐＮｅｘｔＦｒｏｍ；ａｓｓｅｒｔ（ｐＴａｂｌｅ－＞ｉＤｂ＜ｄｂ－＞ｎＤｂ）；Ｆｒｅｅ（ｐＦＫｅｙ）；）｜粵ＤｅｌｅｔｅｔｈｅＴａｂｌｅｓｔｒｕｃｔｕｒｅＲｓｅｌｆ．?★｜ｆｏｒ（ｉ＝０；ｉ＜ｐＴａｂｌｅ－＞ｎＣｏｌ；ｉ＋＋）｛．ＥＤＢＦｒｅｅ（Ｉ：ＩＴａｂｌｅ－＞ａＣｏｌ［ｉ］．ｚＮａｍｅ）；ＥＤＢＦｒｅｅ（ｐＴａｂｌｅ一＞ａＣｏｌ［ｉ］．ｚＤｆｌｔ）；ＥＤＢＦｒｅｅ（ｐＴａｂｌｅ一＞ａＣｏｌ［ｉ］．ｚＴｙｐｅ）；＞ＥＤＢＦｒｅｅ（ｐＴａｂｌｅ－＞ｚＮａｍｅ）；ＥＤＢＦｒｅｅ（ｐＴａｂｌｅ－＞ａＣ０１）；ＥＤＢＳｅｌｅｃｔＤｅｌｅｔｅ（ｐＴａｂｌｅ－＞ｐＳｅｌｅｃｔ）；ＥＤＢＦｒｅｅ（ｐＴａｂｌｅ）；＞（３）插入記錄插入記錄的主要過程為：首先在字典表中查找要插入記錄的表名，若不存在，則提示出錯退出。然后比較列的列表參數(shù)，如果列名與表中的列名不符，則提示出錯退出。如果表名和列名都正確，那么插入數(shù)據(jù)到表中。如果此表沒有索引，那么插入操作完成。如果此表有索引，那么還要更新索引表，具體流程如圖３－８所示。１９嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)圖３－８記錄插入流程圖記錄插入源代碼：ｖｏｉｄＤａｔａｌｎｓｅｒｔ（／幸Ｐａｒｓｅｒｃｏｎｔｅｘｔ棗／產(chǎn)Ｎａｍｅｏｆｔａｂｌｅｉｎｔｏｗｈｉｃｈｗｅａｒｅｉｎｓｅｒｔｉｎｇ棗／／木Ｌｉｓｔｏｆｖａｌｕｅｓｔｏｂｅｉｎｓｅｒｔｅｄ木／件ＡＳＥＬＥＣＴｓｍｔｅｍｅｍｔｏｕｓｅａｓＰａｒｓｅ宰ｐＰａｒｓｅ，ＳｒｃＬｉｓｔ宰ｐＴａｂＬｉｓｔ，ＥｘｐｒＬｉｓｔ木ｐＬｉｓｔ，Ｓｅｌｅｃｔ木ｐＳｅｌｅｃｔ，ｔｈｅｄａｔａｓｏｕｒｃｅ木／ＩｄＬｉｓｔ木ｐＣｏｌｕｍｎ，ｉｎｔｏｎＥｒｒｏｒｐＣｏｌｕｍｎｎａｍｅｓｃｏｒｒｅｓｐｏｎｄｉｎｇｔｏＩＤＬＩＳＴ．牛／嚴(yán)Ｈｏｗｔｏｈａｎｄｌｅｃｏｎｓｔｒａｉｎｔｅｒｒｏｒｓ?／）｛第三章嵌入式數(shù)據(jù)庫的分析與設(shè)計ｄｂ＝ｐＰａｒｓｅ一＞ｄｂ；產(chǎn)定位需要插入數(shù)據(jù)的表宰／ｚＴａｂ＝ｐＴａｂＬｉｓｔ－＞ａ［Ｏ］．ｚＮａｍｅ；ｎＣｏｌｕｍｎ＝ｐＬｉｓｔ－＞ｎＥｘｐｒ；ｄｕｍｍｙ．ｎＳｒｃ＝０：ｆｏｒ（ｉ＝０；ｉ＜ｎＣｏｌｕｍｎ；ｉ＋＋１ｉｆ（ｐＣｏｌｕｍｎ）｛ｆｏｒ（ｉ＝０；ｉ＜ｐＣｏｌｕｍｎ一＞ｎｌｄ；ｉ＋＋）｛ｐＣｏｌｕｍｎ一＞ａ［ｉ］．ｉｄｘ‘２－１；）ｆｏｒ（ｉ＝０；ｉ＜ｐＣｏｌｕｍｎ－＞ｎＩｄ；ｉ＋＋）｛ｆｏｒ（ｊ＝０；ｊ＜ｐＴａｂ－＞ｎＣｏｌ；ｊ＋＋）｛ｉｆ（ＥＤＢＳｔｒｌＣｍｐ（ｐＣｏｌｕｍｎ一＞ａ【ｉ】．ｚＮａｍｅ，ｐＴａｂ?＞ａＣｏｌ［ｊ］．ｚＮａｍｅ）一０）｛ｐＣｏｌｕｎｍ一＞ａ［ｉ】．ｉｄｘ２ｊ；ｉｆ（ｊ一－－ｐＴａｂ－＞ｉＰＫｅｙ）｛ｋｅｙＣｏｌｕｍｎ＝ｉ：）ｂｒｅａｋ；）｝ｉｆ（ｊ＞＝ｐＴａｂ－＞ｎＣ０１）｛ｉｆ（ＥＤＢＩｓＲｏｗｉｄ（ｐＣｏｌｕｍｎ－＞ａ［ｉ】．ｚＮａｍｅ））｛ｋｅｙＣｏｌｕｍｎ＝ｉ；）ｅｌｓｅ｛ＥＤＢＥｒｒｏｒＭｓｇ（ｐＰａｒｓｅ．”ｔａｂｌｅ％ＳｈａｓｎＯｃｏｌｕｍｎｎａｍｅｄ％ｓ＂，ｐＴａｂＬｉｓｔ，０，ｐＣｏｌｕｍｎ－＞ａ［ｉ】．ｚＮａｍｅ）；ｐＰａｒｓｅ－＞ｎＥｒｒ＋＋；ｇｏｔｏｉｎｓｅｒｔ＿ｃｌｅａｎｕｐ；））｝２１）（４）更新記錄更新函數(shù)的運(yùn)行過程與刪除函數(shù)相似，唯一的不同就是把刪除記錄改為更新記錄，具體流程如３—９所示。圖３－９更新記錄流程圖更新記錄源代碼：ｖｏｉｄＥＤＢＵｐｄａｔｅ（Ｐａｒｓｅ宰ｐＰａｒｓｅ，產(chǎn)１１１ｅｐａｒｓｅｒｃｏｎｔｅｘｔ?／ＳｒｃＬｉｓｔ＊ｐＴａｂＬｉｓｔ，產(chǎn)Ｔｈｅｔａｂｌｅｉｎｗｈｉｃｈｗｅｓｈｏｕｌｄｃｈａｎｇｅｔｈｉｎｇｓ幸／２２第三章嵌入式數(shù)據(jù)庫的分析與設(shè)計ＥｘｐｒＬｉｓｔ?ｐＣｈａｎｇｅｓ．／宰Ｔｈｉｎｇｓｔｏｂｅｃｈａｎｇｅｄ宰／Ｅｘｐｒ木ｐＷｈｅｒｅ．／奉ＴｈｅＷＨＥＲＥｃｌａｕｓｅ．Ｍａｙｂｅｎｕｌｌ木／ｉｎｔｏｎＥｒｒｏｒ嚴(yán)Ｈｏｗｔｏｈａｎｄｌｅｃｏｎｓｔｒａｉｎｔｅｒｒｏｒｓ掌／）｛／／定位所需更新的表ａＸＲｅｆ＝ＥＤＢＭａｌｌｏｃ（ｓｉｚｅｏｆ（ｉｎｔ）＋ｐＴａｂ一＞ｎＣ０１）；ｉｆ（ａ№ｆ釜Ｏ１ｇｏｔｏｕｐｄａｔｅ＿ｃｌｅａｎｕｐ；ｆｏｒ（ｉ＝０；ｉ＜ｐＴａｂ－＞ｎＣｏｌ；ｉ＋＋）ａＸＲｅｆ［ｉ】２－１；ｉｆ（ｒｏｗ＿ｔｒｉｇｇｅｒｓｅｘｉｓｔ）｛ｎｅｗｌｄｘ＝ｐＰａｒｓｅ－＞ｎＴａｂ＋＋；’ｏｌｄｌｄｘ＝ｐＰａｒｓｅ一＞ｎＴａｂ＋＋；）ｐＴａｂＬｉｓｔ一＞ａ【Ｏ］．ｉＣｕｒｓｏｒ＝ｉＣｕｒ＝ｐＰａｒｓｅ?＞ｎＴａｂ＋＋；ｆｏｒ（ｐｌｄｘ＝ｐＴａｂ一＞ｐｌｎｄｅｘ；ｐＩｄｘ；ｐｌｄｘ＝ｐｌｄｘ－＞ｐＮｅｘｔ）｛ｐＰａｒｓｅ－＞ｎＴａｂ＋＋；）ｃｈｎｇＲｅｃｎｏ２０：ｆｏｒ（ｉ＝０；ｉ＜ｐＣｈａｎｇｅｓ?＞ｎＥｘｐｒ；ｉ＋＋）｛ｉｆ（ＥｘｐｒＲｅｓｏｌｖｅｌｄｓ（ｐＰａｒｓｅ，ｐＴａｂＬｉｓｔ，０，ｐＣｈａｎｇｅｓ－＞ａ［ｉ］．ｐＥｘｐｒ））｛ｇｏｔｏｕｐｄａｔｅ＿ｃｌｅａｎｕｐ；）ｉｆ（ＥｘｐｒＣｈｅｃｋ（ｐＰａｒｓｅ，ｐＣｈａｎｇｅｓ－＞ａ［ｉ】．ｐＥｘｐｒ，０，０））｛ｇｏｔｏｕｐｄａｔｅ＿ｃｌｅａｎｕｐ；）ｆｏｒ（ｊ＝Ｏ；ｊ＜ｐＴａｂ－＞ｎＣｏｌ；ｊ＋＋）｛ｉｆ（ＳｔｒｌＣｍｐ（ｐＴａｂ一＞ａＣｏｌ［ｊ］．ｚＮａｍｅ，ｐＣｈａｎｇｅｓ一＞ａ［ｉ】．ｚＮａｍｅ）一０）｛ｉｆ（ｊ一－－ｐＴａｂ一＞ｉＰＫｅｙ）｛ｃｈｎｇＲｅｃｎｏ＝１；ｐＲｅｃｎｏＥｘｐｒ＝ｐＣｈａｎｇｅｓ?＞ａ［ｉ］．ｐＥｘｐｒ；）ａＸＲｅｆ［ｊ］＝ｉ；．２３嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)ｉｆ（ｊ＞＝ｐＴａｂ－＞ｎＣ０１）｛ｉｆ（ＩｓＲｏｗｉｄ（ｐＣｈａｎｇｅｓ－＞ａ［ｉ】．ｚＮａｍｅ））｛ｃｈｎｇＲｅｃｎｏ＝１；ｐＲｅｃｎｏＥｘｐｒ＝ｐＣｈａｎｇｅｓ－＞ａ［ｉ］．ｐＥｘｐｒ；｝ｅｌｓｅ｛ＥｒｒｏｒＭｓｇ（ｐＰａｒｓｅ，”ｎｏｇｏｔｏｕｐｄａｔｅ＿ｃｌｅａｎｕｐ；ｓｕｃｈｃｏｌｕｍｎ．％ｓ”，ｐＣｈａｎｇｅｓ一＞ａ【ｉ】．ｚＮａｍｅ）；＞ｆｏｒ（ｎｌｄｘ＝ｎｌｄｘＴｏｔａｌ＝０，ｐｌｄｘ＝ｐＴａｂ一＞ｐｌｎｄｅｘ；ｐｌｄｘ；ｐｌｄｘ＝ｐｌｄｘ－＞ｐＮｅｘｔ，ｎＩｄｘＴｏｔａｌ＋＋）｛ｉｆ（ｃｈｎｇＲｅｃｎｏ）｛ｉ＝Ｏ；｝ｅｌｓｅ｛ｆｏｒ（ｉ＝０；ｉ＜ｐｌｄｘ－＞ｎＣｏｌｕｍｎ；ｉ＋＋）｛ｉｆ（ａＸＲｅｆ［ｐＩｄｘ?＞ａｉＣｏｌｕｍｎ［ｉ］］＞＝０＞）ｉｆ（ｉ＜ｐＩｄＸ一＞ｎＣｏｌｕｍｎ）ｍｄ刈斗；１ｂｒｅａｋ；＞（５）查找記錄ＥＤＢＳｅｌｅｃｔＮｅｗ函數(shù)實(shí)現(xiàn)記錄的查詢操作。查詢分為３種情況。第一種就是沒有ｗｈｅｒｅ條件，該查詢?yōu)榘从涗浱柌樵?，?shí)現(xiàn)的是所有記錄從頭到尾的查詢，這種情況下Ｓｅｌｅｃｔ，結(jié)構(gòu)體中的指針為空：第二種是按屬性列（不是索弓ＩＹＵ）查詢，這種情況與２４第三章嵌入式數(shù)據(jù)庫的分析．ｏｊ設(shè)計第一種類似，只是從頭到尾都根據(jù)ｗｈｅｒｅ條件中的列表達(dá)式比較，符合則放入到棧中；第三種是索引查詢，此種方式在數(shù)據(jù)量大的時候?qū)崿F(xiàn)了快速查詢，也是本文要重點(diǎn)講述的查詢方式，具體流程如圖３－１０所示?！皥D３—１０查找記錄流程圖查找記錄源代碼：Ｓｅｌｅｃｔ幸ＥＤＢＳｅｌｅｃｔＮｅｗ（ＥｘｐｒＬｉｓｔ＾ｐＥＬｉｓｔ．｜嚏ｗｈｉｃｈｃｏｌｕｍｎｓｔｏｉｎｃｌｕｄｅｉｎｔｈｅｒｅｓｕｌｔ★｜ＳｒｃＬｉｓｔ鼻ｐＳｒｃ，ｊ｜嘎ｔｈｅＦＲＯＭｃｌａｕｓｅ一一ｗｈｉｃｈｔａｂｌｅｓｔｏｓｃａｎ｜ｌ。Ｅｘｐｒ喪ｐＷｈｅｒｅ、｜愧ｔｈｅＷＨＥＲＥｃｌａｕｓｅ＾ｌＥｘｐｒＬｉｓｔ鼻ｐＧｒｏｕｐＢｙ，｜嚏ｔｈｅＧＲＯＵＰＢＹｃｌａｕｓｅ＾｜Ｅｘｐｒ木ｐＨａｖｉｎｇ．／宰ｔｈｅＨＡＶＩＮＧｃｌａｕｓｅ宰／ＥｘｐｒＬｉｓｔ木ｐＯｒｄｅｒＢｙ，／棗ｔｈｅＯＩ己ＤＥＲＢＹｃｌａｕｓｅ木／ｉｎｔｉｓＤｉｓｔｉｎｃｔ，≯ｔｒｕｅｉｆｔｈｅＤＩＳＴＩＮＣＴｋｅｙｗｏｒｄｉｓｐｒｅｓｅｎｔ鼻｜２５嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)ｉｎｔｎＬｉｍｉｔ，ｉｍｎＯｆ．ｆｓｅｔ產(chǎn)ＬＩＭＩＴｖａｌＬｉｅ．．１ｍｅａｎｓｎｏｔｕｓｅｄ，Ｉ‘／／棗ＯＦＦＳＥＴｖａｌｕｅ．０ｍｅａｎｓｎｏｏｆｆｓｅｔ堆／）｛Ｓｅｌｅｃｔ事ｐＮｅｗ；ｐＴａｂ?＞ｚＮａｍｅ２ｚＴａｂＮａｍｅ？ＳｔｒＤｕｐ（ｚＴａｂＮａｍｅ）：Ｏ；ｐＥＬｉｓｔ＝ｐＳｅｌｅｃｔ－＞ｐＥＬｉｓｔ；ｐＴａｂ－＞ｎＣｏｌ＝ｐＥＬｉｓｔ一＞ｎＥｘｐｒ；ａｓｓｅｒｔ（ｐＴａｂ－＞ｎＣｏｌ＞０）；ｐＴａｂ一＞ａＣｏｌ＝ａＣｏｌ＝ＥＤＢＭａＵｏｃ（ｓｉｚｅｏｆ（ｐＴａｂ一＞ａＣｏｌ［０］）宰ｐＴａｂ－＞ｎＣ０１）；ｆｏｒ（ｉ＝Ｏ；ｉ＜ｐＴａｂ?＞ｎＣｏｌ；ｉ州｛Ｅｘｐｒ牛Ｐ．宰ｐＲ；ｉｆ（ｐＥＬｉｓｔ－＞ａ［ｉ】．ｚＮａｍｅ）｛ａＣｏｌ［ｉ］．ｚＮａｍｅ＝ＥＤＢＳｔｒＤｕｐ（ｐＥＬｉｓｔ－＞ａ［ｉ】．ｚＮａｍｅ）；｝ｅｌｓｅｉｆ（①＝ｐＥＬｉｓｔ－＞ａ［ｉ］．ｐＥｘｐｒ）－＞ｏｐ一－－－ＴＫ＿ＤＯＴ＆＆（ｐＲ＿叩－＞ｐＲｉｇｈｔ）！＝０＆＆ｐＲ－＞ｔｏｋｅｎ．Ｚ＆＆ｐＲ一＞ｔｏｋｅｎ．ｚ［Ｏ】）｛ｉｎｔｃｎｔ；ＳｅｔＮＳｔｒｉｎｇ（＆ａＣｏｌ［ｉ］．ｚＮａｍｅ，ｐＲ－＞ｔｏｋｅｎ．ｚ，ｐＲ－＞ｔｏｋｅｎ．ｎ，０）；ｆｏｒ（ｊ＝ｃｎｔ＝０；ｊ《；ｊ什）＜ｉｆ（ＥＤＢＳｔｒｌＣｍｐ（ａＣｏｌ［ｊ］．ｚＮａｍｅ，ａＣｏｌ［ｉ］．ｚＮａｍｅ）－一－－Ｏ）｛ｉｎｔｎ：ｃｈａｒｚＢｕｆ［３０］；ｓｐｒｉｎｔｆ（ｚＢｕｆ，”—％ｄｆＩ，＋＋ｃｎｔ）；ｎ＝ｓｔｒｌｅｎ（ｚＢｕｆ）；ＳｅｔＮＳｔｒｉｎｇ（＆ａＣｏｌ［ｉ］．ｚＮａｍｅ，ｐＲ－＞ｔｏｋｅｎ．ｚ，ｐＲ一＞ｔｏｋｅｎ．ｎ，ｚＢｕｆ，ｎ，０）；Ｊ＝－ｌ；｝｝｝ｅｌｓｅｉｆ（ｐ－＞ｓｐａｎ．ｚ＆＆Ｐ一＞ｓｐａｎ．ｚ［Ｏ］）｛ＥＤＢＳｅｔＮＳｔｒｉｎｇ（＆ｐＴａｂ一＞ａＣｏｌ［ｉ］．ｚＮａｍｅ，ｐ－＞ｓｐａｎ．ｚ，ｐ－＞ｓｐａｎ．ｎ，０）；）ｅｌｓｅ｛ｃｈａｒｚＢｕｆ［３０］；２６第三章嵌入式數(shù)據(jù)庫的分析與設(shè)計ｓｐｒｉｎｔｆ（ｚＢｕｆ，”ｃｏｌｕｎｍ％ｄ”，ｉ＋１）；ａＣｏｌ［ｉ］．ｚＮａｍｅ＞Ｄｅｑｕｏｔｅ（ａＣｏｌ［ｉ］．ｚＮａｍｅ）；｝ｐＴａｂ一＞ｉＰＫｅｙ＝－１；ｒｅｔｕｒｎｐＴａｂ；２ＳｔｒＤｕｐ（ｚＢｕｆ）；（６）刪除記錄此函數(shù)的輸入是要刪除的表名，ｗｈｅｒｅ條件可以沒有，此時指刪除表中的所有記錄。此函數(shù)的的刪除過程為：首先在字典表中檢查要刪除的表名，如果不存在，則提示錯誤退出，然后檢查ｗｈｅｒｅ條件參數(shù)，若為空，則直接清空表中的數(shù)據(jù)，若有ｗｈｅｒｅ條件從句，則先比較條件中的列名是否在表的列中出現(xiàn)，若列名不存在，則提示錯誤退出，否則進(jìn)行記錄的刪除工作，此刪除過程分為兩步，第一步是從頭到尾掃描表，若記錄滿足ｗｈｅｒｅ條件，則把滿足條件的記錄的記錄號放入到一個整數(shù)隊列中。第二步是按隊列中的記錄號刪除表中的記錄。若此表還有索引，則還要更新索引記錄，刪除記錄流程如圖３－１ｌ所示。２７嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)圖３—１１刪除記錄流程圖３．６．６索引設(shè)計本數(shù)據(jù)庫采用Ｂ＃樹索引結(jié)構(gòu)，Ｂ＃樹能適應(yīng)隨機(jī)查找和順序查找，并且能在很大程度提高數(shù)據(jù)庫的空間利用率。索引結(jié)點(diǎn)結(jié)構(gòu)主要包括５個部分，ＦｉｌｅＨｅａｄｅｒ（數(shù)據(jù)庫文件頭頁，它只存在于每一個數(shù)據(jù)庫文件的第一頁，其它的中間頁或是葉子頁都沒有這一項），ＰａｇｅＨｅａｄｅｒ（結(jié)點(diǎn)頭部），ＣｅｌｌＵｎｌｏｃａｔｅｄＰｉｏｎｔｅｒａｒｒａｙ（索引項指針數(shù)組，指向ｃｅｌｌｃｏｎｔｅｎｔａｒｅａ），ｓｐａｃｅ（指暫時還沒分配去的，或是己被系統(tǒng)回收的空間），ｃｅｌｌｃｏｎｔｅｎｔａｒｅａ（指每個ｃｅｌｌ的數(shù)據(jù)集合），如圖３－１２所示：第三章嵌入式數(shù)據(jù)庫的分析１ｊ設(shè)計圖３－１２索引節(jié)點(diǎn)結(jié)構(gòu)示意圖１．索引查找算法設(shè)計在Ｂ＃樹中，繼承了Ｂ＋樹的優(yōu)點(diǎn)，區(qū)別在于Ｂ＃樹中可能有溢出頁，也就是在查找關(guān)鍵字時，如果在葉子結(jié)點(diǎn)中如要沒有發(fā)現(xiàn)要查找的關(guān)鍵字時，還需要檢查溢出頁，如果溢出頁存在，繼續(xù)在它的溢出頁順序查找，如果查找成功，則查找結(jié)束。在Ｂ＃樹中，如果關(guān)鍵字在葉子結(jié)點(diǎn)中，則跟Ｂ＋樹查找方法一樣，這里不需要多說，如果關(guān)鍵字出現(xiàn)在溢出頁中，專為查找Ｂ＃樹的溢出頁中關(guān)鍵字設(shè)計了函數(shù)ｆｉｎｄｏｖｅｒｆｌｏｗＣｅｌｌ（），用它來查找Ｂ＃樹的溢出頁中的關(guān)鍵字。ｓｔａｔｉｃｕ８木ｆｉｎｄＯｖｅｒＣｅｌｌ（ＭｅｍＰａｇｅ木ｐＰａｇｅ，ｉｎｔｉＣｅｌｌ）｛ｉｎｔｉ；ｆｏｒ（ｉ＝ｐＰａｇｅ－＞ｎＯｖｅｒｆｌｏｗ－１；ｉ＞＝Ｏ；ｉ一、｛ｉｎｔｋ：ｓｔｒｕｃｔ—ＯｖｆｌＣｅｌｌ宰ｐＯｖｆｌ；ｐＯｖｆｌ＝＆ｐＰａｇｅ－＞ａＯｖｆｌ［ｉ］；’ｋ＝ｐＯｖｆｌ；ｉｆ（ｋ＜＝ｉＣｅｌｌ）｛ｉｆ（ｋ—ｉＣｅｌｌ）｛ｒｅｔｕｒｎｐＯｖｆｌ一＞ｐＣｅｌｌ；２９嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)＿｝ｉＣｅＵ－－；））＞２．索引插入算法設(shè)計在Ｂ＋樹索引機(jī)制中，如果發(fā)現(xiàn)葉子結(jié)點(diǎn)已滿，待插入的關(guān)鍵字一插入，就會引起結(jié)點(diǎn)的分裂。葉子結(jié)點(diǎn)一分為二，把關(guān)鍵字平均分配到兩個結(jié)點(diǎn)，中間關(guān)鍵字提升，更新父結(jié)點(diǎn)中的關(guān)鍵字，完成了一次結(jié)點(diǎn)分裂的操作。在Ｂ＃樹索引機(jī)制，當(dāng)發(fā)現(xiàn)葉子結(jié)點(diǎn)己滿，會先查找它的左右２Ｎ個兄弟個是否有未分配的空間，如果沒有，再查找它的溢出頁中是否已滿，如果未滿，則直插入到溢出頁，否則，進(jìn)行結(jié)點(diǎn)分裂。在Ｂ＃中，如果要插入一個關(guān)鍵字，首先調(diào)用函數(shù)查找樹中是否存在關(guān)鍵字，如果關(guān)鍵字存在，直接返回。當(dāng)關(guān)鍵字不存在于Ｂ＃樹中，假如葉子結(jié)點(diǎn)空間己滿，則檢查它的左右２Ｎ個兄弟結(jié)點(diǎn)是否存在未分配的空間，如果是，則通過Ｂａｌａｎｃｅｓｏｒｔ函數(shù)來騰出空間，再把關(guān)鍵字插入到合適的空間中，并保持葉子結(jié)點(diǎn)間關(guān)鍵字有序。如果左右兄弟的結(jié)點(diǎn)都己滿，則檢查它溢出頁是否存在未使用空間，如果存在，則插入溢出頁，否則調(diào)用函數(shù)ｄｅｆｒａｇｍｅｎｔＰａｇｅ來分裂結(jié)點(diǎn)，把關(guān)鍵字插入分裂后的空間，并調(diào)用函數(shù)Ｂａｌａｎｃｅ保持葉子結(jié)點(diǎn)關(guān)鍵字的有序。３．索引刪除算法設(shè)計在Ｂ＃樹中，如果結(jié)點(diǎn)發(fā)生關(guān)鍵字刪除操作，如果該關(guān)鍵字在葉子結(jié)點(diǎn)中，刪除后，判斷它的溢出頁是否存在，如果存在，則將溢出中的關(guān)鍵字移到葉子結(jié)點(diǎn)中，并保持葉子結(jié)點(diǎn)中關(guān)鍵字原有順序，如果不存在，則檢查其同父結(jié)點(diǎn)的２Ｎ個左右兄弟是否存在溢出頁，如果是，則通過“動態(tài)平衡”，騰出空位，把溢出頁中關(guān)鍵字移到葉子結(jié)點(diǎn)中，并保持葉子結(jié)點(diǎn)關(guān)鍵字原有順序，如果否，則檢查該結(jié)點(diǎn)和它的同父結(jié)點(diǎn)的２Ｎ個兄弟結(jié)點(diǎn)，能否同時容納于２Ｎ個結(jié)點(diǎn)中，如果能，則進(jìn)行合并，刪除一個結(jié)點(diǎn)，進(jìn)行“動態(tài)平衡＂，保持２Ｎ個結(jié)點(diǎn)中關(guān)鍵字原有順序，如果不能，用動態(tài)平衡算法把關(guān)鍵字平均分配到２Ｎ＋１個結(jié)點(diǎn)中，并保持原有順序。如果刪除的關(guān)鍵字在溢出頁中，則刪除過后，判斷溢出頁是否為空，如果是，則由于系統(tǒng)回收該溢出頁，否則保持溢出頁中關(guān)鍵字有序。３０第四章基于ＡＲＭ的嵌入式數(shù)據(jù)庫的實(shí)現(xiàn)第四章基于ＡＲＭ的嵌入式數(shù)據(jù)庫的實(shí)現(xiàn)４．１硬件平臺的搭建４．１．１ＡＲＭ開發(fā)平臺介紹ＡＲＭ微處理器是一種高性能、低功耗的３２位微處器，它被廣泛應(yīng)用于嵌入式系統(tǒng)中，ＡＲＭ是一家英國公司，它的文字含義是ＡｄｖａｎｃｅｄＲＩＳＣＭｉｃｒｏｐｒｏｃｅｓｓｏｒ（高級ＲＩＳＣ微處理器）。ＡＲＭ為客戶提供１６／３２位嵌入式ＲＩＳＣ微控制器方案，將其ＲＩＳＣ處理器授權(quán)給電子公司使用，在便攜式通訊，手持計算設(shè)備，消費(fèi)類和數(shù)字化多媒體方案中，ＡＲＭ正有一種成為標(biāo)準(zhǔn)的趨勢ｎ９１。４．１．２Ｓ３０２４１０開發(fā)板介紹三星（Ｓａｍｓｕｎｇ）￥３Ｃ２４１０是一款著名的移動設(shè)備處理器產(chǎn)品，最著名的應(yīng)用是在惠普的ｉＰＡＱ系列ＰＤＡ上，￥３Ｃ２４１０有兩個型號：￥３Ｃ２４１０Ｘ和￥３Ｃ２４１０Ａ，Ａ型是Ｘ型的改進(jìn)型，相對來說具有更好的性能和更低的功耗，￥３Ｃ２４１０主要面向手持式設(shè)備以及高性價比、低功耗的應(yīng)用，現(xiàn)在市面上許多高性能的ＰＤＡ、手機(jī)、數(shù)碼相機(jī)、機(jī)頂盒等均采用￥３Ｃ２４１０為處理器。４．２嵌入式Ｌｉｎｕｘ開發(fā)環(huán)境的建立４．２．１嵌入式Ｌｉｎｕｘ開發(fā)環(huán)境的基本結(jié)構(gòu)由于嵌入式設(shè)備沒有足夠的內(nèi)存以及存儲資源來完成其編譯過程，所以就在主機(jī)上完成針對目標(biāo)的代碼編譯生成，這個過程稱為交叉編譯。這也是目前大多數(shù)嵌入式設(shè)備開發(fā)所使用的編譯方式。為了提高嵌入式Ｌｉｎｕｘ的開放效率，一個完善的嵌入式Ｌｉｎｕｘ開發(fā)環(huán)境是必不可少的。嵌入式Ｌｉｎｕｘ開發(fā)環(huán)境一般由如下幾部分構(gòu)成：Ｌｉｎｕｘ服務(wù)器（宿主機(jī)）、工作站、嵌入式目標(biāo)系統(tǒng)和將它們連接在一起的網(wǎng)絡(luò)環(huán)境，其具體結(jié)構(gòu)如圖圖４－１嵌入式開發(fā)環(huán)境基本結(jié)構(gòu)圖中所示的嵌入式Ｌｉｎｕｘ開發(fā)環(huán)境中，Ｌｉｎｕｘ服務(wù)器作為嵌入式Ｌｉｎｕｘ內(nèi)核編譯、應(yīng)用程序編譯的公共平臺，由單獨(dú)的一臺ＰＣ機(jī)充當(dāng)，安裝常用的桌面標(biāo)準(zhǔn)Ｌｉｎｕｘ操３ｌ嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)作系統(tǒng)，如ＲｅｄｈａｔＬｉｎｕｘ等。工作站即為普通的局域網(wǎng)計算機(jī)，可以是一臺或多臺，以支持小組項目開發(fā)。工作站一般安裝常用的ｗｉｎｄｏｗｓ操作系統(tǒng)，仍然可以完成各種日常工作。當(dāng)需要使用Ｌｉｎｕｘ服務(wù)器資源時，就從工作站遠(yuǎn)程登錄到Ｌｉｎｕｘ服務(wù)器，以完成各項需要的操作。工作站作為開發(fā)人員的操作終端，可能需要經(jīng)常登錄Ｌｉｎｕｘ服務(wù)器和工作站之間進(jìn)行文件的傳輸，因此，一般需要在工作站上安裝ＦＴ，客戶端程序（如Ｃｕｔｅｆｔｐ等）和Ｔｅｌｎｅｔ客戶端程序（如ＳｅｃｕｒｅＣＲＴ等）。當(dāng)Ｌｉｎｕｘ服務(wù)器的ＦＴＰ服務(wù)和Ｔｅｌｎｅｔ服務(wù)運(yùn)行時，開發(fā)人員就可以方便地在工作站和Ｌｉｎｕｘ服務(wù)器之間進(jìn)行文件傳輸，并可以通過Ｔｅｌｎｅｔ方式登錄到Ｌｉｎｕｘ服務(wù)器，并對其進(jìn)行相關(guān)操作。４．２．２在Ｌｉｎｕｘ服務(wù)器上安裝交叉編譯工具１．獲取交叉編譯工具?開發(fā)基于Ｌｉｎｕｘ的應(yīng)用程序，一般的步驟是先編寫程序源代碼，然后編譯調(diào)試，最終生成可執(zhí)行程序。交叉編譯工具一般由專門的機(jī)構(gòu)負(fù)責(zé)維護(hù)，可以從他們的網(wǎng)站上免費(fèi)取得㈨。２．安裝交叉編譯工具下載的交叉編譯工具以壓縮的方式存在，需要將其安裝到Ｌｉｎｕｘ服務(wù)器上。這里把交叉編譯工具安裝在Ｌｉｎｕｘ服務(wù)器的／ｕｓｒ／ｌｏｃａｌ／目錄下，執(zhí)行如下操作，建立／ｕｓｒ／ｌｏｃａｌ／ａｒｍ目錄，并將下載的交叉編譯工具復(fù)制到該目錄下乜引：＃ｃｄ／ｕｓｒ／ｌｏｃａｌ＃ｍｋｄｉｒａｒｍ（進(jìn)入目錄／ｕｓｒ／ｌｏｃａｌ）（建立子文件夾）（拷貝文件）＃ｃｐ／ｈｏｍｅ／ｗｏｒｋ／ｃｒｏｓｓ一２．９５３．ｔａｒ．ｂｚ２輸入如下命令解壓安裝編譯工具：＃ｔａｒｚｘｖｆｃｒｏｓｓ一２．９５．３．ｔａｒ．ｂｚ２（解壓縮文件）當(dāng)以上命令執(zhí)行完畢以后，會生成／ｕｓｒ／１０ｃａｌ／ａｒｍ／２．９５．３子目錄，表明交叉編譯器已經(jīng)成功安裝到了／ｕｓｒ／ｌｏｃａｌ／ａ瑚下。安裝后會在該目錄下生成如下的文件和目錄：ａｒｍ－Ｌｉｎｕｘｂｉｎｉｎｃｌｕｄｅｉｎｆｏｌｉｂｍａｎｓｈａｒｅｔｅｓｔ—ｉｆ—ｗｒｉｔｅ其中，ｂｉｎ目錄下是交叉編譯器和一些工具，如編譯器ａｍｔ—Ｌｉｎｕｘ—ｇｃｃ是Ｃ交叉編譯器，ａｒｍ－Ｌｉｎｕｘ—ｇ＋＋是Ｃ＋＋編譯器，ａｒｍ－Ｌｉｎｕｘ—ａｓ是匯編器，ａｒｍ—Ｌｉｎｕｘ—Ｉｄ是鏈接器。Ｌｉｂ目錄下存放的是庫文件，包括ｇｃｃ庫、１ｉｂ－ｇｃｃ庫、ｌｉｂ—ｇ＋＋庫等。／ｉｎｃｌｕｄｅ目錄存放編譯器的頭文件，包含了標(biāo)準(zhǔn)Ｃ的頭文件、Ｌｉｎｕｘ的頭文件、３２第四章基于ＡＲＭ的嵌入式數(shù)據(jù)庫的實(shí)現(xiàn)特定處理器相關(guān)的Ｌｉｎｕｘ頭文件等。在以上工具中，ａｒｍ－Ｌｉｎｕｘ－ｇｃｃ作為基于ＡＲＭ架構(gòu)的Ｃ編譯器，在系統(tǒng)開發(fā)過程中是最為常用的㈨。４．２．３嵌入式ＬＩｎｕｘ內(nèi)核的配置與編譯Ｌｉｎｕｘ最大的特點(diǎn)是內(nèi)核具有非常良好的結(jié)構(gòu)，可由用戶根據(jù)特定的系統(tǒng)需求，對內(nèi)核進(jìn)行配置或裁剪，而這一特點(diǎn)恰恰滿足了嵌入式應(yīng)用的差異性需求心利。１．獲取Ｌｉｎｕｘ內(nèi)核源代碼Ｌｉｎｕｘ內(nèi)核由專門的機(jī)構(gòu)維護(hù)，可以從Ｌｉｎｕｘ內(nèi)核的官方發(fā)布網(wǎng)站：：ｈｔｔｐ：／／嗣ｗｋｅｍｅｌ．ｏｒｇ上獲取功能完善的最新內(nèi)核。２．Ｌｉｎｕｘ內(nèi)核配與編譯本系統(tǒng)的Ｌｉｎｕｘ內(nèi)核編譯步驟如下：１）整理出系統(tǒng)需要支持的硬件、文件系統(tǒng)類型以及網(wǎng)絡(luò)協(xié)議等內(nèi)容，以便配置內(nèi)核時選擇所需的軟件支持。２）下載并解壓Ｌｉｎｕｘ內(nèi)核，因為安裝系統(tǒng)時所安裝的源代碼默認(rèn)情況下支持很多設(shè)備，這樣給內(nèi)核裁減降低了難度。一般都將Ｌｉｎｕｘ內(nèi)核源代碼放在／ｕｓｒ／ｓｒｃ下。３）清除從前編譯內(nèi)核時殘留的文件和不必要的關(guān)聯(lián)：ｃｄ／ｕｓｒ／ｓｒｃ幾ｉｎｕｘ（進(jìn)入文件夾）ｍａｋｅｍｒｐｒｏｐｅｒ（清除不必要的關(guān)聯(lián)）確保源代碼目錄下沒有不正確的文件和文件依賴關(guān)系，執(zhí)行該命令后，內(nèi)核選項會回到默認(rèn)的狀態(tài)下。本系統(tǒng)是下載的內(nèi)核源碼，而且是第一次編譯，所以就不必執(zhí)行這一步操作。４）配置內(nèi)核，修改相關(guān)參數(shù)一＋。’本系統(tǒng)需要選擇的模塊有：Ｓｕｐｐｏｒｔｆｏｒｐａｇｉｎｇｏｆａｎｏｎｙｍｏｕｓｍｅｍｏｒｙ（ｓｗａｐ）／／支持虛擬內(nèi)存Ｅｎａｂｌｅｌｏａｄａｂｌｅｍｏｄｕｌｅｓｕｐｐｏｒｔ（ＣＯＮＦＩＧＭＯＤＵＬＥＳ）／／動態(tài)裝載模塊功能Ｎｅｔｗｏｒｋｉｎｇｓｕｐｐｏｒｔ（ＣＯＮＦＩＧＮＥＴ）／／網(wǎng)絡(luò)支持ＴＣＰ／ＩＰｎｅｔｗｏｒｋｉｎｇ／／ＴＣＰ／ＩＰ協(xié)議等系統(tǒng)必須的功能模塊。５）運(yùn)行ｍａｋｅｃｌｅａｎ，清理一些不必要的文件，如果在上次編譯的基礎(chǔ)上，刪去了一些選項就必須執(zhí)行這一步操作。６）編譯內(nèi)核３３嵌入式數(shù)據(jù)庫的設(shè)計與實(shí)現(xiàn)編譯內(nèi)核的命令是：ｍａｋｅ４．２．４根文件系統(tǒng)的制作ｚＩｍａｇｅ對于嵌入式Ｌｉｎｕｘ來說，最簡單、最常用的根文件系統(tǒng)是ＲＡＭＤＩＳＫ。ＲＡＭＤＩＳＫ就是指使用系統(tǒng)的一部分內(nèi)存空間來模擬一個用戶熟悉的磁盤分區(qū)，用戶在ＲＡＭＤＩＳＫ上進(jìn)行的所有操作都與傳統(tǒng)的磁盤文件操作一樣。因此，對于無盤系統(tǒng)或嵌入式系統(tǒng)，選擇ＲＡＭＤＩＳＫ作為根文件系統(tǒng)是很適合的。在實(shí)際的應(yīng)用過程中，通常采用的方式是從開發(fā)系統(tǒng)提供商獲得一個已經(jīng)做好的ＲＡＭＤＩＳＫ然后由用戶根據(jù)自身系統(tǒng)的實(shí)際需求，對己有的ＲＡＭＤＩＳＫ進(jìn)行增減，最終形成一個適合自身應(yīng)用的ＲＡＭＤＩＳＫ。１．ＲＡＭＤＩＫ的制作１）首先為根文件系統(tǒng)創(chuàng)建空的文件鏡像：ｍｋｄｉｒ／ｒａｎｔｉｎｉｔｒｄｄｄ／／創(chuàng)建目錄?－ｉｆ＝／ｄｅｖ／ｚｅｒｏｏｆ＝ｉｎｉｔｒｄ．ｉｍｇｂｓ＝ｌｋｃｏｕｎｔ＝８１９２／／確定文件系統(tǒng)大?。恚耄妫螅澹簦惨唬疲恚铮酰睿椋睿椋簦颍洌椋恚纾ぃ兆魑募到y(tǒng)ｉｔｒｄ．ｉｍｇ／ｍｎｔ／ｉｎｉｔｒｄ／／掛載ｔ一０ｌｏｏｐｉｎ上面命令創(chuàng)建了一個８１９２ＫＢ的文件系統(tǒng)鏡像，并通過ｄｅｖ／ｚｅｒｏ進(jìn)行初始化。２）創(chuàng)建目錄，上面的命令創(chuàng)建了一個ＲＡＭＤＩＳＫ，要用必要的文件填充它：ｍｋｄｉｒｄｅｖｐｒｏｃｅｔｃｓｂｉｎｂｉｎｌｉｂｍｎｔｕｓｒ。２．利用已有的ＲＡＭＤＩＳＫ本系統(tǒng)的ＲＡＭＤＩＳＫ是這樣實(shí)現(xiàn)：解壓系統(tǒng)提供商的ＲＡＭＤＩＳＫ：ｇｚｉｐ—ｄｒａｍｄｉｓｋ．ｇｚ，將文件掛載到一個臨時目錄：＃ｍｋｄｉｒｒａｍ—ｄｉｓｋｒａｍ＿ｄｉｓｋ＃ｍｏｕｎｔ‘。０ｌｏｏｐｒａｍｄｉｓｋ＃１Ｓ根據(jù)本系統(tǒng)的需求，對相關(guān)文件進(jìn)行增減操作，即可以往目錄復(fù)制或刪除一些文件。操作好后對新的ＲＡＭＤＩＳＫ文件進(jìn)行壓縮：＃ｕｍｏｕｎｔ／ｒａｍｄｉ＃ｇｚｉｐｒａｍｄｉｓｋｓｋ／／卸載／／壓縮文件系統(tǒng)這樣生成一個新的ＲＡＭＤＩＳＫ。有了嵌入式Ｌｉｎｕｘ和根文件系統(tǒng)，一個完整的嵌入式Ｌｉｎｕｘ系統(tǒng)就編譯完成了。３４第四章基于刪的嵌入式數(shù)據(jù)庫的實(shí)現(xiàn)４．２．５網(wǎng)絡(luò)文件系統(tǒng)（ＮＦＳ）及配置首先在Ｌｉｎｕｘ服務(wù)器上設(shè)置：以Ｒｏｏｔ身份登錄Ｌｉｎｕｘ服務(wù)器，編輯共享目錄配置文件ｅｘｐｏｒｔ，指定共享目錄及權(quán)限等。執(zhí)行如下的命令編輯文件：ｅｔｃ／ｅｘｐｏｒｔｓ＃ｖｉ／ｅｔｃ／ｅｘｐｏｒｔｓ（編輯ｅｘｐｏｒｔｓ的內(nèi)容）在該文件中添加如下內(nèi)容：／ｈｏｍｅ／ｗｏｒｋ１９２．１６８．１水添加的內(nèi)容表示ＩＰ在１９２．１６８．１．木的計算機(jī)以讀寫的權(quán)限來訪問／ｈｏｍｅ／ｗｏｒｋ目錄。／ｈｏｍｅ／ｗｏｒｋ也稱為服務(wù)器輸出共享目錄。接著執(zhí)行如下命令，啟動端口映射：＃／ｅｔｃ／ｒｃ．ｄ／ｉｎｉｔ．ｄ／ｐｒｏｔｍａｐｓｔａｒｔ最后執(zhí)行如下命令啟動ＮＦＳ服務(wù)，此時ＮＦＳ會激活守護(hù)進(jìn)程，然后就開始監(jiān)聽客戶端的請求：＃／ｅｔｃ／ｒｃ．ｄ／ｉｎｉｔ．ｄ／ｎｆｓｓｔａｒｔ在ＮＦＳ服務(wù)啟動后還要檢查Ｌｉｎｕｘ服務(wù)器的防火墻等設(shè)置，確保沒有屏蔽掉ＮＦＳ使用的端口和允許通信的主機(jī)。首先在Ｌｉｎｕｘ服務(wù)器上進(jìn)行ＮＦＳ服務(wù)器的回環(huán)測試，驗證共享目錄是否能夠被訪問。在嵌入式系統(tǒng)上運(yùn)行如下命令。＃ｍｏｕｎｔ－ｔｎｆｓ１９２．１６８．１．１：／ｈｏｍｅ／ｗｏｒｋ／ｍｎｔ命令將Ｌｉｎｕｘ服務(wù)器的ＮＦＳ輸出共享目錄掛載到／ｍａｔ目錄下，因此，如果ＮＦＳ工作正常，應(yīng)該能夠在／ｍｎｔ目錄中看至Ｕ／ｈｏｍｅ／ｗｏｒｋ共享目錄中的內(nèi)容。在Ｌｉｎｕｘ服務(wù)器設(shè)置好以后，接下來需要進(jìn)行客戶端的設(shè)置。首先需要運(yùn)行在嵌入式目標(biāo)系統(tǒng)的Ｌｉｎｕｘ內(nèi)核支持ＮＦＳ客戶端，在嵌入式目標(biāo)系統(tǒng)的Ｌｉｎｕｘｓｈｅｌｌ下，執(zhí)行如下命令進(jìn)行Ｎ