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

Research on Data Organization and Index of EMMDB

作　　者：宋玲[1] 杨雪君 马兰[1] 

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

出　　处：《计算机科学与探索》2010年第8期742-748,共7页Journal of Frontiers of Computer Science and Technology

基　　金：国家科技型中小企业技术创新基金No.07C26224501847;广西科学研究与技术开发计划项目No.09321073~~

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]