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倍。

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

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

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.

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

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

SEQUENTIAL RETRIEVAL OF B-TREES AND A FILE STRUCTURE WITH A DENSE B-TREE INDEX

A simple fast method is given for sequentially retrieving all the records in a B tree. A file structure for database is proposed. The records in its primary data file are sorted according to the key order. A B tree is used as its dense index. It is easy to insert, delete or search a record, and it is also convenient to retrieve records in the sequential order of the keys. The merits and efficiencies of these methods or structures are discussed in detail.

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

小议如何删除数据结构B-tree的关键字

数据结构B-Tree在文件系统管理中经常用到,是一种平衡的多路查找树。作为一种有效的存取和索引记录的数据结构,它用简单的记录管理和B-Tree的索引引擎来浏览记录、修改文件和索引,使用起来非常简单快捷。这里,重点讨论了在B-Tree中删除关键字的实现思想。

面向科技文献多维语义组织的混合倒排索引构建方法

[目的/意义]为满足科研人员对科技文献内部细粒度语义信息进行高效查询的迫切需求,前期研究提出了面向科技文献的多维语义索引体系,然而基于HashMap的常见倒排索引会导致查询效率低下。本文旨在通过面向不同维度语义特征建立混合倒排索引,以改进语义查询性能。[方法/过程]本文以Treap、B+树等多种数据结构探索适合不同语义维度的倒排索引构建方法,并将其组合形成多种适用于科技文献多维语义组织的混合倒排索引构建方法,并通过对比实验,在排序查询和布尔查询条件下分析验证不同类型倒排索引构建方法的查询性能。[结果/结论]实验结果表明,组合形成的8种混合倒排索引构建方法中,表2所示的C3(HHHB)被证明在排序查询条件下具有最高的效率,而C4(TTTB)则在布尔查询条件下被证明最为高效。本文的方法能有效解决单一索引结构导致的查询效率问题。

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

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

基于B-树的分布式群组密钥管理机制

提出把B-树引入到管理机制中,并给出了加入协议和离开协议的形式化描述。B-树方案在通信开销和计算开销方面优于二叉树方案,并且二者的差距随着B-树阶数的增大和群组成员数目的增加而明显加大。在安全性方面,B-树方案能够抵抗联合攻击。

一种用B-树的最佳阶数组织内存索引文件的方法

根据当前和今后计算机内存配置情况的变化，本文提出了一种将全部索引文件放入内存，并根据内存索引文件区别于外存索引文件的特点选择一个最佳阶数ｍ来构造用于组织索引文件的Ｂ－树，使该Ｂ－树的查询和插入效率达到近似最佳的方法，并给出了相应的分析和证明。

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

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

B-树的性能分析及其在数据搜索中的应用

在数据文件中,数据搜索可用顺序查找等方法实现,但是这些方法速度较慢。这里介绍了多路查找树——B-树,给出其定义和性能分析,并且对它在数据搜索中的应用进行了举例分析。

B-树在NTFS索引目录管理中的应用研究

目前国内一些有关NTFS文件系统的书籍或杂志认为NTFS对索引目录的管理是采用B+树结构,而只有少量书籍中认为NTFS对索引目录的管理是采用B-树结构。针对这种争议,以Windows7操作系统为平台,以NTFS文件系统和文件目录为研究分析对象,用WinHex磁盘编辑为分析工具,对NTFS文件系统中元文件$MFT文件夹记录的90H属性、A0H属性和B0H属性进行分析。以B-树的定义为衡量标准,对NTFS文件系统索引目录中的文件进行查找、删除和插入操作,来观察NTFS文件系统索引目录的结构变化。实验结果表明,NTFS索引目录基本符合B-树的定义。NTFS文件系统对索引目录的管理是采用B-树结构,但并非是标准的B-树结构。

NTFS索引目录B-树结构解析及其应用

针对一些有关NTFS文件系统的书籍和杂志中认为NTFS文件系统对索引目录的管理是采用B+树结构,通过对NTFS文件系统元文件$MFT文件夹记录的90H属性、A0H属性和B0H属性以及索引结点结构的分析,以实验的方式对索引文件进行查找、删除和插入运算来观察NTFS索引目录结构变化.实验结果表明:NTFS文件系统对索引目录的管理是采用B-树结构,但并非是一棵标准的B-树.

B-树/B+树的批量插入算法

本文对传统的B -树 /B +树插入算法进行改进 ,提出了B -树 /B +树的批量插入的算法 ,在理论上估计了该算法的复杂度 ,并进行了比较实验 .实验结果表明 :本算法在对大批量的关键字建立索引时 ,大大提高了B -树 /B +树的插入效率 。

中国部分鸡种B-G基因SNP和Indel

鸡的MHC基因家族中B-G基因与鸡抗病性有关,通过研究与抗病有关的B-G基因的多态性可以从根本上提高鸡抵抗疾病的能力,进而为抗病育种奠定基础。试验对25个鸡种基因组DNA进行目标捕获测序,以NCBI中Gallus gallus的B-G基因序列为参考,利用MEGA6软件进行不同鸡种基因序列比对,分析B-G基因外显子和内含子中的SNPs和Indels以及氨基酸的变化,最后制作进化树。结果表明,25个鸡种中外显子存在8个SNPs、19个Indels,内含子有67个SNPs、327个Indels;同时氨基酸序列也呈现出相应的多态性,中国地方鸡种也表现出丰富的遗传多样性。来航鸡、仙居鸡、隐性白羽鸡的B-G基因存在丰富的多态性;来航鸡在进化树上单独为一类,藏鸡、文昌鸡由于地理位置因素也分别为单独一类;现代肉鸡中罗斯与隐性白羽鸡聚为一类;不同类型的中国地方鸡种间同源性较小。中国地方鸡种B-G基因存在多源性进化以及丰富的遗传多样性,进而产生抗病性差异。

线粒体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-树分析与应用

介绍了动态索引数据结构─B_树 ,着重论述了B_树结构 ,B_树性能分析 ,B_树运算和应用 。