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

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

HyperTree:高并发B+树索引加速器

B+树是关系型数据库中用来加速查询的常用索引结构,通过构建平衡树维护关键属性的顺序.索引提升了数据库查询性能,但其严格的有序关系增加了数据库表的维护开销.特别是在大数据场景下,数据量激增使得索引查询和维序性能进一步下降.如何平衡B+树的查询和维序性能,以及在大数据场景下提升索引查询和维序的效率,对提升索引系统性能具有重要意义.由此设计了一种专用的B+树索引加速系统,对存储和计算进行协同优化,均衡提升索引查询和维序性能.利用内存突发读写高带宽的特性设计规则的树和节点存储格式以提升内存带宽利用效率,设计高效的同构计算架构和多数据通道以提升索引操作并行度.同时设计解耦合的子树结构缓解索引维护时的树读写冲突.实验结果表明,相比于CPU,B+树索引加速系统能够提升系统查询性能超过6.84倍,提升索引维序性能提升超过29.14倍.

LI-Tree:一个基于非易失性内存和轻量级B+树的学习索引

大数据背景下剧增的数据给经典的内存索引技术带来了巨大挑战,为了实现对海量数据的高性能索引,工业界和学术界分别从设备和结构角度推出了高性能大容量的非易失型内存(Non-Volatile Memory,NVM)和受机器学习启发的学习索引(Learned Index,LI).然而目前基于NVM的学习索引结构的相关研究非常稀少,在如何结合NVM和LI来高效地索引海量数据方面还有许多问题需要解决.本文提出了一种基于NVM的新型智能索引结构LI-Tree,充分发挥了两者的优势.具体的,LI-Tree可分为三层:由机器学习模型组成的能够提高LI-Tree单点性能的模型层、由静态数组构成的减少NVM写的数据索引层和由一系列轻量级B+树组成以避免模型层插入时频繁重训练的数据层.在真实设备上评估表明,LI-Tree相比传统B+树,插入、查询和删除性能分别提高了70%、30%和130%.另外,LI-Tree与学习索引结构ALEX,PGM-Index和XIndex对比,插入性能分别提升了80%,130%和150%.

基于B+树的多媒体教育资源层次化索引模型

为了能够在海量的多媒体教育资源中快速且准确地检索出所需要的部分,提高教育资源利用率,设计一种基于B+树的多媒体教育资源层次化索引模型。首先对多媒体教育资源属性进行判断,并对数值型资源进行标准化和离散化处理,然后利用B+树建立其索引以及索引库,最后设计相应的检索算法,完成资源查找。结果表明:与R树索引模型、四叉树索引模型、多哈希表索引模型、网格索引模型、B-树索引模型相比,所设计的索引模型占据存储空间最小,检索时间最短,NDCG值较高,综合表现好。

LayerLSB:基于分层局部敏感B树的最近邻搜索

最近邻搜索由于其广泛的应用已成为一个重要的研究课题。传统的空间索引结构,如R-tree和KD-tree,可以在低维空间中高效地返回准确的最近邻搜索结果,但不适用于高维空间。局部敏感B树(LSB)将数据点哈希到可排序的一维值,并将它们排列成树状结构,这在不影响结果质量的前提下极大地提高了传统局部敏感哈希(LSH)所需的空间和查询效率。但是,LSB并没有考虑到数据分布,它在均匀的数据分布设置中表现良好,但在数据倾斜时表现出了不稳定的性能。针对这个问题,文中提出了LayerLSB,通过探索哈希值的密度对密集范围内的哈希值进行重建,使其分布更均匀,从而提高查询效率。相比LSB,LayerLSB索引在数据分布方面变得更有针对性,并构建了多层结构,与简单的重新哈希方法相比,多层方法会通过仔细选择组数和哈希函数来保证搜索质量。实验结果表明,在达到相同查询精度的情况下,查询成本最多可降低为原来的44.6%。

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

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

NTFS目录下索引B+树结构动态解析

为开发直接操作新技术文件系统(NTFS)的程序,并解决NTFS方面开发的技术难题,对磁盘上的具体目录索引B+树结构进行了分析。由于NTFS大目录在磁盘上的存储结构与主文件表和索引缓冲区大小相关,提出了三级大目录的概念,并在此基础上总结了相关文件操作下目录结构的动态变化规律。程序运行结果表明,该分析有效可行,有利于深入了解NTFS文件系统的结构。

B+树索引机制的研究及优化

当数据庞杂时,B+树索引在查找效率和空间利用率方面还存在不足。针对该问题提出一种改进的B+树结构,首先通过调整叶子节点与非叶子节点的数量关系,以降低树的深度;然后优化原插入算法,在分裂节点前进行平衡处理(BP),以提高树的空间利用率。经实验,改进后的B+树与传统B+树相比,在查找效率和空间利用率上分别提高了10%和6%,证明对B+树的改进具有可行性。

一种基于B+树的混合索引结构

针对文件中存在字符属性和数值属性特点的数据,提出一种基于B+树的2层混合索引结构。在索引创建过程中,将文件中的数据根据其类型进行分类,第1层是为数据属性建立B+树索引结构,第2层是根据不同的数据类型建立不同的索引结构。实验结果表明,该索引结构能实现跨数据范围的检索,提高索引的创建速度和空间利用率。

基于B＋树的数据索引存储

针对传统索引算法在数字数据索引应用中存在的索引建立时间开销较大问题,提出一种将B+树理论和算法应用于索引的设计方案.在对B+树索引基础上,建立了索引存储模型,结合位图存储方式将B+树节点存储在存储介质上,实现索引存储.实验结果表明,使用B+树,可按路径读取,节省了建立索引时间,同时提高了B+树的稳定性,在B+树节点存储的情况下访问键值信息,索引速度得到较大提升.

NTFS B+树大目录结构动态解析

为了分析新技术文件系统(NTFS)管理大目录的结构及变化规律,研究了NTFS文件系统生成大目录的条件、基本结构。动态跟踪一个大目录下删除和创建一个文件时发生的变化,对频繁变动的大目录可能生成的0X20属性进行深入的分析,给出了改进三层大目录MFT结构的方案,并设计实验进行验证。研究结果可作为在非Windows操作系统甚至无操作系统环境下进行NTFS分区操作的重要基础。

XML数据B树存储索引研究

XML正逐渐成为WWW数据表示和交换的标准,如何有效实现对于XML数据的存储、查询及更新等操作是XML相关技术研究中的一个重要领域。论文首先提及了几种对XML文档的编码机制;然后给出了改进的扩展编码方式,使用改进的B+树构造算法存储XML文档并对其进行查询、更新等操作,分析了执行效率;最后对系统的可扩展性进行了分析。

一种大数据流内存B+树构建方法

面向具有时间维度的大数据流,基于二级B+树索引结构,提出了一种高效的面向时间窗口、采用批量装载技术的内存B+树构建方法。该方法对时间窗口进行分片,通过分离出可以并行处理的操作来加速构建过程,将排序操作与数据流接收并行,B+树骨架的构建与排序并行;采用基于排序的批量装载技术以及优化的构建顺序,能够避免多线程之间不必要的加锁、同步开销,有效提高构建效率。提出的多次微批量排序单次批量装载(MBSortSBLoad)B+树构建方法的构建速度快,能承载的最大流速大。实验验证了所提方法的有效性。

多维索引hB树的改进方法——hB*树

本文在ｈＢ树基础上提出多属性索引方法——ｈＢ＊树．ｈＢ＊树索引结点溢出时先寻求避免分裂，以期得到较好的空间利用率；通过避免和消除多父结点，使ｈＢ＊树成为严格的树形结构．本文表明ｈＢ＊树提高了空间利用率，树形化的代价也不高．

基于B+树的发布/订阅并行匹配算法

现有的消息匹配算法不能很好地满足大规模分布式发布/订阅系统中海量数据的有效分发。为此,提出一种高效的发布/订阅并行匹配算法。采用B+树的存储结构,订阅消息按属性-值进行空间划分,建立多级索引订阅属性树,消息匹配采用改进的B+树查询方法,结合计数的思想实现快速消息匹配。实验结果表明,该算法在大规模分布式发布/订阅系统中,消息匹配时间短,订阅匹配树生成迅速,匹配效果更好。

基于B^+树的索引字段加密

针对索引字段加密难的问题,提出一种基于B+树的索引字段加密处理技术。该技术采用DBMS内部加密机制,选取在页/段映射到块时使用加密组件对索引字段进行加密,它能够使加密后的索引仍然保持有序,不会失去索引的快速查询功能。为了进一步保证索引字段本身的安全性,对索引按结点实施加密。实验中,模拟Postgresql中B+树的构造方法,研究基于B+树的加密索引字段的查询性能,并在页结点数和B+树深度参数变化时,对分结点加密的查询性能进行测试。研究结果表明:基于B+树的索引字段加密的查询速度虽然比明文查询速度下降20%左右,但采用分结点加密方式能够有效地减少解密代价,避免索引字段加密对查询性能产生较大影响。

基于改进B+树索引的结构连接算法

基本的结构连接是XML数据库查询处理的一个核心操作。Stack_Tree_Desc_B+算法能够有效地跳过不参加连接的后代,但跳过祖先的能力不强。通过对B+树叶子结点的每一项增加了parent和nextNeighbour指针,该文提出了一种改进算法Stack_Tree_Desc_B+_pn。改进算法不但具有较强的跳过后代的能力,而且具有较强的跳过祖先的能力。实验表明Stack_Tree_Desc_B+_pn算法可以有效地减少I/O次数,具有更高的性能。

一种基于Trie树和扩展B树的RFID标签编码过滤方法研究

面向EPC模式(EPC Pattern)的标签编码过滤是RFID中间件的主要功能之一.为提高过滤效率,本文给出了一种基于trie树和扩展B树相结合的标签编码过滤方法.通过分析标签编码和EPC模式的结构特征,将系统中大量的EPC模式构造成一个层次查找结构,对于EPC模式中的常规编码段采用trie树表达,对于区间形式采用扩展B树表达.查找过程按照编码段由高至低依次进行,并采用了基于位向量集合的优化方法.实验表明标签编码过滤效率受EPC模式数量变化的影响较小,能够有效降低向上层应用传输数据的延迟.

B+树在数据库索引中的应用

索引是数据库中建立记录间有规律排序的主要方式,它可以显著提高文件的操作速度。当数据库中记录的数目和数据量很大的时候,顺序查找速度会明显下降。为了提高查找速度,必须对文件建立索引。数据库索引的设计与实现有几种方法,主要阐述了使用B+树实现索引的方法。通过对B+树定义及算法的描述,可以看到使用B+树能够方便、有效的建立数据库的索引,并且能够有效减少查找时磁盘的I/O次数,提高数据查找的效率。

一种基于B+树的RFID抗冲突算法

针对二进制树形算法冲突集合分裂速度慢、标签分裂不均匀问题,提出一种基于B+树的RFID抗冲突算法.本算法将冲突集合分裂成一个3阶的B+树,即将每次发生冲突的集合分裂成3个子集,从而加快冲突集合的分裂速度,冲突集合相当于B+树的中间节点,每个子集分别对应于一个关键码,叶子节点或只包含一个标签或为一个空集合.为了防止集合分裂的不均匀,引入合适的hash函数,使集合均匀分裂.仿真实验表明,B+算法减少了标签冲突的发生,缩短了标签识别延时,提高了识别性能.