学习索引研究综述

大数据时代数据呈爆发式增长，传统索引结构难以处理庞大复杂的数据，为解决这一问题，学习索引应运而生，并成为当前数据库领域的研究热点之一。学习索引利用机器学习模型进行索引构建，通过对数据和物理位置之间的关系进行训练和学习得到学习模型，掌握二者之间的分布特点和规律，从而实现对传统索引的改进和优化。大量实验表明，与传统索引相比，学习索引可以适应大规模数据集，提供更好的搜索性能，具有更低的空间要求。文中详细介绍了学习索引的应用背景，梳理了现有的学习索引模型；根据数据类型的不同，将学习索引分为一维和多维两种类别，并对每种类别中学习索引模型的优缺点和可以支持的查询进行了详细的介绍和分析；最后对学习索引的未来研究方向进行了展望，以期为相关研究提供参考。     

一种混合模式的智能卡DBMS存储模型研究

智能卡DBMS是实现个人数据管理的重要基础技术之一。本文基于EEPROM和FLASH两种存储,提出了一种混合模式的智能卡DBMS存储模型。该存储模型充分利用了FLASH和EEPROM两种非易失性存储器的特性,通过把读写粒度低或者操作频繁的删除位、伪记录、引用计数器和索引链存储在EEPROM中,而把绝大部分数据存储在FLASH中,从而实现了表、域和索引的存储性能优化。最后通过对无排序要求的记录追加算法的分析,验证了该存储模型在性能上的提升。     

海量小文件系统的可移植操作系统接口兼容技术

基于Hadoop分布式文件系统（HDFS）研发的海量小文件系统（SMDFS）遗留了HDFS不兼容可移植操作系统接口（POSIX）约束的问题,为解决SMDFS的这一问题,提出基于本地缓存的POSIX兼容技术和基于数据暂存区的元数据高效管理技术。首先,通过设置数据暂存区来实现读写模式文件流的重定向,然后建立异步线程池模型,实现数据暂存区镜像文件的同步,从而完成用户层到存储层的所有POSIX相关的文件操作。此外,借助跳表结构的元数据缓存实现List目录等元数据操作效率优化。测试表明,相较于HDFS的Linux客户端,基于技术成果实现的SMDFS3.0的随机读性能有10倍以上的性能提升,顺序读和顺序写性能有约3~4倍的提升,随机写性能可以达到本地文件系统的20%,基于目录的元数据缓存的设计使目录的List操作效率提升近10倍。但是,由于用户空间文件系统（FUSE）挂载的客户端会引入额外的内核态和用户态切换等带来的开销,因此SMDFS3.0的Linux客户端相对于系统的Java接口会有大约50%的性能损耗。     

基于云平台的企业远程办公文件分布式存储方法

为提高数据的读写性能,设计基于云平台的企业远程办公文件分布式存储方法。总体架构由计算层、数据接入层、存储层、数据聚集层构成。存储层由Hadoop集群构成,各集群由NameNode管理;计算层与数据接入层可以实现数据的持久化存储;数据聚集层采用一致性多副本哈希存储算法作为数据聚集算法。通过搭建虚拟化云平台统一管理多个服务器,创建主机虚拟集群。设计文件加解密过滤器进行数据加解密。设计随机化数据冗余算法进行数据冗余。测试结果表明设计方法的集群负载情况良好,读、写带宽最高达到3 798 bps和3 912 bps,读、写速率最高达到3 298字节/s和3 258字节/s。     

一种结构化数据缓存方法

针对现有报表缓存方法在内存消耗和访问速度上相冲突的问题,提出一种结构化数据缓存方法,把具有行列结构的报表数据分块存储到文件中。以文件形式存储的数据被划分为索引区和数据区,通过数据分块算法和写操作将报表数据缓存入文件。在读取报表数据时根据索引区可以直接定位到所在的块,在块中快速查找所需要的数据,从而在内存消耗和访问速度上达到优化。     

RLPI索引:一种处理连续不确定XML索引

针对目前连续不确定XML数据的概率阈值范围查询,提出一种新的包含路径索引和值索引的RLPI(Reverse Label Probabilistic Index)索引。RLPI路径索引以逆序标签路径作为索引项,通过逆序标签路径可区分不同路径上的同名节点,更具针对性地定位所需节点。RLPI值索引借鉴U树的思想,通过提前计算并存储叶子节点的相关信息,以减少查询中需处理的元素数目,并且其对满足任意连续pdf(probability density function)的不确定数据均适用。理论分析和实验结果表明,RLPI索引技术有效地提高了查询处理的性能。     

ATC系统中高速内存缓存的设计与实现

由于空中交通管制系统在航空领域里的特殊应用,系统中部分数据实时性强,并且不需要长期存储,针对这一存储需求设计并实现了基于高速内存缓存的数据存储模型.模型基于key-value的内存池的内存管理方法,采用预申请和分组方式管理内存.通过实验分析比较了T数索引和哈希表索引的优点和适用范围,最终选择T树索引作为模型的索引数据结构.实验结果表明,该模型极大的提高了系统对该类数据的存取能力和系统性能.     

非易失性内存友好的线性哈希索引——NVM-LH

非易失性内存（NVM）因其大容量、持久化、按位存取和读延迟低等特性而受到人们的关注,但它同时也具有写次数有限、读写速度不均衡等缺点。针对传统线性哈希索引直接在NVM上实现时会导致大量的随机写操作这一问题,提出了一种新的NVM友好的线性哈希索引NVM-LH。NVM-LH通过存储数据时的缓存行对齐实现了缓存友好性,同时提出了无日志的数据一致性保证策略。此外,NVM-LH还通过优化分裂和删除操作来减少NVM写操作。实验结果表明,NVM-LH在空间利用率上比CCEH高30%,在NVM写次数上比CCEH减少了15%左右,表现了更好的NVM友好性。     

基于大批量训练和正交正则化的跨模态哈希方法

基于深度学习的跨模态哈希方法都使用小批量训练方式来训练模型,然而小批量方式在每次更新参数时获取样本数量有限,不能得到很好的梯度,影响最终训练的模型检索性能。针对此问题,提出了一个新的跨模态哈希方法。该方法使用大批量方式进行训练,并引入正交正则化来增加大批量训练的稳定性;同时考虑了哈希码的离散性,将哈希码与特征之间的距离加入到目标函数中,使得哈希码能够更加真实地表示数据。在两个广泛使用的跨模态检索数据集上的实验表明,该方法比现有的几种哈希方法具有更好的性能。     

路网时窗排序的回归模型树轨迹索引

最近,通过学习型索引取代传统索引以减少索引大小和提高查询效率受到广泛关注.轨迹点在路网和时间维度的连续性难以刻画,数据分布倾斜普遍存在,现存的学习型索引不能有效地支持其查询.提出一种基于路网时窗排序的回归模型树,以支持点和范围查询,含数据排序和模型训练两个阶段：首先,结合希尔伯特曲线和模拟退火寻找保持道路临近性的路段排序,进而采用两层划分获取轨迹点的一维排序,保证时空近邻点排序后彼此靠近;其次,引入回归模型树映射轨迹点和存储位置,提出批量加载和周期更新两种训练模式.真实和模拟数据集上的实验表明,在保证和传统索引可比的查询性能前提下,大幅度降低索引大小,有效地支持以读为主的历史轨迹数据查询.     

UStore：面向新型硬件的统一存储系统

数据规模的爆发式增长使得分布式存储广泛应用，长期以来分布式存储直接使用本地文件系统访问本地存储资源，随着高性能NVMe SSD、持久内存（persistent memory,PMEM）、异构加速设备的出现，本地文件系统难以发挥新型器件的特性和性能优势.现有很多研究针对SSD或者PMEM的硬件特性在软件层面进行优化和改进.然而，这些工作兼容性和扩展性差，不能灵活适配硬件环境变化，缺乏面向新型硬件的统一解决方案.提出了一种兼容多种存储介质的统一存储系统UStore，可根据业务场景灵活选择存储介质，并针对PMEM、KVS加速卡、NVMe SSD等典型硬件进行组合设计优化，充分利用其硬件特性，满足多层次的业务需求；通过一种与物理存储介质形态解耦的元数据设计，使其适应不同硬件的性能和原子更新能力差异，实现灵活的元数据存储策略；通过高效的数据管理机制和更新策略，实现无日志的数据原子写保证，消除了现有系统的写放大以及性能抖动等问题.实验结果表明，相比于BlueStore,UStore的4KB随机读性能提升了3.2倍，4KB随机写提高了8.2倍，3种典型硬件组合下UStore表现出与之相匹配的数据访问...     

基于全同态加密算法的高校数据安全存储方法

目前，高校数据安全存储结构多为单一模式，存储效率较低，导致数据安全存储写入速率下降，为此提出对基于全同态加密算法的高校数据安全存储方法的设计与验证分析。采用多层级的方式，设计多层级数据存储加密结构，从而构建全同态加密测算数据存储模型，采用HBase并发索引加密实现数据安全存储。最终测试结果表明：设计的全同态加密测算数据安全存储测试组最终得出的数据安全存储写入速率可以达到6.5MB/s以上，说明此种数据存储方法的针对性和稳定性较强，存储速度更快。     

列存储数据库中压缩位图索引技术

为提高压缩码的利用率,提出一种适用于列存储数据库的压缩位图索引技术。定义反转、合并等操作,将所有计算的输入值与输出值格式化为位向量形式。通过活跃度衡量索引中位向量的复杂度,并对压缩位向量进行直接计算,优化where子句和group by子句在查询执行过程中的数据提取。在SSB数据集上的实验结果证明,该技术能提高29.7%~38.9%的压缩位图索引性能。     

一种基于数据访问流的数据库索引优化方法

提出了一种基于数据访问流进行索引优化的方法,该方法通过集成业务流程模型与数据模型,抽取了流程活动中包含的数据访问操作和流程的控制结构形成数据访问流,分析了数据访问流中数据访问操作的频度,为频繁数据访问操作所对应的数据项创建索引,达到改善数据访问性能的目的。实验结果表明,该方法提高了数据查询的速度。     

TVDSM:支持透明计算的虚拟磁盘存储模型

为了解决在透明计算环境下,现有虚拟磁盘镜像存储存在多用户虚拟磁盘数据冗余过度的问题,基于写时重定向(redirect-on-write,ROW)思想设计了一种树状虚拟磁盘存储模型(tree virtual disk storage model,TVDSM)。该模型将虚拟磁盘中数据资源按共享度划分成多个层级,不同终端用户共享位于上层的系统资源以及应用软件资源,只在底层存储自身改写的数据,从而减少了虚拟磁盘存储系统中的冗余数据。同时基于位图索引技术设计并实现了一种树状的虚拟磁盘存储结构,该结构不仅能够很好地支持虚拟磁盘存储模型,而且支持将写重定向和查询定位操作以不同粒度分开实现,使得系统能够在较小共享粒度下获得较高的数据查询效率。     

关系数据库更新查询的优化技术

大型数据库的数据更新常常因为响应速度而深受影响,因此对于执行更新操作的UPDATE语句要进行优化,合理书写条件语句,并要结合索引的灵活使用,最终达到提高系统的响应速度,优化系统性能的目的.     

基于HBase的气象地面分钟数据分布式存储系统

针对气象地面分钟数据要素多样、信息量大、产生频次高等特点,传统的关系型数据库系统在存储和管理数据上出现负载饱满、读写性能不理想等问题。结合对分布式数据库HBase的存储模型的研究,行主键(row key)采用时间加站号的方式设计了气象分钟数据存储结构模型,实现对海量气象数据的分布式存储和元信息管理。对HBase的唯一索引在面对气象业务的复杂查询用例时响应时间过长的问题,使用搜索引擎solr提供的API接口并参考气象业务中的查询用例对相关字段建立辅助索引,来满足业务检索时效。实验结果表明,该系统具有很好的存储能力和检索效率,入库效率最高可达每秒34000条,并且在常规查询用例的结果返回时效达到毫秒级,能够满足大规模气象数据在业务应用中对存储和查询时效的性能要求。     

连续数据存储中面向RAID5的写操作优化设计

针对连续数据存储应用,如视频监控、连续数据保护(CDP)、虚拟磁带库(VTL)等,提出一种面向RAID5的写操作优化方法:首先进行基于区间映射(area mapping)的地址转换(AT),把非连续的I/O请求虚拟地址转换为连续的物理地址,以实现对磁盘阵列的连续写;然后,在缓冲区内保存应用程序发出的写数据块,并构造一个与RAID5的完整条带长度相等的对齐数据决,对齐数据块在RAID5上恰好占满整个条带,再发送给RAID5,以实现对RAID5的完全写.这样写入的数据块恰好占满RAID5的整个条带,不仅避免了因生成校验数据而产生重构写、读改写等额外I/O开销,而且数据块的连续写入有效降低了磁头的寻道时间,提高了RAID5的吞吐能力.实验表明,该写优化方法在有限降低RAID5读性能的同时,可大幅提高RAID5的写性能,在80％连续的负载下,使RAID5的数据传输率接近其最大值.在连续数据存储中该方法同样适用于RAID4和RAID6.     

基于SSD SMR混合存储的LSM树键值存储系统的性能优化

大数据对存储系统的可扩展性、性能和成本等方面提出了更高的要求。瓦记录(Shingled Magnetic Recor-ding,SMR)硬盘由于存储密度高、价格便宜,正逐步被广泛应用于大数据存储系统。但是,SMR硬盘的随机写性能较差,与快速的基于闪存的固态硬盘(Solid State Drive,SSD)一起构成混合存储时可以显著提升性能。同时,基于写优化的日志结构合并(Log-Structured Merge,LSM)树的键值存储已被广泛应用于许多NoSQL系统,如BigTable,Cassandra和HBase等。因此,如何基于新型的SSD-SMR混合存储构建出高性能的LSM树键值存储系统是一个具有很大研究价值的问题。首先建立基于SSD-SMR混合存储的LSM树键值系统的性能模型,然后针对SSD和SMR的硬件特征以及LSM树键值存储的软件特点,设计了一套面向SSD-SMR混合存储进行性能优化的LSM树键值存储系统,并基于LevelDB实现了该系统。在仅仅使用0.4%～2%空间的SSD的情况下,所提方法可以使SSD-SMR混合存储方案比普通磁盘方案的随机写性能提高20%,随机读性能提高5倍。     

基于SSD的云存储主服务器元数据管理研究

为了提高对云存储系统主服务器中元数据的有效管理,在数据密集型应用中,考虑到读多写少的特点符合网络中各种应用的基本特征,而文件存储的元数据往往小于4KB,我们提出一种基于SSD的针对云存储系统主服务器的元数据管理策略,建立了一套相对独立的存储服务器目录路径索引机制,此策略将元数据的管理分为两个部分：目录路径索引和文件名,充分利用SSD的低功耗与优越读性能。测试表明,基于SSD的云存储主主服务器元数据管理策略可以明显改善系统响应时间,降低延迟,提升云存储系统的性能。