冯 涛 杨耀辉

（西安理工大学 陕西 西安 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).