紅黑樹的性能分析及其在實時數據庫中的應用

馮 濤 楊耀輝

（西安理工大學 陜西 西安 710082）

0 引言

對于任何一個數據庫系統,其數據組織結構是基礎。實時內存數據庫的設計應該打破傳統磁盤數據庫的設計觀念，考慮內存直接快速存取和數據實時性的特點，以CPU和內存空間的高效利用為目標來重新設計開發各種策略與算法、技術、方法及機制。

本文論述實時數據庫的組織結構，針對實時內存數據庫系統的實際需求，提出了一種基于紅黑樹結構的數據組織方式。數據的組織實現了底層數據的抽象，為上層的數據庫的管理和查詢提供了方便。此處采用紅黑樹結構組織數據。

1 常用實時數據庫的樹形組織結構

實時數據庫的總體設計目標是使內存和CPU的利用率盡可能高，而實時數據庫的數據組織是結構實現該目標的基礎，必須考慮內存的直接存取這一特征，這里介紹幾種適合于實時數據庫的樹形組織方法。

二叉搜索樹(也作二叉排序樹)是一種很好的選擇:構造簡單，動態性能好。但在極端壞的情況下，二叉搜索樹會“蛻化”成了線性鏈表。

AVL樹常作為實時數據庫的數據結構，他是一個二叉樹，我們在結點的數據結構中加入一個記錄左右子樹高度差的字段。如果高度差的絕對值超過了2，可以通過調整，使樹的高度減小。平衡二叉樹保證較高的查找效率，但代價卻是靠構造樹的時候不斷調整樹的形狀。

B_樹是比較合適用于磁盤的數據結構，由于他是一個寬而淺的樹，查找一個數據需要訪問很少的節點。然而，B_樹的結點允許容納多個關鍵字，這樣會使結點的定義不統一，并且在結點中的查找效率不高。

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

(1)每個結點或是紅色的，或是黑色的(增加一位表示顏色的存儲位)；

(2)每個葉結點(空指針NIL)是黑色的；

(3)如果一個結點是紅色的，則它的兒子應是黑色的；

(4)從任一給定結點到其子孫葉結點的每條簡單路徑上都具有相同個數的黑結點。

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

2 紅黑樹模型的實現

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

紅黑樹中樹的結點是由關鍵字key、指向記錄的指針、結點顏色、指向父節點的指針和指向左右節點的指針構成。紅黑樹的數據結構部分代碼如下：

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

3 結束語

針對實時數據庫系統的特點以及目前所管理數據的需求，提出了一種數據組織以及查詢的方法，采用基于紅黑樹結構組織方法，實現實時內存數據庫的構建。該方法具有較高的空間利用率，并消除了數據操作中通常存在的內存空間的不斷申請和釋放操作，減少了不必要的空間調整和數據更新的計算。能夠大大縮短檢索數據庫需要的時間，這對于保證實時內存數據庫的定時性有著重要的意義。

［1］蔡子經,施伯樂.數據結構教程[M].上海:復旦大學出版社,1994.

［2］劉云生.實時數據庫系統[J].計算機科學,1994,3:24-46.

［3］劉云生,等.ARTS-I:一個主動實時內存數據庫系統[J].華中理工大學學報,1996,24(3).