实时数据库混合索引机制的设计与实现

第３１卷第８期　２０１１年８月　计算机应用　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｖｏ１．３ｌ　Ｎｏ．８　Ａｕｇ．２０１１　

文章编号：１００１—９０８１（２０１１）０８—０２２６５—０５　ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１０８７．２０１　１．０２２６５　

实时数据库混合索引机制的设计与实现　

刘　波，范士明，刘　华　

（中国航天科技集团公司第五研究院五零三研究所，北京１０００８６）　（１ａｕ１９８３１００３＠ｙａｈｏｏ．ｃｏｒｎ．ｃｎ）　

摘要：在卫星地面设备监控中，需要将大量实时数据实时地存进数据库并提供实时查询、针对实时数据和　

Ｊｕｄｙ　ａｒｒａｙ数字树的特点，提出了一种基于内存映射文件的位图分配法，然后设计了一种哈希表、Ｂ　树和Ｊｕｄｙ　ａｒｒａｙ混　

合索引机制。通过大量记录的插入和查询，结果表明位图分配法能避免大量不可利用的内存碎片的产生，结合内存　

位图分配法的混合索引机制也为应用程序提供了实时的索引插入和查询。　关键词：实时数据库；位图分配法；内存映射文件；哈希表；Ｂ　树；Ｊｕｄｙ　ａｒｒａｙ　

中图分类号：ＴＰ３ｌ１．１３１　文献标志码：Ａ　

Ｄｅｓｉｇｎ　ａｎｄ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｈｙｂｒｉｄ　ｉｎｄｅｘ　ｍｅｃｈａｎｉｓｍ　ｆｏｒ　ｒｅａｌ－ｔｉｍｅ　ｄａｔａｂａｓｅ　

ＬＩＵ　Ｂｏ．ＦＡＮ　Ｓｈｉ—ｍｉｎｇ．ＬＩＵ　Ｈｕａ　

（５０３　Ｉｎｓｔｉｔｕｔｅ，ｔｈｅ　Ｆｉｆｔｈ　Ａｃａｄｅｍｙ　ｏｆ　Ｃｈｉｎａ　Ａｅｒｏｓｐａｃｅ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｃｏｒｐｏｒａｔｉｏｎ，Ｂｅｉｊｉｎｇ　１０００８６，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｉｔ　ｉｓ　ｎｅｃｅｓｓａｒｙ　ｔｏ　ｓｔｏｒｅ　ｍａｓｓｉｖｅ　ｒｅａｌ－－ｔｉｍｅ　ｄａｔａ　ｉｎｔｏ　ｄａｔａｂａｓｅ　ａｎｄ　ｑｕｅｒｙ　ｒｅｃｏｒｄｓ　ｆｒｏｍ　ｄａｔａｂａｓｅ　ｉｎ　ｒｅａｌ－－ｔｉｍｅ　ｏｎ　ｔｈｅ　ｆｉｅｌｄ　ｏｆ　ｓａｔｅｌｌｉｔｅ　ｇｒｏｕｎｄ　ｄｅｖｉｃｅ　ｍｏｎｉｔｏｒｉｎｇ．Ｔａｋｉｎｇ　ａｃｃｏｕｎｔ　ｏｆ　ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｒｅａｌ—ｔｉｍｅ　ｄａｔａ　ａｎｄ　Ｊｕｄｙ　ａｒｒａｙ，ａ　ｂｉｔｍａｐ　

ｍｅｍｏｒｙ　ａｌｌｏｃａｔｉｏｎ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ｍｅｍｏｒｙ　ｍａｐ　ｆｉｌｅ　ｗａｓ　ｐｒｏｐｏｓｅｄ．Ａ　ｈｙｂｒｉｄ　ｉｎｄｅｘ　ｍｅｃｈａｎｉｓｍ　ｗｈｉｃｈ　ｅｍｐｌｏｙｅｄ　Ｈａｓｈ　ｔａｂｌｅ，　

Ｂ　ｔｒｅｅ　ａｎｄ　Ｊｕｄｙ　ａｒｒａｙ　ｗａｓ　ｄｅｓｉｇｎｅｄ．Ｔｈｒｏｕｇｈ　ｉｎｓｅｒｔｉｏｎ　ａｎｄ　ｑｕｅｒｙｉｎｇ　ｏｆ　ｍａｓｓｉｖｅ　ｒｅｃｏｒｄｓ，ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｂｉｔｍａｐ　ａｌｌｏｃａｔｉｏｎ　ｍｅｔｈｏｄ　ａｖｏｉｄｓ　ｔｈｅ　ｇｅｎｅｒａｔｉｏｎ　ｏｆ　ｍａｓｓｉｖｅ　ｔｉｎｙ　ｍｅｍｏｒｙ　ｈｏｌｅｓ．Ｂｅｉｎｇ　ｃｏｍｂｉｎｅｄ　ｗｉｔｈ　ｂｉｔｍａｐ　ａｌｌｏｃａｔｉｏｎ　ｍｅｔｈｏｄ，　

ｔｈｅ　ｈｙｂｒｉｄ　ｉｎｄｅｘ　ｍｅｃｈａｎｉｓｍ　ｐｒｏｖｉｄｅｓ　ｒｅａｌ—ｔｉｍｅ　ｉｎｄｅｘ　ｉｎｓｅｒｔｉｏｎ　ａｎｄ　ｒｅｃｏｒｄ　ｑｕｅｒｙｉｎｇ　ｆｏｒ　ａｐｐｌｉｃａｔｉｏｎｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｒｅａｌ—ｔｉｍｅ　ｄａｔａｂａｓｅ；ｂｉｔｍａｐ　ａｌｌｏｃａｔｉｏｎ　ｍｅｔｈｏｄ；ｍｅｍｏｒｙ　ｍａｐ　ｆｉｌｅ；Ｈａｓｈ　ｔａｂｌｅ；Ｂ　ｔｒｅｅ；Ｊｕｄｙ　ａｒｒａｙ　

０　引言　

卫星地面设备监控系统需要对大量数据信息进行采集、　

传输、综合分析、计算等处理。从监控系统组成可以看出，数　

据是联系各功能模块的纽带。随着卫星地面应用系统的发　

展，地面设备监控系统的功能需求也不断增多、增强，数据量　

也不断扩大，数据之间的关系也越来越复杂。因此需要将数　

据库技术引入卫星地面设备监控，用数据库技术来管理、处理　

监控过程中的数据。但卫星地面设备监控中数据的一个显著　

特点是具有时间特性，且有效时间是短暂的，过时则失效。而　

以关系数据库为代表的传统数据库的设计目标是维护数据的　

正确性、保证系统的低代价和提供友好的用户接口。这种数　

据库系统对传统的商务和事务型应用是有效、成功的，但对于　

新领域的实时数据和实时事务的应用要求难以胜任。所以，　

需要结合数据库技术和实时技术，研究具有显式定时限制的　

实时数据库系统…。　

键值（ｋｅｙ—ｖａｌｕｅ）型索引性能的好坏直接影响实时数据库　

的稳定性、可靠性、实时性。在卫星地面设备监控中，实时数　

据库将面临超大量的实时数据，最新的实时数据必须能在一　定时间内存入数据库，相对陈旧的历史数据在给定ｋｅｙ时必　

须能在一定时间内检索到相应的值。传统的键值型索引并没　

考虑到这种超大量实时数据的特点，导致其在内存空间的利　

用效率、索引插入和查询的实时性上很难达到要求。对此本　

文根据地面设备监控中实时数据的特点以及检索要求，采用　

内存映射文件技术处理数据文件的读取，提高了数据文件的　Ｉ／Ｏ读写速度；利用位图分配法代替操作系统的内存分配，可　

以避免大量内存碎片，提高数据库文件存储空问的利用率；采　

用混合索引取代数据库中常用的哈希表、Ｂ　树、Ｔ树索引机　

制，实现了索引压缩和有序存储，并保证记录的实时插入和查　

询。　

ｌ　基于内存映射文件的位图分配法　

１．１　内存文件映射机制　内存映射文件允许在进程的虚拟地址空间中保留一段内　

存区域，并将物理存储器中的目标文件提交给该区域，映射到　

这段虚拟内存之中。这样，物理存储器来自一个已经位于磁　

盘上的存储近期实时历史数据的文件，而不是系统的页文件。　

一旦该文件被映射，就可以用存取内存数据的方式直接操作　

文件中的数据，就像整个文件已经被加载到内存中一样。因　此使用内存映射文件处理存储在磁盘上的文件时，将不必再　

对文件执行Ｉ／Ｏ操作，这意味着对文件进行处理时将不必再　为文件申请并分配缓存，所有的文件缓存操作均由系统直接　

管理，由于取消了将文件数据加载到内存、数据从内存到文件　

的回写以及释放内存块等步骤，使得内存映射在处理实时数　

据库这种有着大数据量的文件时有显著的优势。　

实时数据库必须作为多个进程共享数据的仓库。内存映　

射文件正是计算机操作系统提供的解决多个进程间共享数据　

的最有效方法。数据共享通过让多个进程映射同一文件内核　

对象的视图来实现的，这意味着进程间将共享物理存储器中　

的同一个数据库文件。因此，当一个进程将数据写入一个共　

收稿日期：２０１１—０２—２１；修回日期：２０１１—０４—２８。　基金项目：中国空间技术研究院ＣＡＳＴ创新基金资助项目（ｃａｓｔ２０１０－０８）。　作者简介：刘波（１９８３一），男，河南信阳人，博士研究生，主要研究方向：分布式实时数据库、卫星遥感信息处理；　范士明（１９４５一），男，上　海人，研究员，硕士，主要研究方向：卫星遥感信息处理；刘华（１９６９一），男，重庆人，高级工程师，硕士，主要研究方向：卫星遥感信息处理。

　计算机应用　第３１卷　

享文件映射对象的视图时，其他进程可以立即看到它们视图　

中的数据变更情况。同时，内存映射文件将作为数据库持久　

存储的手段。当事务提交时，如果内存中相应于磁盘文件的　

页面发生了改变，调用操作系统的内外存交换机制，将事务对　

数据库的更新操作保存在磁盘上。此时持久化到磁盘上的文　件将作为数据库的后端备份，一旦应用程序出错或掉电导致　

内存数据丢失时，磁盘文件将被重新映射，使数据库能尽可能　

快地从故障中恢复过来。　

１．２位图分配法　

实时数据库系统中，内存分配要求实时高效。本文借助　位图　－３１实现内存分配，根据系统配置大小设定共需多少个　

位图页面，每个位图页面为４ＫＢ，因此共有３２Ｋ比特位，每个　

比特位可分配８　Ｂ（也可以不是８　Ｂ，可根据系统配置要求而　

定）。如果该位为０，表示该比特位代表的相应位置的８　Ｂ尚　

未分配，否则相应位置的８　Ｂ已分配出去，因此一个位图页面　

可分配的空间为２５６　ＫＢ。文件头包含数据库文件的描述信　息，页面地址分别指向各自的位图页面首地址，ｎ个位图页面　

连续集中在一起，可减少因位图页面过于分散而导致的内存　

碎片较多的问题。每个位图页面负责其分配的区域，如位图　

页面０负责分配第一个２５６　ＫＢ，位图页面１负责分配第２个　

２５６ＫＢ。　１）位图页面内寻找可分配空间过程。　如下代码所示，其中ｐｏｓ以字节为单位，ｉ表示正搜寻的　

位图页面编号（从０开始）；ｏｆｆｓ指当前位图页面搜寻的起始　

点，以字节为单位，其范围是（０，…，４Ｋ一１）；ｍａｓｋ为ｏｆｓ位置　

上的值，单字节长度；ｈｏｌｅＢｉｔＳｉｚｅ指目前搜寻到的连续的比特　０数目；ｓｉｚｅ指请求分配的字节数，ｏｂｊＢｉｔＳｉｚｅ指分配ｓｉｚｅ所需　

比特数；ＰａｇｅＳｉｚｅ是页面大小，４　ＫＢ；ｆｉｒｓｔＨｏｌｅＳｉｚｅ［ｍａｓｋ］指　

ｍａｓｋ中从最低位往最高位数起的第一个连续比特０个数；　

ｍａｘＨｏｌｅＳｉｚｅ［ｍａｓｋ］表示ｍａｓｋ中最多的连续比特０个数，代　

表可分配的最大空间；ｍａｘＨｏｌｅＯｆｆｓｅｔ［ｍａｓｋ］为最多的连续比　

特０个数区域在ｍａｓｋ中的位置；ｌａｓｔＨｏｌｅＳｉｚｅ［ｍａｓｋ］表示从最　

高位往最低位数起的连续的比特０个数；ｍａｓｋ的值为（０，…，　

２５５），它们有各自的ｆｉｒｓｔＨｏｌｅＳｉｚｅ、ｌａｓｔＨｏｌｅＳｉｚｅ、ｍａｘＨｏｌｅＳｉｚｅ、　

ｍａｘＨｏｌｅＯｆｆｓｅｔｏ　ｉｆ（ｈｏｌｅＢｉｔＳｉｚｅ＋ｆｉｒｓｔＨｏｌｅＳｉｚｅ［ｍａｓｋ］）／＞ｏｂｊＢｉｔＳｉｚｅ｛　ｐｏｓ：８×（（ｉ×ＰａｇｅＳｉｚｅ＋ｏ如）｝８一ｈｏｌｅＢｉｔＳｉｚｅ）；　如果从ｐｏｓ开始ｓｉｚｅ大小的区域尚未保留，保留这片区域，将位　图页面中ｐｏｓ开始ｓｉｚｅ大小的相应位全置１，然后撤销保留区　域，内存分配成功，返回ｐｏｓ；否则，ｏｆｆｓ增加（ｏｂｊＢｉｔＳｉｚｅ＋７）／８，　ｈｏｌｅＢｉｔＳｉｚｅ置０，继续搜索可分配空间　｝ｅｌｓｅ　ｉｆ（ｍａｘＨｏｌｅＳｉｚｅ［ｍａｓｋ］／＞ｏｂｊＢｉｔＳｉｚｅ）｛　ｐｏｓ＝８×（（ｉ×ＰａｇｅＳｉｚｅ＋ｏｆｆｓ）×８一ｍａｘＨｏｌｅＯｆｆｓｅｔ［ｍａｓｋ］）；　如果从ｐｏｓ开始ｓｉｚｅ大小的区域尚未保留，保留这片区域，将　位图页面中ｐｏｓ开始ｓｉｚｅ大小的相应位全置１，然后撤销保留　区域，内存分配成功，返回ｐｏｓ；否则，ｏｆｆｓ增加（ｏｂｊＢｉｔＳｉｚｅ＋７）／　８，ｈｏｌｅＢｉｔＳｉｚｅ置０，继续搜索可分配空间　｝ｅｌｓｅ　ｉｆ（上述两条件都没有满足）｛　如果ｌａｓｔＨｏｌｅＳｉｚｅ［ｍａｓｋ］等于８，将ｈｏｌｅＢｉｔＳｉｚｅ加８；否则将　ｈｏｌｅＢｉｔＳｉｚｅ设置为ｌａｓｔＨｏｌｅＳｉｚｅ［ｍａｓｋ］　ｏｆｆｓ加１：　｝　如果ｏｆｆｓ￣＞ＰａｇｅＳｉｚｅ，这时搜寻到下个位图页面，置ｏｆｆｓ为０，ｉ加１　２）扩展位图页面过程。　

当搜寻全部位图页面后，还没能找到指定大小的空间，则　需要增加新的位图页面，此时等于扩展可分配的内存空间。　ｅｘｔｅｎｓｉｏｎ为新扩展的内存空间大小，ｍｏｒｅＰａｇｅｓ为重新开辟的