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

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

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

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

三阶B树的构造与应用

本文给出两种构造三阶Ｂ树的算法，证明算法的时间复杂性，并给出用三阶Ｂ树实现热力公司的数据管理实例。

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

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

基于改进B树的多层次仿真系统搜索算法

针对多层次分布式仿真系统中仿真成员较多时系统搜索效率低下的问题,研究分析仿真成员的多层级树状结构关系,给出多层次仿真系统常用搜索方法的缺陷。提出利用分色的策略来改进B树搜索算法,将B搜索树的低网络通信和分色查找的高效率结合实现了多仿真成员的快速搜索和网络资源的低消耗。结果表明,该方法可以实现对多层次仿真系统仿真成员的快速搜索和通信网络资源的低消耗,保证了多层次分布式仿真系统的实时性和仿真网络的稳定性。

B树分析

本文将描述Ｂ树，解释和分析查找、插入和删除过程，并对Ｂ树运算进行讨论，还将介绍Ｂ树的几种变型。

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

XML正逐渐成为 WWW数据表示和交换的标准 ,如何有效实现对于 XML数据的存储、查询及更新等操作是 XML 相关技术研究中的一个重要领域。本文首先简要介绍了我们的基于模式匹配的 XML 数据库系统 (DISXDBS)组成 ;然后研究了如何实现用 B树存储 XML 文档以及对其进行查询、更新等操作 ;最后与目前存在的几种 XML 文档的存储策略进行比较。

嵌入式数据库SQLite中B树的研究

本文重点描述了开源嵌入式数据库SQLite对数据的组织方法和其中B树页的结构,并对利用SQLite建立的数据库文件进行了的设计。在此基础之上,进一步对SQLite中实现此部分的程序代码进行了更深入的分析。最后利用SQLite中提供的接口函数完成了对红-黑树的操作程序,实现了在数据库中对B树的应用,完成了对该数据库的优化。

一种基于范围表示B树的大容量IPv6路由查表算法

IPv6具有巨大的地址空间,未来要面对的将会是海量IPv6路由表,而且128位的IPv6地址比IPv4需要更多的访存数。算法针对IPv6路由查找问题中的这两个难点,提出利用B树高度较低的优良性质,将前缀转化为范围表保存在B树中,并在结点内部利用分段范围比较树算法来减少访存次数和空间耗费。理论分析和实验表明,该算法能够以很好的性能支持IPv6海量路由表的查找。

从编程和性能看B树和B+树

B树和B+树被广泛使用于各种领域,关于它们的原理已经有大量文章文献讨论研究,但是关于具体实施少有提及。从编程与性能的角度分析了B树和B+树的区别,探讨了两者从实现方法到性能的差异。

类属B树方法在GIS系统中的应用

1引言 自80年代以来,效据库新的应用领域不断出现.这些新兴的应用领域如:计算机集成制造系统CIMS、多媒体系统、地理信息系统(GIS)等,要求支撑的数据库管理系统(DBMS)能存储和处理各种复杂对象;支持新的数据类型和操作;支持动态模式修改;存储和处理四维环境下的信息{x,y,z,t};并能提供基于四维关系上的查询功能[5].

多B树在全文库中的实现

在全文数据库发展过程中，人们一直在寻求一种好的索引方式以满足巨量数据信息管理的需要.本文论述了全文库中索引技术发展现状，并针对其在索引维护方面存在的不足，分析一种基于B＋树的新数据结构--多B树结构在全文索引技术方面的优势、实现的可行性以及发展前景.

B^n树的空间和效率分析——一种新型而实用的扩展B树

B树现在已经成为数据处理中最主要的文件组织形式、它以其空间和效率方面的优势、在数据库系统的索引技术中占住了统治地位、目前、它仍在不断改进和发展,本文简述了各类B树特点和优劣,并提出了一种新型的B树——B^n树,它在空间和效率方面较之传统的B树都有相当的改进,并大大减少了分裂和合并的概率,当然这是要付出一定的代价为条件的,文中给出了一个成本及效益的模型。

XML数据B树存储索引研究

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

基于B树的否定选择算法及其应用

针对传统的方法在带钢表面缺陷图像检测中存在的问题,提出了基于B树的否定选择算法.根据影响成熟检测器生成的因素,通过低频和高频变异生成初始检测器集合,改变检测器的表示方式,以数值型的检测数代替二进制字符串形式的检测器,提取自体数值、检测数值和待检数值,使用B树建立索引并构建自体信息树和检测信息树,来实现其质量检测.实验表明,该方法明显优于传统的图像检测算法,提高了检测效率.

基于改进B树索引的DHT多维范围查询

DHT在分布式网络环境中的应用越来越来得到重视,著名的算法有Chord、CAN、Pastry、Tapestry,以及Kademlia,它们使用一致性哈希的方法,虽然保证查询的效率和准确性,但是破坏原有数据的组织结构,使得DHT只支持精确查找,不支持复杂查询。根据实际,提出一种基于B树的范围查询,将改进后的B树索引分布式存储到网络节点中,从而在DHT之上建立的数据索引。在不破坏DHT结构的基础之上支持范围查询功能,提出如何解决多维范围查询的方法。

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

本文重点介绍数据结构中经典的树（B树）结构在数据库索引中的经典应用，其中涉及几种数据库中对此支持的细微不同，以期比较完整地描述实现原理。作者认为，搞清实际需求，对备选方案的原理尽可能深入全面的了解会更有利于我们的决策。

基于SPB树的公路网络最短路径查询

针对在线地图服务和路程安排等领域中的点对点最短路径查询方法,提出一种新的数据结构——最短路径B+树(SPB树),以有效存储预先计算好的点空间信息和与之对应的最短路径信息。实验结果证明,利用SPB树在公路网络上进行最短路径查询比经典的Dijkstra算法最高快出3个数量级。

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

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

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

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