馮 濤 楊耀輝

（西安理工大學(xué) 陜西 西安 710082）

0 引言

對(duì)于任何一個(gè)數(shù)據(jù)庫(kù)系統(tǒng),其數(shù)據(jù)組織結(jié)構(gòu)是基礎(chǔ)。實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)的設(shè)計(jì)應(yīng)該打破傳統(tǒng)磁盤(pán)數(shù)據(jù)庫(kù)的設(shè)計(jì)觀念，考慮內(nèi)存直接快速存取和數(shù)據(jù)實(shí)時(shí)性的特點(diǎn)，以CPU和內(nèi)存空間的高效利用為目標(biāo)來(lái)重新設(shè)計(jì)開(kāi)發(fā)各種策略與算法、技術(shù)、方法及機(jī)制。

本文論述實(shí)時(shí)數(shù)據(jù)庫(kù)的組織結(jié)構(gòu)，針對(duì)實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)的實(shí)際需求，提出了一種基于紅黑樹(shù)結(jié)構(gòu)的數(shù)據(jù)組織方式。數(shù)據(jù)的組織實(shí)現(xiàn)了底層數(shù)據(jù)的抽象，為上層的數(shù)據(jù)庫(kù)的管理和查詢(xún)提供了方便。此處采用紅黑樹(shù)結(jié)構(gòu)組織數(shù)據(jù)。

1 常用實(shí)時(shí)數(shù)據(jù)庫(kù)的樹(shù)形組織結(jié)構(gòu)

實(shí)時(shí)數(shù)據(jù)庫(kù)的總體設(shè)計(jì)目標(biāo)是使內(nèi)存和CPU的利用率盡可能高，而實(shí)時(shí)數(shù)據(jù)庫(kù)的數(shù)據(jù)組織是結(jié)構(gòu)實(shí)現(xiàn)該目標(biāo)的基礎(chǔ)，必須考慮內(nèi)存的直接存取這一特征，這里介紹幾種適合于實(shí)時(shí)數(shù)據(jù)庫(kù)的樹(shù)形組織方法。

二叉搜索樹(shù)(也作二叉排序樹(shù))是一種很好的選擇:構(gòu)造簡(jiǎn)單，動(dòng)態(tài)性能好。但在極端壞的情況下，二叉搜索樹(shù)會(huì)“蛻化”成了線性鏈表。

AVL樹(shù)常作為實(shí)時(shí)數(shù)據(jù)庫(kù)的數(shù)據(jù)結(jié)構(gòu)，他是一個(gè)二叉樹(shù)，我們?cè)诮Y(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中加入一個(gè)記錄左右子樹(shù)高度差的字段。如果高度差的絕對(duì)值超過(guò)了2，可以通過(guò)調(diào)整，使樹(shù)的高度減小。平衡二叉樹(shù)保證較高的查找效率，但代價(jià)卻是靠構(gòu)造樹(shù)的時(shí)候不斷調(diào)整樹(shù)的形狀。

B_樹(shù)是比較合適用于磁盤(pán)的數(shù)據(jù)結(jié)構(gòu)，由于他是一個(gè)寬而淺的樹(shù)，查找一個(gè)數(shù)據(jù)需要訪問(wèn)很少的節(jié)點(diǎn)。然而，B_樹(shù)的結(jié)點(diǎn)允許容納多個(gè)關(guān)鍵字，這樣會(huì)使結(jié)點(diǎn)的定義不統(tǒng)一，并且在結(jié)點(diǎn)中的查找效率不高。

紅黑樹(shù)是一種自平衡二叉搜索樹(shù)一棵二叉查找樹(shù)如果滿(mǎn)足下列性質(zhì)，則稱(chēng)為紅黑樹(shù)：

(1)每個(gè)結(jié)點(diǎn)或是紅色的，或是黑色的(增加一位表示顏色的存儲(chǔ)位)；

(2)每個(gè)葉結(jié)點(diǎn)(空指針NIL)是黑色的；

(3)如果一個(gè)結(jié)點(diǎn)是紅色的，則它的兒子應(yīng)是黑色的；

(4)從任一給定結(jié)點(diǎn)到其子孫葉結(jié)點(diǎn)的每條簡(jiǎn)單路徑上都具有相同個(gè)數(shù)的黑結(jié)點(diǎn)。

紅黑樹(shù)引入了“顏色”的概念，目的在于使得紅黑樹(shù)的平衡條件得以簡(jiǎn)化。紅黑樹(shù)只要求黑色結(jié)點(diǎn)平衡。紅黑樹(shù)理論中以黑色高度來(lái)“代替”AVL樹(shù)理論中的平衡因子，實(shí)際上是弱化了平衡因子的作用。這樣帶來(lái)的好處就是可以減少樹(shù)形的調(diào)整，紅黑樹(shù)在動(dòng)態(tài)存儲(chǔ)效率上優(yōu)于平衡二叉樹(shù)，但查找效率稍劣于平衡二叉樹(shù)，在查找效率上優(yōu)于B樹(shù)在查找動(dòng)態(tài)存儲(chǔ)效率上劣于B樹(shù)，但存儲(chǔ)結(jié)構(gòu)簡(jiǎn)單。查找和數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)之間相互矛盾，不存在最完美的解決萬(wàn)案，紅黑樹(shù)平均性能較好。

2 紅黑樹(shù)模型的實(shí)現(xiàn)

整個(gè)數(shù)據(jù)庫(kù)系統(tǒng)所管理數(shù)據(jù)的邏輯組織單位是若干獨(dú)立或有一定關(guān)系的數(shù)據(jù)庫(kù)，每個(gè)數(shù)據(jù)庫(kù)有若干記錄組成，這些記錄全都被表示成（key,value）的形式。以紅黑樹(shù)紅黑樹(shù)結(jié)構(gòu)組織數(shù)據(jù)。如果把一組相關(guān)的（key,value）對(duì)也看作一個(gè)表的話，那么每一個(gè)數(shù)據(jù)庫(kù)只允許存放一個(gè)表，這一點(diǎn)不同于一般的關(guān)系數(shù)據(jù)庫(kù)，相當(dāng)于一般關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中的表；而“key/data”對(duì)相當(dāng)于關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中的行；不提供關(guān)系數(shù)據(jù)庫(kù)中列直接訪問(wèn)的功能，而是在“key/data”對(duì)中的data項(xiàng)中通過(guò)實(shí)際應(yīng)用來(lái)封裝字段(列)。數(shù)據(jù)庫(kù)提供函數(shù)來(lái)進(jìn)行數(shù)據(jù)庫(kù)的訪問(wèn)和管理并不復(fù)雜，在大多數(shù)場(chǎng)合下只需按照統(tǒng)一的接口標(biāo)準(zhǔn)進(jìn)行調(diào)用就可以完成基本操作。

紅黑樹(shù)中樹(shù)的結(jié)點(diǎn)是由關(guān)鍵字key、指向記錄的指針、結(jié)點(diǎn)顏色、指向父節(jié)點(diǎn)的指針和指向左右節(jié)點(diǎn)的指針構(gòu)成。紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)部分代碼如下：

在數(shù)據(jù)庫(kù)系統(tǒng)中除了數(shù)據(jù)的組織，數(shù)據(jù)庫(kù)的查詢(xún)也必不可少，數(shù)據(jù)的組織制約著數(shù)據(jù)的查詢(xún)，而查詢(xún)的方式?jīng)Q定著整個(gè)數(shù)據(jù)庫(kù)的效率。該實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)中可含有多個(gè)數(shù)據(jù)庫(kù)，這些數(shù)據(jù)庫(kù)通過(guò)數(shù)組的方式組織。每個(gè)數(shù)據(jù)庫(kù)中用紅黑樹(shù)樹(shù)組織起來(lái)，并提供樹(shù)中常用的插入、刪除，遍歷、查找等操作。在插入和刪除時(shí)會(huì)調(diào)整二叉樹(shù)。整個(gè)數(shù)據(jù)庫(kù)系統(tǒng)不提供SQL查詢(xún)層，而是使用接口函數(shù)來(lái)操作，避免了對(duì)SQL語(yǔ)句的分析和優(yōu)化所帶來(lái)的系統(tǒng)資源消耗。用戶(hù)需要通過(guò)接口函數(shù)查詢(xún)數(shù)據(jù)：查詢(xún)數(shù)據(jù)可以調(diào)用Search函數(shù)來(lái)完成。

3 結(jié)束語(yǔ)

針對(duì)實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)以及目前所管理數(shù)據(jù)的需求，提出了一種數(shù)據(jù)組織以及查詢(xún)的方法，采用基于紅黑樹(shù)結(jié)構(gòu)組織方法，實(shí)現(xiàn)實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)的構(gòu)建。該方法具有較高的空間利用率，并消除了數(shù)據(jù)操作中通常存在的內(nèi)存空間的不斷申請(qǐng)和釋放操作，減少了不必要的空間調(diào)整和數(shù)據(jù)更新的計(jì)算。能夠大大縮短檢索數(shù)據(jù)庫(kù)需要的時(shí)間，這對(duì)于保證實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)的定時(shí)性有著重要的意義。

［1］蔡子經(jīng),施伯樂(lè).數(shù)據(jù)結(jié)構(gòu)教程[M].上海:復(fù)旦大學(xué)出版社,1994.

［2］劉云生.實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)[J].計(jì)算機(jī)科學(xué),1994,3:24-46.

［3］劉云生,等.ARTS-I:一個(gè)主動(dòng)實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)[J].華中理工大學(xué)學(xué)報(bào),1996,24(3).