ZXSS10A200内存数据库的快速索引设计优化

（一）ZXSS10 A200内存数据库系统

ZXSS10 A200使用的数据库是由中兴通讯开发的，是一种内存数据库，特点也类似于内存数据库。内存数据库是数据库的一种，我们要在技术上对它的发展进行了解，然后学习并掌握它的特点，如此才能对ZXSS10 A200内存数据库的优缺点进行概括。

1.内存数据库的特点

内存数据库系统（MMDB）是管理整个数据库或对数据库的某个部分进行管理的系统。在该系统中，数据是可以直接被访问的，而不需要通过磁盘进行。内存数据库的这种特点提升了其在事务处理上的能力。

如果磁盘数据库在内存缓冲区上是足够大的，那么对于整个数据库而言，其都被放置在缓冲区上，磁盘数据库在性能上能达到与MMDBMS一样高效吗？虽然磁盘数据库在进行UPDATE操作时要保证数据与磁盘同步，但它与SELECT操作在效率上是相近的。因为磁盘数据库在进行查询时，算法比较复杂，为了优化磁盘访问的效率，必须提升磁盘系统的性能。内存数据库之所以有着比较高的性能，主要是因为它有着特别的数据库技术，同时数据库系统在架构上也与众不同。其具体如下：

（1）数据访问的成本。

在价格上，磁盘比存储器低，而存储器比CPU和CACHE更低。也就是说，在速度越快的同时，其价格也越高。从另一个角度来看，在对磁盘进行访问时，其处理时间是毫秒级的，而内存则是几十纳秒级的。如果想要得到较高的性能，数据库在内存中是不够存储的，需要优化内存的结构技术，同时还需要涉及高速缓存技术、数据管理技术和基于内存的查询优化技术等。

（2）内存和磁盘的地址映射。

在进行DBMS管理时，如果其中的数据是在磁盘中存储的，那么对记录的访问是通过RID（Record Identifier）来完成的。因此，要想对一个记录进行访问，其地址映射要向着RID进行转化，它能转化为内存的物理地址。物理地址与数据库的地址在映射的时间上是很短的，但是不能忽略其对高速数据的处理。内存DBMS是通过内存指针在数据库中进行访问的，但是由于地址映射时间的缺失，影响了数据库性能的提升。同样，在磁盘中进行数据库的备份或者恢复日志内容时，地址映射时间也是不可或缺的。由于地址映射技术在效率上有所差别，并且映射次数也有不同，内存数据库在性能上也是不同的。

（3）内存优化的索引结构。

磁盘数据库系统在进行索引时常用的技术是B-树索引。B-树结构的功能主要是满足数据文件在索引查找上的需要，以减少对I/O数量的查找。通过控制B-树结点内部的索引值，可以实现这一目标。结点包含的索引条目比较多，每增多一次磁盘的I/O，都可以访问其索引条目。T-树索引技术的目的是实现内存访问的优化。T-树针对一个结点而言，其索引条目有多个，是一种平衡二叉树。在索引项上，无论是基于算法还是基于大小，T-树比B-树更加精简。在搜索算法上，T-树与其值所在的地方是不加区分的。也就是说，无论是内存还是在当前结点，对于访问到的新结点而言，其索引的范围减小了一半。

（4）查询优化。

在查询优化算法上，磁盘数据库系统的作用是为了保证磁盘在其I/O上的减少。DRDBMS系统优化的方针如下：先对数据进行假定，再在磁盘上进行存放。磁盘数据库中的数据可能在内存缓冲中，也可能在磁盘上。磁盘在I/O上比内存访问是更大的，因此需要对磁盘数据库运行时的最坏情况进行假定。另外，内存数据库的数据是否在内存中进行存放是可以确定的。以这一假设为基础，要想实现查询算法的优化，就要保证数据都在内存中存放。内存数据库所进行的查询优先于磁盘的问题是不需要考虑的，所以其本身也是更加精确和简单的。对于内存数据库系统来说，在优化算法方面，它比磁盘数据库更具有优势。

（5）日志和恢复。

由于内存本身的性质是易失性的，这一存储介质需要对数据库进行备份。基于其易失性，MMDRMS在磁盘上进行备份的数据需要进行弥补。对于备份数据库和内存数据库来说，需要保证它们是同步进行的，这样的数据才具有一定的耐用性。这是数据库的基本准则。除此之外，在数据处理方面，ACID标准对于日志的精确性和其本身的恢复能力是有着基本要求的。目前，商业上的内存数据库系统已经在很多领域得到了应用，保证了数据的耐用性。但是，同步方式在优化上的实现，于日志而言，在数据耐用度和恢复能力是不同的；于系统而言，在性能上也是不同的。

2.A200内存数据库

ZXSS10 A200数据库系统分为两个部分，即数据库管理软件部分和数据库核心部分。数据库核心部分是相关数据在其集合上的结构化，包括数据库本身及其所具有的操作原语。对于数据库系统而言，应用程序是独立存在的，也是它重要的管理对象和核心。数据库不仅要对数据库进行维护和管理，同时还要实现对数据的维护、操作和定义等多种功能。不同的应用程序和数据库应满足对象不同的请求，并且对数据的安全性负责。数据库的核心是为了实现ZXSS10 A200数据库管理软件的功能，并在不同的应用层上实现数据库基本接口上的功能。ZXSS10 A200内存数据库所具有的性能可以满足数据库系统汇总的很多模块在数据操作上的要求。很多数据库应用接口在数据库系统上，速度比较快，同时也很可靠。目前，数据库系统中每条数据的插入速度大约是30微秒，删除速度大约是90微秒。

A200在数据库上采用的是关系数据库结构，其中的数据在组织方式上是面向对象的。根据数据在特点上的不同，A200可以分为三种，即数据表、数据表索引和数据表队列。每一类数据都可以在系统数据对象类上进行定义，而系统是在统一对象列上实现对数据的定义的，同时还进行统一管理。一个具体的数据对象也被称作某一类数据对象类的数据实例。每一个数据对象类在数据实例的分配上都添加一个16位的整数，从而实现了对其的表示，被称为“数据实例句柄”。数据实例在存储上是通过实例句柄来实现的。这种方式具有一个优点，即在数据管理上不具有稳定性，数据实例在变化的同时，它是不会发生变化的。这对于系统的稳定性具有重要的意义。该方式的另一个优点是方便了数据对象类的扩充，在对不同的数据对象类进行相应管理时，数据对象类的独立性要得到充分保证，同时还要能实现数据对象类的扩充，并且不能破坏原本数据的安全性。

在对每一种数据对象进行相应的基本操作和提供接口时，需要在数据管理上进行应用，如检索、插入、删除、修改等。对A200数据库系统的并发性问题的处理是从以下两个方面进行的：一方面，对有着较高优先级的进程进行异步消息方式或同步消息方式接口的访问，这种数据访问能保证时效性；另一方面，数据库在进程上的访问是通过同步调用的方式进行的，它们在优先级上的要求比数据进程更低。(www.xing528.com)

A200内存数据库在工作性能上的高低主要通过索引算法效率的高低来体现，其中包括删除、插入和修改等操作。对于A200来说，相应的索引算法对效率的提升是至关重要的，尽量缩短每个操作所占用的时间，以提高A200在整体上的性能。对于一些具体的索引算法，可以进行相应的分析，选择其中一些合适的部分，使之在A200内存数据库系统中得到充分应用。

（二）ZXSS10 A200索引算法的实现

目前，很多数据库索引技术的发展主要是基于对Hash索引和T树索引的研究。对于Hash算法，通过对其的有效利用可以改变内存数据库的访问效率，如快速搜索中的多目录Hash方法等，对其的研究就要在一定的系统中进行。目前的硬盘数据库所使用的最快的索引算法是B树，但对于内存数据库来说，B树在存取上的效率过低。而对于Hash索引算法和T树索引算法来说，其内存数据库主要有两种算法，内存数据库在索引上的研究主要就是基于这两种算法开展的。在Hash索引中，要先建立一个对应关系f，再对其进行查找。这一过程就是对这个关系f在其给定值K中的查找。这一给定值就相当于索引中的关键字。在创建Hash索引的过程中，存储关键字是非常重要的。这样一来，索引关键字在其空间上就不需要再进行申请了，从而节省了很多内存空间。索引关键字是Hash索引的重要特点，对内存数据库而言，这个选择是合适的。

对于顺序索引来说，这种索引算法的操作比较简单，其顺序索引一般采用二分查找法来实现，在实时性上要求对内存数据库进行满足。顺序索引空间在大小上是比较容易确定的，只要确定记录树的大小即可，这样就不需要重复申请多余的内存空间，从而节省了相应的内存数据库上的内存空间。

T树索引算法主要是为了实现像B树索引算法那样的索引算法，主要特点是快速。目前，B树索引算法在数据库索引算法中是最快的，但由于B树索引算法每个结点在其数据存储上的效率太低，因而对每个结点都要申请一定的内存空间，以满足内存数据库的需要。对于T树索引算法来说，它吸取了B树索引算法的优点，同时克服了B树索引算法的缺点，节省了内存空间，提升了索引效率。对于内存数据库来说，这一选择是合适的，且能很快找到关键字所在的结点。此外，通过对这一结点进行相应的二分法查找，能快速定位结点所在的位置。也就是说，T树索引算法是顺序索引算法和B树索引算法两者的完美结合。

1.Hash索引算法

ZXSS10 A200所使用的操作系统是VXWORKS^[4]。这一操作系统是嵌入式的，只支持4字节的关键字，如果其关键字超过4字节，就需要使用Hash索引方式。

Hash算法有很多种，包括折叠式Hash函数法、子域散列检索算法、快速搜索多目录Hash方法等。折叠式Hash函数法是把关键字值自左向右分成位数相等的几部分，每一部分的位数应与散列表地址的位数相同，只有最后一部分的位数可以短一些。把这些部分的数据叠加起来（去除进位），就可以得到关键字值的散列地址。子域散列检索算法是需要进行唯一性变化的。其在进行变换时，比ZXSS10 A200费时，所以需要增加额外的存储空间，会对A200在其内存数据库上的空间产生一定的影响。对于快速搜索多目录Hash方法来说，它需要申请更多的内存空间，以实现关键字的保存和展开，从而形成空间目录，这一过程是需要添加指针的。当哈希在数目上成倍增加时，其在期望的目录空间上也是成倍增加的。也就是说，在记录数目增加的同时，期望的目录在大小上也是相应增加的。之所以要使用Hash算法，主要是为了减少内存的使用量，同时实现检索效率的提升。对于ZXSS10 A200内存数据库系统而言，效率是至关重要的，需要着重考虑内存的使用情况。如果效率提到了提升，但内存花费较多，就说明ZXSS10 A200对其是不适合的，因此，用Hash算法实现对ZXSS10 A200的快速搜索是不合适的。

对这三种Hash算法进行相应分析后，折叠式Hash函数法在算法上相比另外两种方法而言，是处在底层的，但是针对ZXSS10 A200来说，其在环境上是合适的。

2.T树索引算法的实现

我们在这里引入一种新的索引类型，并把它定义为 IDX_TTREE，使用时判断代入的索引类型，如果为DX_TTREE，则为T树索引。

ZXSS10 A200内存数据库系统在每个数据表所具有的索引关键字上，长度是随机的。为了方便对空间的申请，T树索引在关键字索引上规定其长度不能超过4字节。这种规定与顺序索引是相似的，但是与顺序索引相比，T树索引需要更多的内存消耗，而且查找效率也是更高的。如果数据表在其中记录的数据量是较大的，则其关键字的索引在4字节以内。

首先定义一个用来确定T树每个结点的结构T_NODE。T_NODE中包括BF平衡因子、父结指针UP、左子结点指针LP、右子结点指针RP、索引关键字数量 KEYNUM、索引关键字数组TUPKEY［30］、记录号数组 UPLENO［30］等内容。

在对T树索引的结点结构和应用范围进行确定后，就要创建T树索引算法。由于数据表在容量上有所不同，所以要对T树上的结点个数nodenum进行确定，然后根据确定的结点在数量上的不同，为T树申请内存空间。同时，还要通过定义一个结构来实现T树对其内存空间的使用。这一结构包括结点数组，分为还没有对记录进行使用的结点空间和使用结点所具有的空间，每次去除的结点是node［nodeleft-1］，去除后要进行相应的减一操作。

查找是从T树的根结点开始的，首先要代入关键字TUPLEKEY，然后与根结点中最小的索引关键字进行比较。如果小于最小的索引关键字，就要对TUPLEKEY根结点的左子结点进行比较；如果大于最小的索引关键字，就要对其最大的关键字进行比较。如果TUPLEKEY比最大的关键字更大，就要把JPLEKEY代入根结点中，同时与右子结点进行比较。如果TUPLEKEY居于最小关键字和最大关键字之间，就需要进一步采用三分查找法，将TUPLEKEY与关键字进一步比较，找出相等的关键字，输出其记录号，然后进行查找；如果没有找到，就需要进行推出。通过这一步，我们发现相比顺序索引而言，T★树的查找效率更高。

在进行插入时，T树的根结点是重要开始，需要在结构上对这一结点的KEYNUM进行判断。如果其在数值上比30小，就可以在这一结点中对KEYNUM进行直接插入；如果其在数值上等于30，KEYNUM要对结点中的最小索引关键字和最大索引关键字进行相应的比较，并确定其插入的位置，其中包括根结点的左子结点、右子结点和根结点。如果还是根结点，其中的关键字就要在其所对应的记录号上移入根结点的左子结点或右子结点上。如果加入新结点，就需要提取并占用这个结点的空间记录。从结构上来说，则要删除这一结点的空间记录，只对没有被使用的结点空间进行记录。此外，需要保持T树本身的平衡状态，如果T树失去平衡，就需要对其进行相应的旋转操作，以保持T树处在平衡状态。

同样地，在进行删除时，T树的根结点也是重要开始。首先对关键字TUPLEKEY进行代入和查找，等找到其所在的结点后，根据对应的记录号，对结点中的TUPLEKEY进行删除。如果这种删除操作是在结点内部进行的，就要在记录号中对这一结点在左子树或右子树中的最小或最大关键字进行结点上的移入。如果是最后一个关键字，就要对其叶结点进行删除操作，并归还所占用的结构资源，同时相应增加TMARK中的记录。此外，还要保持T树的平衡状态，如果T树失去平衡，就需要对其进行相关的旋转操作，以保证T树处在平衡状态。