一種新的嵌入式內(nèi)存數(shù)據(jù)庫的設(shè)計

　隨著硬件的發(fā)展，內(nèi)存的容量在不斷擴大，人們長期思考的將全部或大部分?jǐn)?shù)據(jù)存放在 內(nèi)存中運行成為可能。同時，嵌入式設(shè)備在日常生活中得到廣泛應(yīng)用，如何對其內(nèi)部日益繁 多的數(shù)據(jù)進行管理顯得很關(guān)鍵。當(dāng)前嵌入式內(nèi)存數(shù)據(jù)庫產(chǎn)品很多，大多數(shù)產(chǎn)品由于各方面的 限制，在性能和市場前景方面表現(xiàn)欠佳。在嵌入式內(nèi)存數(shù)據(jù)庫研究領(lǐng)域，新的存儲與索引方 法被不斷提出，同時面向?qū)ο蟮某绦蛟O(shè)計語言java作為當(dāng)前主流開發(fā)語言，在多線程和死鎖 處理方面有其獨特之處，為提出新的嵌入式內(nèi)存數(shù)據(jù)庫的設(shè)計方法，及基于事務(wù)模型的恢復(fù) 方法提供了可能。
　　1嵌入式內(nèi)存數(shù)據(jù)庫概述
　　嵌入式內(nèi)存數(shù)據(jù)庫的設(shè)計一般采取兩種思路：一種是對傳統(tǒng)的大型數(shù)據(jù)庫進行裁剪和改 進，很多處理問題的方法仍采用傳統(tǒng)數(shù)據(jù)庫的方法，某些方法在嵌入式內(nèi)存數(shù)據(jù)庫不適用則 做些稍微改進，這種思路沒有逃離傳統(tǒng)數(shù)據(jù)庫設(shè)計思想的束縛。另一種則是根據(jù)嵌入式內(nèi)存 數(shù)據(jù)庫自身的特點，提出新的體系結(jié)構(gòu)，存儲結(jié)構(gòu)和恢復(fù)機制，以滿足嵌入式內(nèi)存數(shù)據(jù)庫的 要求。目前，第二種方法被普遍采用和推崇，本文新的設(shè)計方法就采用后者。
　　
　　1.2嵌入式內(nèi)存數(shù)據(jù)庫的體系結(jié)構(gòu)
　　在新的體系結(jié)構(gòu)中，我們采用關(guān)系數(shù)據(jù)模型，最上層提供外部查詢接口，支持多種常用 語言如C，java等語言連接數(shù)據(jù)庫。第二層是對SQL語句進行解析的查詢命令分解與優(yōu)化層， 這一層下面是兩個重要的模塊：數(shù)據(jù)組織與管理和事務(wù)管理器。其中，數(shù)據(jù)組織與管理模塊 完成常用的索引和數(shù)據(jù)組織工作，事務(wù)管理器具有創(chuàng)建事務(wù)，調(diào)度事務(wù)，回收事務(wù)的功能。 內(nèi)存工作區(qū)是該體系結(jié)構(gòu)最重要的模塊，全部數(shù)據(jù)操作及日志處理在這里進行，它在事務(wù)處 理時為每一個事務(wù)分配一個內(nèi)存工作區(qū)，其中存放數(shù)據(jù)和日志。日志管理器管理內(nèi)存工作區(qū) 中的日志，而恢復(fù)管理器則在系統(tǒng)出現(xiàn)故障時起作用。該數(shù)據(jù)庫大部分操作在內(nèi)存工作區(qū)中 運行，只有當(dāng)發(fā)生檢查點操作和數(shù)據(jù)庫備份，及系統(tǒng)恢復(fù)時才與外面的磁盤打交道，因此該 數(shù)據(jù)庫是典型的嵌入式內(nèi)存數(shù)據(jù)庫。上述體系結(jié)構(gòu)圖如圖1所示：
　　
　　2．?dāng)?shù)據(jù)的存儲與索引
　　嵌入式內(nèi)存數(shù)據(jù)庫通常在內(nèi)存受限的環(huán)境中進行，CPU能直接操縱內(nèi)存中的數(shù)據(jù)，且數(shù) 據(jù)經(jīng)常由于各種故障而丟失。因此合理的有效利用內(nèi)存資源，減少內(nèi)存開銷和CPU指令數(shù)， 使內(nèi)存空間得到高效利用很關(guān)鍵，為此我們引用了一種新的存儲與索引方法——T樹。
　　T樹是將AVL樹和B樹結(jié)合在一起而得出的一種新的數(shù)據(jù)結(jié)構(gòu)，T樹也是一種二叉樹，只不 過每個結(jié)點（稱為T結(jié)點）都包含多個元素。每個T結(jié)點都包含一系列從小到大排序后的元素和 三個指針，指針分別指向父結(jié)點和左右結(jié)點。某一T結(jié)點A的左結(jié)點中必會包含比A結(jié)點中最 小元素小的最大元素，而A結(jié)點的右結(jié)點中必會包含比A結(jié)點中最大元素大的最小元素。因為 是二叉樹，所以T樹具有AVL樹固有的二分查找特性，又因為每個結(jié)點包含多個元素，其又包 含了B樹良好的更新和存儲特性的優(yōu)點。對T樹來說，因插入和刪除數(shù)據(jù)所造成的數(shù)據(jù)移動通 ?？梢跃窒拊谝粋€結(jié)點內(nèi)進行，和AVL樹一樣，T樹也是通過旋轉(zhuǎn)來使樹達到平衡的， 但其所 需要的旋轉(zhuǎn)操作的次數(shù)遠少于AVL樹［ 2 ］。