一种集成R树、哈希表和B^*树的高效轨迹数据索引方法

为兼顾时空索引方法的空间利用率、时间效率和查询种类,提出了一种新的轨迹数据索引方法——HBSTR树。其基本思想是:轨迹采样点以轨迹节点的形式成组集中管理,哈希表用于维护移动目标的最新轨迹节点,轨迹节点满后作为叶节点插入时空R树,另外采用B*树对轨迹节点构建一维索引,既有利于提升索引创建效率,又同时满足时空条件搜索和特定目标轨迹搜索等多种查询类型。为提升时空查询效率,提出了新的时空R树评价指标和节点选择子算法改进时空R树插入算法,同时提出了一种时空R树的数据库存储方案。试验结果表明,HBSTR树在创建效率、查询效率和支持查询类型等方面综合性能优于现有方法,支持大规模实时轨迹数据库的动态更新和高效访问。

RFN-B^+树索引文件及其有效性

在对比传统的Ｂ树和Ｂ＋树的定义和操作算法的基础上，定义了一种新的Ｂ＋树：ＲＦＮ－Ｂ＋树，以获得更高的空间利用率和可用性．首先比较和分析了ＲＦＮ－Ｂ＋树与传统Ｂ＋树的空间效率，然后讨论了ＲＦＮ－Ｂ＋树索引文件的有效性以及支持这种有效性的全链接指针结构和两个备用模块：基于虚拟根结点的随机检索算法和重构结点的算法．

e—B^＋树：面向多用户数据库系统优化的索引技术

Ｂ＋树在数据库系统中已成为一种标准的索引结构，其上的并发控制机制对多用户数据库系统的性能有很大的影响．本文提出了一种变种Ｂ＋树──弹性Ｂ＋树－ｅ—Ｂ＋树（ｅｌａｓｔｉｃＢ＋－ｔｒｅｅ），定义了其上的安全点和操作及并发控制方法，对ｅ—Ｂ＋树的重构时机也进行了调整，降低了ｅ—Ｂ＋树上结点的合并／分裂频率，减少了ｅ—Ｂ＋树的维护开销，也缩短了封锁时间，从而使得其上操作的并发度和系统的效率得以提高．

B^+树索引文件结构的优化设计

指出当普通B+树的数据块设计为定长时，数据块长度的选择具有一个最优的选取设计过程。给出了在两种数据库系统模型中，对B+树索引文件结构的优化设计：（1）在具有限量内存的数据库系统DBSLAM（DatabaseSystemswithLimitedAmountofMainMemory）模型中，只是缓存B+树中的部分结点；（2）具有极大数量内存的数据库系统DBSVLAM(DatabasesystemswithVeryLargeAmountofMainMemory)模型中，将缓存B+树中的所有结点。对于DBSLAM和DBSVLAM，分别建立了一个时间开销模型和一个时空开销模型，并以此作为系统优化的基础。

面向嵌入式数据库的改进B^+-树索引机制

B^+-树是数据库中常用的索引机制,它最大的优点是效率高,而最大的缺点是空间利用率较差。这对空间资源非常有限的嵌入式数据库来说影响尤为巨大。本文针对B^+-树的这个缺点,研究了一种改进B^+-树,并将改进后的B+-树索引机制成功地应用在嵌入式数据库-伯克利数据库中。这种改进B+-树索引机制不仅继承了B^+-树效率高,能同时进行随机查找和顺序查找的优点,还克服了B^+-树空间利用率较差的缺点,更提高了数据库查找记录的速度。实验结果证明了改进B^+-树索引机制比B+-树索引机制具有更高的空间利用率。

一种新的基于B^+树结构的XML元素的索引方法

提出了一种用于搜索XML文档的新的索引方法即RIST。通过采用代码化的结构序列(SES)来表示XML文档和XML查询,得出查询XML数据等同于查找子序列匹配。RIST采用树结构作为查询的基本单元,从而避免了代价高昂的连接操作。另外,RIST还在XML文档的内容和结构上提供了一个统一的索引,所以它的一个很明显的优势就是克服了仅仅根据内容或结构建立索引的弊端。实验表明RIST在支持结构查询上是一种高效的方法。

全链接指针B^+树的研究

在对比传统的Ｂ~＋树的定义和操作算法的基础上，定义了一种更适合于物理索引文件结构设计的Ｂ~＋树：ＦＬＰ－Ｂ~＋树。经过对数据的研究和分析表明，与一般 Ｂ~＋树相比， ＦＬＰ－Ｂ~＋树具有更高的空间利用效率。同时，为 ＦＬＰ－Ｂ~＋树索引文件设计了一种全链接的指针结构，以提高系统故障恢复的能力，以及在故障恢复期间保持等效的不中断服务的能力，亦即系统的有效性。

XML数据的B^+树存储实现及更新

XML已成为Web数据表示和交换的标准,如何有效实现对于XML数据的存储、查询及更新操作是XML相关技术研究中的一个重要领域.本文简要介绍了基于模式匹配的XML数据库系统(DISXDBS)组成,重点研究了基于模式匹配的XML数据库系统(DISXDBS)上实现用B+树存储XML文档以及对其进行查询、更新等简单操作,并对目前几种常见XML文档的存储策略进行比较.

DVBB:基于Dewey向量的B^+树索引结构连接算法

为解决XML数据库中的结构关系查询问题,本文以Dewey向量为基础,提出了基于Dewey向量的B^+树(Dewey Vector Based B^+ Tree,简称为 DVBB)双栈结构连接算法。该算法利用了两个栈,PublicStack和 Privat-eStack,在这两个栈的基础上,利用DVBB索引,能够最大限度地避免那些不能产生连接结果的元素参加连接运算。一系列的实验结果表明,基于DVBB的双栈结构连接算法,无论是对于有效的跳过“祖先”还是“后代”节点,都具有很高的性能。

基于并行B^+-树的并行Join算法的设计、分析与实现

B＋-树是一种有效的数据库存储结构，被普遍应用于各种关系数据库系统．把B＋-树并行化，使之用于并行数据库系统显然是一项很有意义的重要工作．本文研究了适用于并行数据库的并行B＋-树存储结构，提出两类基于并行B＋-树的并行Join算法．理论和实验结果表明，这些算法效率高于其它并行Join算法．

一种新的分布式并行索引树——DPB^+-Tree

随着数据规模的增大,查询越来越复杂,分布式并行索引以其高性能而逐渐成为解决复杂查询问题的有效手段。本文提出一种适合于分布式并行的新索引树结构——DPB^+-Tree,该索引树以B^+树和 hash结构为基础,其叶子结点被组织为有n个散列表元的hash表链,从树的根结点到叶子结点,结点副本数量逐渐减少,并且其数量的变化是动态的。对DPB^+-Tree响应时间的仿真结果表明 DPB^+-Tree系统提高了系统的查询效率,与其它相关策略,如CPB方法比较具有较明显优势。

流水线算法及其在B^+树结构维护方面的应用

流水线技术是并行处理中一项非常重要的并行技术，将流水线技术用于B+树这一数据结构的维护，给出了在B+树中插入或删除一组元素操作的并行算法，并给出了相应的性能分析。

基于B^+树的大规模XMARK数据存储算法研究

随着互联网的不断发展,XM L数据目前已被广泛应用到数字图书馆以及各种大型数据库中,因此MARK数据转化为XM L数据成为研究的热点.对现有的XM L数据存储方式进行研究,发现MARK数据转化为XM L数据算法的好与坏直接影响到检索及数据的更新.采用一种B+树的树结构作为存储索引树提高了存储和检索速度,采用一种特殊的散列函数作为数据的存储方式,同时该散列函数得到的关键值可作为B+树的结点数据,极大提高检索速度和解决了地址冲突等问题.

重定向内存资源B^+树索引文件缓冲区策略

在作者研究的鉴定古陶瓷的专家系统(Expert System for Appraising Pottery and Porcelain,ESAPP)中,需要使用一个大型的数据库管理系统,如何合理而有效地使用内存资源,是进行系统设计时需要考虑的一个重要因素。在该系统中,设计了一种“可重定向内存资源的B+树索引文件缓冲区管理策略”,它把文件缓冲区中的内存页面定义为一种可以重定义的系统资源,极大地提高了系统的运行效率。

一种采用隐文B^+树的文件目录索引方法

传统方法使用对文件或整个磁盘进行加密的方法来保护数据信息,然而加密后的信息本身无法隐藏自身的存在,文件本身的存在就会促使感兴趣的攻击者去企图破解加密信息。在某些情况下攻击者甚至可以使用强迫手段迫使文件的主人公开他的加密密钥,这使得复杂的加密技术变得毫无意义。介绍一种新的着重于隐藏数据的存在性的加密手段———隐文加密(Steganography,隐写术)来对重要文件的存储进行加密,该方法采用隐文B+树(Steg B+Tree)建立UNIX系统的文件索引,并通过隐藏表将隐文B+树索引隐蔽起来,使攻击者无法知道重要信息的存在,从而使要保护的信息更安全。

B^+树的研究

在对比传统的树的定义和操作算法的基础上,定义了一种更适合于物理索引文件结构设计的树——FLP树。经过对数据的研究和分析表明,与一般树相比,FLP树具有更高的空间利用效率。同时,为FLP树索引文件设计了一种全链接的指针结构,以提高系统故障恢复的能力,以及在故障恢复期间保持等效的不中断服务的能力,亦即系统的有效性。

一种处理B^+树重复键值的方法

当前B^+树索引结构常采用"溢出页"处理重复出现的键值,易于实现,但存在严重的空间浪费。该文通过改进索引结构的定义,使B^+树能够显式支持重复键值,并给出相应算法。实验证明,采用该方法的P+树能有效减少索引文件的大小,使B^+树满足更多数据库索引的需求。

基于B^+树的多关键字密文排序检索方法

针对当前社会信息量大、隐私信息需要加密存储带来的检索难度大等问题,研究分析了现有的基于密文的可搜索加密方案,提出了一种基于B^+树的多关键字密文排序方法。利用向量模型构建索引和查询陷门,根据相关性分数和关键字匹配度对检索结果进行排序。在真实数据集上进行了实验,结果证明本方案具有较高的检索效率。

FLP-B^+树索引文件的有效性

该文描述了一种具有较高空间利用效率的全链接指针 Ｂ~＋树（Ｆｕｌｌ－ｌｉｎｋ Ｐｏｉｎｔｅｒ Ｂ^（＋） Ｔｒｅｅ，简称 ＦＬＰ－Ｂ^（＋）树）索引文件，为提高系统故障恢复的能力，以及在故障恢复期间保持等效的不中断服务的能力，亦即系统的有效性，文章给出了两个备用模块：基于虚拟根结点的随机检索算法和重构结点数据块的算法。

B^+树阶数m的最优选取

本文指出对普通的B^+树作了一定的限制后,当选择B^+树适当的阶数m时,对B^+树索引文件的时间和空间利用率有一个最优的设计过程。分别给出了应用在两种数据库系统模型中的B^+树索引文件结构:(1)具有有限内存的数据库系统(DatabaseSystems with Limited Amount of Main Memory,简称为DBSLAM),在DBSLAM模型中,我们只是缓存B^+树中的部分结点;(2)具有极大内存的数据库系统(Database Systems with Very Large Amount of Main Memory,简称为DBSVLAM),在DBSVLAM模型中,我们将缓存B^+树中所有的结点。基于以上两种模型,我们分别建立了两个不同的时空开销模型,并以此进行了优化设计。