Journal of Frontiers of Computer Science and Technology ›› 2010, Vol. 4 ›› Issue (8): 742-748.DOI: 10.3778/j.issn.1673-9418.2010.08.008

• 学术研究 • Previous Articles     Next Articles

Research on Data Organization and Index of EMMDB*

SONG Ling1+, YANG Xuejun2, MA Lan1   

  1. <P class=3 style=
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-08-10 Published:2010-08-10
  • Contact: SONG Ling

嵌入式内存数据库的存储和索引算法研究*

宋 玲1+ , 杨雪君2, 马 兰1   

  1. 1. 广西大学 计算机与电子信息学院, 南宁 530004
    2. 广西壮族自治区电子产品监督检验所, 南宁 530031

  • 通讯作者: 宋 玲

Abstract: This paper proposes the EHAS(quasi-extendible hashing area-segment) and the PMCT-tree algorithms, which are more efficient ones on data organization and index of embedded main-memory database (EMMDB). The EHAS is a storage algorithm which combines quasi-extendible hashing and is based on area-segment method. It locates and stores records with corresponding unique triples, each of which has three parts separately as an area sign, a segment sign and a storage address sign. The PMCT-tree has a priority match catalog (PMC) more than typical T-tree. The PMC is composed of some edges thresholds, which are extracted from T-tree nodes. Experimental results indicate that the EHAS algorithm accelerates storage response time and its average querying time complexity can reach a constant level under certain conditions; and the PMCT-tree algorithm is good on effectiveness and querying response time.

Key words: : embedded main-memory database (EMMDB), T-tree, index, quasi-extendible hashing, area-segment method

摘要: 提出了用于嵌入式内存数据库的更高效的数据存储算法(EHAS)和索引算法(PMCT-tree)。EHAS算法是基于区-段式, 结合类可扩散列的思想, 将记录以唯一对应的三元组作为区标号、段标号、地址标号来定位存储的算法。PMCT-tree比典型的T树增加了一种多路分支目录(PMC), 它是由T树节点中抽取出的部分边缘阈值构成的。测试结果表明, EHAS算法加快了存储响应时间, 且在一定条件下其平均查询时间复杂度可达到常数级; PMCT-tree算法在有效性和查询响应时间上性能良好。

关键词: 嵌入式内存数据库, T树, 索引, 类可扩散列, 区-段式

CLC Number: