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

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

基于B^(*)-树的连续微流控生物芯片流层物理设计方法

作为连续微流控生物芯片设计中的关键步骤,流层物理设计是一个复杂的多目标优化问题,传统方法通常将其分为布局和布线2个阶段。为弥补这2个阶段之间的交互不足,提出了一种基于B^(*)-树的流层物理设计方法,以提高解的质量和求解效率。在布局阶段,采用Memetic算法更高效地搜索解空间。在布线阶段,使用考虑通道顺序的基于协商的算法,同时将布线信息反馈给布局阶段,以调整布局并减少拥挤区域和通道交叉。实验结果表明,与现有算法相比,所提算法在芯片面积、通道总长度以及通道交叉数量等方面取得了更优的效果。

ZB^(+)-tree:一种ZNS SSD感知的新型索引结构

ZNS SSD是近年来提出的一种新型固态硬盘(solid state drive,SSD),它以分区(Zone)的方式管理和存取SSD内的数据.相比于传统SSD,ZNS SSD可以有效提升SSD的读写吞吐,降低写放大,减少SSD的预留空间.但是,ZNS SSD要求Zone内必须采用顺序写模式,并且Zone上的空间分配、垃圾回收等任务都需要用户自行控制.ZNS SSD的这些特性对于传统数据库系统的存储管理、索引、缓存等技术均提出了新的挑战.针对如何使传统的B^(+)-tree索引结构适配ZNS SSD的问题,提出了一种ZNS SSD感知的新型索引结构——ZB^(+)-tree(ZNS-aware B^(+)-tree).ZB^(+)-tree是目前已知的首个ZNS SSD感知的索引,它以B^(+)-tree为基础,利用ZNS SSD内部支持少量随机写的常规Zone(conventional zone,Cov-Zone)和只支持顺序写的顺序Zone(sequential zone,Seq-Zone),通过常规Zone来吸收对ZNS SSD的随机写操作.ZB^(+)-tree将索引节点分散存储在常规Zone和顺序Zone中,并为2种Zone内的节点分别设计了节点结构,使ZB^(+)-tree不仅能够吸收对索引的随机写操作,而且又可以保证顺序Zone内的顺序写要求.在实验中利用null_blk和libzbd模拟ZNS SSD设备,并将现有的CoW B^(+)-tree修改后作为对比索引.结果表明,ZB^(+)-tree在运行时间、空间利用率等多个指标上均优于CoW B^(+)-tree.

一种wandering B+tree问题解决方法

为了应对磁盘和固态硬盘随机写和顺序写性能差异较大的问题,文件系统和块存储系统通常采用日志结构(log-structured)技术将随机写转换为顺序写.因此,对于日志结构存储系统数据和元数据的修改都以异地写的方式执行.在日志结构存储系统中,B+tree常被用于管理元数据,这就会导致wandering B+tree问题,即树结点异地更新会导致树结构递归更新.目前,现有工作主要通过分离树结点的逻辑索引和物理地址,并使用额外的数据结构和物理设备空间存放树结点逻辑索引和物理地址的映射,从而避免递归更新树结构.但现有方法既引入额外空间开销,又存在额外物理设备空间非顺序写的问题.提出IBT B+tree,将树结点逻辑索引和物理地址均存放在树结构中.同时,基于IBT B+tree结构引入dirty链表设计,并提出了非递归更新的IBT B+tree下刷算法.IBT B+tree既解决了wandering B+tree问题,又不引入额外的数据结构和物理设备空间,消除了固定物理设备空间的非顺序写.分别实现IBT B+tree和基于F2FS中NAT设计的B+tree,在此基础上设计实现Monty-Dev块存储系统以评价2棵B+tree.实验表明,在HDD和SSD介质上,IBT B+tree在写放大和下刷效率方面均优于NAT B+tree.

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%.

Learned Index和B-Tree在不同分布数据上的性能对比及优化

Learned Index是一种通过训练模型来建立输入数据和存储位置之间映射关系的索引,它能学习到数据间分布的信息,而不同的数据分布将影响模型训练准确率和模型复杂度之间的平衡。为了探索Learned Index适用的场景,使用不同分布、不同数据量的数据对它和加以优化的可更新的自适应学习索引(ALEX)进行性能测试,并与B-Tree进行对比,最终发现Learned Index构建大批量数据的索引时间比B-Tree短,读操作性能、存储空间大小有明显的优势,但写操作性能较差,因此得出Learned Index更适用于大数据情景下的在线分析处理(OLAP)数据库,用于静态数据的存储和查询操作的结论。基于B-Tree的索引结构,对初版Learned Index的结构进行了优化和调整,最终使优化后Learned Index在大批量数据的读写操作性能上有明显提高,其中读操作最高达到原版Learned Index的2倍,写操作最高达到原版的3倍。

线粒体Cyt b基因在鲑科品种鉴定中的可靠性分析

为探究Cyt b基因在鲑科鱼类品种鉴定中的可靠性,本研究从GenBank数据库中下载9种鲑科鱼类品种的Cyt b基因序列共997条。以Cyt b全基因和文献报道的两组Cyt b基因短片段(359和200 bp)为研究对象,对其序列变异和分子系统进化树进行分析,并筛选鲑科鱼类品种的微型DNA条形码。结果表明,仅当选用200 bp片段时,银鲑的最大种内遗传距离大于最小种间遗传距离,不存在条形码间隙(barcode gap)。同时,根据分子系统进化树分析,同一品种在基于不同Cyt b基因片段的邻接树中均聚为单系,且每一个分支的结点置信度均大于70%。因此,Cyt b可以作为条形码基因用于鲑科鱼类品种鉴定。本研究筛选获得的微型DNA条形码对鲑科鱼类品种具有良好的特异性。

B^+-Tree的改进算法在可复用软构件库中的应用

文章通过对B+-Tree索引算法的改进,将其应用到可复用软构件库中。该改进算法继承了B+-Tree的优点,结合可复用软构件库的特点,将构件库多维数据索引转化为B+-Tree一维数据索引进行存储、查询。通过对比分析,证明了该构件库索引算法大大改进了构件库中构件的查找效率。

一种数据立方高效索引机制——CuboidTree

提出了一种高效的数据立方索引机制CuboidTree ,利用Z Order编码以保持同一数据小方内立方元组之间的多维空间邻近性 ,将数据立方查询归结为针对其中某个特定数据小方的查询 ,从而将同一数据小方中的立方元组聚簇在一起以加速响应数据立方查询 .对模拟数据和真实数据进行的实验表明 ,CuboidTree不仅可以明显地提高数据立方范围查询的性能 ,而且节省了存储空间 。

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

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

StringB-tree在软件复用中的应用研究

提出了将StringB-tree用于解决软件复用中的参数化样式匹配问题(parameterizedpatternmatching)。通过对参数化字符串做一个变换,使用StringB-tree这种特殊的数据结构可提高匹配效率。文章的重点有两部分,一个是介绍了StringB-tree这种特殊的数据结构的优点及其构建过程;另一个是讲怎样利用StringB-tree解决参数化样式匹配问题。

基于B^+-tree索引的多元时间序列相似查询

为提高多元时间序列相似查询执行效率,采用了基于距离索引结构的相似查询算法。利用主成分分析方法对多元时间序列数据降维并在此基础上进行聚类,以聚类质心为参考点,将各类变换到一维空间,利用B+-tree结构进行索引查询,找到与查询序列最相似的k个MTS序列。实验表明查询效率和准确性都有比较大的提高。

基于CB+-tree的时态XML索引动态更新方法

针对时态XML更新问题,使用了CB+-tree索引时态XML文档和文档添加冗余空间存储,借助时态信息索引、实体地址索引双重索引和文档冗余存储方式高效地实现文档的局部更新。实验结果表明,将实体时态信息和地址索引分离,并为文档添加冗余空间,减少了XML文档更新时间,其效率明显提高。

一种基于B^+-tree索引的有效相似查询算法

提出了一种多元时间序列相似查询算法.在距离索引结构相似查询算法的基础上,利用主成分分析方法对多元时间序列进行降维,并对主成分进行聚类,在聚类质心与各类之间的范数所构成的一维空间上,对聚类建立B+-tree索引结构,然后利用k近邻查询算法查找出与查询序列最相似的k个MTS序列.实验结果表明,文中算法的候选比率与查询时间明显低于Muse算法,且候选比率与查询时间受聚类个数影响不大,说明文中算法具有一定的优越性.

并行B^+-tree的存储结构及其操作

The techniques and methods for implementing parallel B+ -tree are firstpresented. Then, the parallel algorithms for data maintenance of B+ -tree, parallelalgorithms for maintaining schemes of the relations with parallel B+ - tree indices, and theparallel data operation algorithms based on the B+ -trees are propised. The proposedparallel B+ -trees and related parallel algorithms have been used in a parallel relationaldatabase system designed and implemented by the author. It is shown in practicethat the proposed parallel B+ -tree and algorithms are very efficient and very effective.

多核处理器支持的频繁访问B＋-Tree

传统B＋-Tree自顶向下访问模式不适应于频繁访问应用模式，面向多核处理器支持，提出了针对频繁访问的FAB＋-Tree（Frequent Access B＋-Tree）。在B＋-Tree的基础上增加了Hash辅助索引，使得访问B＋-Tree是可以直接定位到叶结点，并利用基于内存的直接访问表及位矢量列表提高更新性能。同时基于共享L2-Cache多核处理器，提出了基于流水线的FAB＋-Tree多线程访问模块，并优化了该模块的共享Cache访问性能。基于开源数据库Ingres实现了FAB＋-Tree和多线程访问模块，实验结果表明B＋-Tree的访问性能得到显著提高。

优化的XML查询匹配:基于B^+-Tree索引的包含段的结构化联接算法

高效的结构化联接方法是XML查询的关键。本文提出一种新颖的结构化联接方法,使用了包含段结构化XML文档树,并且使用了B^+-Tree索引技术支持该新方法,从而在基于栈的结构化联接过程中得以忽略若干时空耗费,提高处理效率。

基于DPB^+-Tree的数据迁移策略研究

提出了一种适合于数据迁移、又能保证分布并行特性的树结构DPB+-Tree,讨论了基于DPB+-Tree的数据迁移策略,其中数据节点迁移采用分布式提交协议来保证原子性,索引重构通过对溢出链的hash重排来实现,迁移算法则通过设置负载系数的两个阈值来对负载倾斜进行判断。经模拟实验结果表明,该数据迁移策略能够有效改善系统的负载均衡和吞吐率特性。

基于CB+-tree的时态XML索引

针对时态查询与时间属性紧密相关的特点,利用时间区间作为改进后B+-tree的索引关键字建立索引,改进后的B+-tree命名为Changing B+-tree(CB+-tree)。实验证明,在CB+-tree上进行时态查询比B+-tree及基于DOM的XML文档的查询效率有所提高。

多核处理器中支持频繁访问的B^+-Tree

针对传统B+-Tree自顶向下访问模式的缺点,提出了支持频繁访问的FAB+-Tree(Frequent Access B+-Tree)。在B+-Tree的基础上增加了Hash辅助索引,使得访问B+-Tree时直接定位到叶结点,并利用基于内存的直接访问表及位矢量列表提高更新性能。同时基于共享Cache多核处理器,提出了基于流水线的FAB+-Tree多线程访问模块,并优化了该模块的共享Cache访问性能。在实验中,基于开源数据库INGRES实现了FAB+-Tree和多线程访问模块,实验结果表明B+-Tree的访问性能得到显著提高。