紅黑樹的性能分析及其在實(shí)時(shí)數(shù)據(jù)庫中的應(yīng)用

馮 濤 楊耀輝

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

0 引言

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

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

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

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

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

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

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

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

(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)。

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

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

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

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

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

3 結(jié)束語

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

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

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

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