面向内存数据库的类字典树索引综述与性能比较

如何快速存取海量数据是大数据时代数据库系统面临的重大挑战.利用大内存构建内存数据库系统是实现大数据实时存取的可行途径.在此背景下,用于加速内存数据存取的内存数据库索引成为近几年国内外的研究热点.但是,内存数据库索引也面临着诸多挑战.以常见的内存B+树索引为例,第一个问题是索引的空间效率较低,这是因为内存B+树索引的节点内部存在较大的空间浪费;第二个问题是索引的查询复杂度较高,B+树的查询复杂度受限于数据规模,随着数据规模的扩张,索引的搜索效率也会下降;第三个问题是变长数据支持弱,B+树对于变长键的支持比较差,往往难以适应实际应用的需要.近年来,由于字典树具有空间代价低、查询效率与数据规模无关、支持变长键等优点,逐步成为了内存数据库索引研究中的一个主要方向.本论文围绕面向内存数据库的类字典树索引,首先介绍了字典树的概念、特点和历史,然后系统梳理和总结了类字典树索引的现状和最新进展,之后提出了一种全新的分类方法对类字典树索引进行了分类.在此基础上,论文对主流的六种类字典树索引进行了实验,在多个数据集和负载上进行了性能对比,并基于实验结果讨论了类字典树索引的设计和使用建议,最后展望了未来类字典树索引的发展方向.

有向图上基于层次树索引的最大cycle truss社区搜索

社区搜索旨在从信息网络中找出包含用户查询顶点的高内聚连通子图,cycle truss是一种基于cycle三角形的社区搜索模型,而现有的基于索引的cycle truss社区搜索方法存在索引空间大、搜索效率低、社区内聚性低的缺点。为了解决这一问题,提出一种基于层次树索引的最大cycle truss社区搜索方法。首先,提出了k-cycle truss分解算法,并引入了两个重要的概念:cycle三角连通与k-层次等价。基于k-层次等价设计了层次树索引TreeCIndex与表结构索引SuperTable,在此基础上,并基于这两个新的索引,提出了两个高效的cycle truss社区搜索算法。在4个真实数据集上与已有的基于TrussIndex与EquiTruss的社区搜索算法进行了比较,实验结果表明,TreeCIndex与SuperTable比TrussIndex与EquiTruss节省至少41.5%的空间,索引构建的时间节省8.2%至98.3%,且搜索最大cycle truss社区的效率分别高出了一个和两个数量级。

基于改进B+树索引的大型数据库检索研究

为解决因信息搜索时间过长造成的数据库检索受限问题,在节约等待时间的同时,完成对数据库主机的精准检索,针对基于改进B+树索引的大型数据库检索方法展开研究。在改进B+树索引架构模型的支持下,完成对数据库主机的查询,再联合关联数据样本,确定模态调度系数的取值范围,实现基于改进B+树索引的数据库主机调度。实施数据矩阵分解,通过构建哈希检索函数的方式,完成对数据库与索引信息的配对处理,实现基于改进B+树索引的大型数据库检索方法的设计。实验结果表明,改进B+树索引条件作用下,信息平均搜索时间小于0.40 ms,因信息搜索时间过长造成的数据库检索受限问题得到较好解决。

空间数据库引擎的R树索引

介绍了空间数据库引擎（SDBE）的R树索引结构，给出系统使用R树索引的方式，并描述了利用R树索引实现最近邻居查询的分支-限界算法,包括代价函数及其上、下界函数的定义，以及算法的伪码形式。

基于排序树索引的轨迹压缩方法

原始采集的GPS轨迹数据通常非常庞大,导致对其的传输、存储和处理变得越来越困难,需要对原始GPS轨迹数据进行压缩.现有的基于方向的轨迹压缩方法存在可容忍误差难以确定、计算代价大、压缩效果较差等问题.针对这些问题,提出了基于排序树索引的轨迹压缩方法,借助于排序树索引,在轨迹压缩的过程中进行有效的剪枝,提高了轨迹压缩的效率.同时,对压缩轨迹中轨迹点的去留起决定作用的指标——线段误差进行了重新定义,提高了轨迹压缩的效果.大量真实数据集上的实验验证了所提的轨迹压缩方法的有效性和高效性.

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

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

嵌入式数据库B+_树索引机制研究及其改进

针对嵌入式数据库中B+_树索引机制的空间利用率低下及面对庞杂数据的处理能力不足,提出了一种改进的B+_树索引机制,使用这种索引机制能较好地解决在存储容量受限的嵌入式系统中提高数据空间利用率和处理庞杂数据能力的问题。

图形处理器上CSB^+-树索引的并行构建算法

为提高缓存敏感CSB+-树索引的操作效率,在图形处理器(GPU)上研究CSB+-树的并行构建和查询性能.通过分析索引树内部节点的每一键与对应叶子节点的映射关系,提出了一种一次性并行构建CSB+-树所有内部节点键值的无锁并行算法,以最大并行度来快速构建索引树.该算法通过设计GPU平台上支持CSB+-树的索引数据任意伸缩的动态数组来解决GPU上不能动态分配显存空间的问题,通过在索引内部节点的边界增加填充位来减少线程块的线程分支数,从而提高CSB+-树的查询效率.实验结果表明,文中所提算法的运行时间比基于单个节点和基于树层的并行算法分别提高了31.0和1.4倍.

一种改进的XML压缩树索引技术

压缩树索引技术是XML数据压缩的热点问题之一,本文提出一种压缩树索引改进方法。针对压缩树在查询过程中不能很好的解决向上匹配与向下匹配的问题,改进方法引入正排索引和倒排索引。当查询到组一级时,利用正排索引可以快速的查找出以该组为父节点的子组。而选出符合值谓词的元素后,在进行向上匹配时利用倒排索引可找出该元素的父节点。新的索引方法在保留原压缩树索引优点的基础上,解决了压缩树索引在查询过程中匹配问题。

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

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

树索引数据差分隐私预算分配方法

树索引空间数据进行差分隐私保护时需要产生噪声,针对现有差分隐私预算采取均匀分配方式,普通用户无法个性化选择的问题,提出等差数列分配法和等比数列分配法两种分配隐私预算策略。首先,利用树结构索引空间数据;然后,用户根据隐私保护度的需要和查询精确度的需要,个性化设置相邻两层分配的隐私预算的差值或比值,动态调整隐私预算;最后,隐私预算分配给树的每一层,实现了个性化按需分配方式。理论分析和实验结果表明,与均匀分配方式相比,这两种方法分配隐私预算更加灵活,且等比数列分配法优于等差数列分配法。

基于R树索引的智能交通系统的算法研究

由于道路交通矛盾的现象已经日益严重,利用智能交通系统解决交通问题已成为普遍共识。文章重点讨论了地理信息系统技术和全球定位系统技术等相关技术,并利用改进的R树索引完成了智能交通系统的核心不确定范围查询算法,分析与实现了智能交通系统。

基于R-树索引的高维相似重复记录检测改进算法

经典的相似重复记录检测算法SNM算法随着记录维度的增加,投影过程不仅会导致数据丢失,算法的误差率也会明显增大.针对SNM算法的不足,提出DRR算法,利用R-树构建索引保留记录的高维空间特性,通过聚类减少记录在叶子节点中的比较次数提高效率,同时改进度量记录相似性的距离算法,避免高维数据稀疏性的影响.最后,通过真实数据在不同维度上分别与SNM算法进行对比,验证了算法的有效性.

一种基于二层网格的移动对象B+树索引

在已有的基于空间分割的移动对象B+树索引基础上,提出一种分割空间的新方法,对空间进行二层网格分割,使空间分割很好地解决由移动对象在空间中分布不均造成的索引效率下降的问题。给出基于这种索引结构的Range查询和kNN查询算法。实验结果表明,该索引结构的性能基本不受移动对象分布的影响。

Oracle B*树索引内部机制及其应用的研究

Oracle数据库应用系统的性能优化是一项系统化的工程,涉及到数据库结构的各个方面。本文从B*树索引入手,分析了B*树索引的结构及原理,阐明了如何正确合理地使用B*树索引及其如何优化数据库系统的性能。

MapReduce模型下基于R树索引的Skyline查询算法

提出一种MapReduce并行计算模型下基于R树索引的Skyline查询算法,解决了海量空间数据集下执行Skyline查询效率低的问题.通过建立R树索引实现空间数据不同粒度的范围剪枝,有效降低了分布式Skyline查询需扫描的数据规模,提高了在MapReduce模型下Skyline查询的执行效率.在不同数据分布下进行对比实验的结果表明,该方法比已有算法在执行效率上更具优势.

面向空间数据的LSM树索引研究综述

空间数据在城市规划、天气预报、资产管理以及路线导航上有着广泛的应用。传统的关系型数据库不能满足空间数据高频存取的需求,面向空间数据的LSM树索引能够提高空间数据的写入和查询性能。但在索引设计中,需要面临索引结构设计、提升查询性能和降低更新开销三方面问题。对此,本文分别对基于空间填充曲线的LSM树索引结构和基于树状结构的LSM树索引结构两方面的现有工作进行分析,比较其优缺点,并展望了该方向的机遇和挑战。

一种顾及导航数据属性的K-DA树索引方法

为了从海量GPS导航数据中高效快速提取有效信息,通过扩充传统空间索引K-D树,提出一种顾及导航数据属性的新的索引方法:K-DA树索引,并对其进行仿真.实验结果表明:在用于导航数据的检索方面,K-DA树索引的索引速度达到传统空间索引速度的2~4倍,且数据越多,时间相差越大,效率越高.

基于动态融合索引树的ARXML查询处理算法

随着汽车行业的不断发展和智能化进程的加速,AUTOSAR已成为一种广泛采用的汽车软件架构标准,ARXML(AUTOSAR结构化文档)是该架构标准中描述车辆电子控制单元(electronic control unit,ECU)的重要资源。针对大量数据密度高且内容复杂的ARXML文档查询处理效率的问题,提出了一种基于动态融合索引树的结构化文档查询处理算法。算法从节点关系规则出发,对单个文档中的内部节点和不同文档中节点之间的关系规则进行分析,在保留节点原始关系的同时构建了带有外部关系的节点关系结构,并基于结构化文档查询表达式对该结构进行改进,最后将其扩展成动态融合索引树结构,降低文档解析处理时间消耗,提高查询性能。复杂性分析和实验结果表明,使用动态融合索引树结构的文档查询效率高于现有的查询方法,具备一定的实用性。

基于改进型B+树的电力多模态数据索引系统研究

电力系统数据在指数级增长的同时也逐渐呈现出多模态特性,这使得传统索引方法不能满足电力业务对异构数据进行快速内容检索与协同管理的需求。因此,本研究在传统B+树索引的基础上,加入倒排索引,并针对电力多模态数据设计了双层混合索引结构。该结构对数据属性和属性值分别建立索引,并依据数据属性的不同类型构建不同的索引结构。双层混合索引能够避免传统单一B+树的不足,在降低时间和空间开销的同时更好地满足了电力业务需求,从而为电力系统智能化分析与应用提供有效支撑。