加密XML数据结构索引方案研究

充分利用XML数据库文档的树形结构特性,结合Dewey编码原理和B+树的索引特性,提出了一种基于B+树的加密XML结构索引和查询模型.在XML文档加密过程中,将XML加密数据与基于加密数据的B+树索引一起存储在服务器端,以便在服务器端完成对加密数据的结构索引.实验结果表明,此法提高了查询的效率,无需解密无关的加密数据,有效地实现了对加密XML数据的结构索引.     

LD_B~+树:闪存系统上一种DBMS索引结构

以往的研究大多针对文件系统,而DBMS存在更多细粒度的更新.本文综合考虑闪存自身的特点、设备种类繁多及不同闪存设备读写特性差别大等,提出了一种基于闪存的DBMS索引结构:LD_B+树.LD_B+树根据工作负载的读写特性动态地调节索引模式使之能够适应于不同种类的闪存设备.LD_B+树采用日志结构组织结点,通过结点转换表和日志缓冲区维护索引结构.模拟实验结果表明,不同闪存设备及工作负载下,LD_B+索引结构比B+树和日志型B+树(BFTL)具有6%-63%的性能提高.     

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

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

持久化内存文件系统的磨损攻击与防御机制

近来出现诸多以非易失性存储器（non-volatile memory,简称NVM）作为存储设备的新型持久化内存文件系统,充分发掘NVM的低延迟和可按字节寻址等优点,优化文件访问的I/O栈和一致性机制,极大提升文件系统的性能.然而,现有持久化内存文件系统都没有考虑NVM写耐受度低的缺陷,极易导致NVM被磨损穿（wear out）.针对NVM写耐受度低的缺点,探索多种利用基本文件操作对NVM造成磨损攻击的方式,并在真实持久化内存文件系统PMFS中以实验证明磨损攻击的严重性.为有效防御针对NVM的磨损攻击,提出了持久化内存文件系统磨损防御机制（persistent in-memory file system wear defense technique,简称PFWD）,包括索引节点元数据虚拟化技术、超级块迁移技术、文件数据页磨损均衡技术和文件索引结构迁移技术,保护文件系统中所有可能被磨损攻击利用的数据结构.实验结果证明所提出的PFWD技术能有效地防御病毒发动对NVM的磨损攻击,提高了存储系统的稳定性.     

一种基于网格与R树的多级混合索引

结合网格索引和R树索引的特点,提出了一种基于网格与R树的多级混合索引.该方案首先将矩形地理空间进行粗网格划分建立多级网格索引.然后针对每个小网格建立基于R树的空间索引.详细讨论了该索引的结构、建立算法、删除算法以及应用该索引的检索算法,并进行了算法分析.与网格索引和R树索引相比,该索引以略大的空间开销换取了更高的查找性能.     

一种面向动态连续查询的查询索引

针对当前面向连续查询的查询索引不适应查询动态变化的问题,提出一种能承受频繁更新的动态连续查询索引。为实现该索引,设计一种基于网格和树的索引结构,该索引结构继承了网格结构的高效更新性能的优点,并通过继承树的特性,克服网格结构高空间开销的问题。实验结果表明,该连续查询索引比基于网格的连续查询索引节省空间开销约一个数量级;比基于树的连续查询索引更新效率提高约70%,查询性能提高约25%。     

KDT树:一种多维空间数据索引结构

通过扩展KD树索引结构,提出了一种新的多维空间数据索引结构——KDT树,给出了数据结构和算法描述,并通过与当前流行的空间数据索引结构——R树的对比,对其性能进行了测试与评估。实验表明,作为一种主存索引结构,KDT树在时间效率方面明显优于R树,并且此种优势随着索引记录数量的增多而越加明显。此外,KDT树亦能较好地解决常规KD树在索引占据一定空间范围的空间对象(如:线、面、体等)时存在的问题。     

MSCR树：一种移动终端电子地图索引结构

现有空间数据索引结构并未同时考虑移动终端电子地图的多比例尺特性及嵌入式设备性能的限制,造成对大区域进行空间查询操作时装载开销过大。深入分析了多种空间索引结构的特点,提出一种新的空间索引结构——MSCR树索引结构,该结构将多级地图中的空间元素线性化,同时以压缩的方式存储空间元素外包矩形数据以提高数据读写效率。实验表明,MSCR树算法有效地提高了查询性能与空间利用率。     

面向新型非易失存储的文件系统研究综述

新型非易失存储(NVM)可字节寻址,具有近似内存的低延迟特性以及外存的非易失性,受限于软硬件技术成熟度,目前首先被用于外存.讨论了NVM用于持久性外存所面临的一系列问题,以及管理上的一些挑战;对现有的典型NVM文件系统及其主要特性进行了梳理.归纳起来,这些特性主要围绕降低一致性开销、降低软件栈开销、内存与外存的融合、分布式文件系统、NVM文件系统安全、容错、空间管理几个方面展开.最后,展望了NVM文件系统仍然有待探讨的几个研究方向,包括扩展性问题、虚拟内存与文件系统的有机融合以及分布式文件系统等.     

空间索引技术研究

空间索引可以提高空间数据库的操作效率,目前人们的研究工作更多地集中在空间数据的多维索引的研究上.文中全面地总结了当前空间数据库领域中空间索引以及时空索引的研究进展,描述了R树系列索引的构建思想,节点插入与分裂操作的不同.通过实验深入分析了R树以及R树变体的磁盘访问率,插入,删除,更新的CPU时间,验证了在数据激增的情况下,R树系列索引的复杂性带来的重叠问题会指数递增.由于R树当前应用的深度和广度,研究基于 R树的高效时空高维索引技术是解决索引应用问题一个有效方法.提出了索引性能改进的方向在于多种索引技术的结合,尤其是树形结构索引和网状结构索引的结合.     

WOBTree: a write-optimized B+-tree for non-volatile memory

The emergence of non-volatile memory (NVM) has introduced new opportunities for performance optimizations in existing storage systems. To better utilize its byte-addressability and near-DRAM performance, NVM can be attached on the memory bus and accessed via load/store memory instructions rather than the conventional block interface. In this scenario, a cache line (usually 64 bytes) becomes the data transfer unit between volatile and non-volatile devices. However, the failureatomicity of write on NVM is the memory bit width (usually 8 bytes). This mismatch between the data transfer unit and the atomicity unit may introduce write amplification and compromise data consistency of node-based data structures such as B+-trees. In this paper, we propose WOBTree, a Write-Optimized B+-Tree for NVM to address the mismatch problem without expensive logging. WOBTree minimizes the update granularity from a tree node to a much smaller subnode and carefully arranges the write operations in it to ensure crash consistency and reduce write amplification. Experimental results show that compared with previous persistent B+-tree solutions, WOBTree reduces the write amplification by up to 86× and improves write performance by up to 61× while maintaining similar search performance.     

COLIN: A Cache-Conscious Dynamic Learned Index with High Read/Write Performance

The recently proposed learned index has higher query performance and space efficiency than the conventional B+-tree. However, the original learned index has the problems of insertion failure and unbounded query complexity, meaning that it supports neither insertions nor bounded query complexity. Some variants of the learned index use an out-of-place strategy and a bottom-up build strategy to accelerate insertions and support bounded query complexity, but introduce additional query costs and frequent node splitting operations. Moreover, none of the existing learned indices are cache-friendly. In this paper, aiming to not only support efficient queries and insertions but also offer bounded query complexity, we propose a new learned index called COLIN (Cache-cOnscious Learned INdex). Unlike previous solutions using an out-of-place strategy, COLIN adopts an in-place approach to support insertions and reserves some empty slots in a node to optimize the node's data placement. In particular, through model-based data placement and cache-conscious data layout, COLIN decouples the local-search boundary from the maximum error of the model. The experimental results on five workloads and three datasets show that COLIN achieves the best read/write performance among all compared indices and outperforms the second best index by 18.4％, 6.2％, and 32.9％on the three datasets, respectively.     

基于密文块数组折半查找的B~+树密文数据库索引

为提升密文数据库的查询性能,提出了一种新型的B+树密文数据库索引.通过用密文块数组来组织树节点键值的方法,使节点能容纳的键值数量可以为任意大小,从而不再受加密长度限制.为提高在这种新型B~+树索引节点上的查找速度,设计了密文块数组折半查找算法,它根据密文块数组的特点,通过引入折半查找的思想,解决了原折半查找算法只能在一维数组上进行查找的局限,减少了对密文块的解密量.仿真实验结果表明,该索引比密文块数组顺序查找速度更快.     

Revisiting Persistent Indexing Structures on Intel Optane DC Persistent Memory

Persistent indexing structures are proposed in response to emerging non-volatile memory(NVM)to provide high performance yet durable indexes.However,due to the lack of real NVM hardware,many prior persistent indexing structures were evaluated via emulation,which varies a lot across different setups and differs from the real deployment.Recently,Intel has released its Optane DC Persistent Memory Module(PMM),which is the first production-ready NVM.In this paper,we revisit popular persistent indexing structures on PMM and conduct comprehensive evaluations to study the performance differences among persistent indexing structures,including persistent hash tables and persistent trees.According to the evaluation results,we find that Cacheline-Conscious Extendible Hashing(CCEH)achieves the best performance among all evaluated persistent hash tables,and Failure-Atomic ShifT B+-Tree(FAST)and Write Optimal Radix Tree(WORT)perform better than other trees.Besides,we find that the insertion performance of hash tables is heavily influenced by data locality,while the insertion latency of trees is dominated by the flush instructions.We also uncover that no existing emulation methods accurately simulate PMM for all the studied data structures.Finally,we provide three suggestions on how to fully utilize PMM for better performance,including using clflushopt/clwb with sfence instead of clflush,flushing continuous data in a batch,and avoiding data access immediately after it is flushed to PMM.     

支持k近邻查询的X*树索引结构

通过分析已有的索引结构在进行k近邻查询时效率上的不足,提出了适合进行k近邻查询的X*树索引结构,采用了新的结点分裂算法,同时不需要额外存储结点分裂的历史信息。实验结果表明它比X树的时间和空间性能更好,更适合k近邻查询的应用。     

RFN-B+树索引文件及其有效性

在对比传统的B树和B+树的定义和操作算法的基础上,定义了一种新的B+树:RFN-B+树,以获得更高的空间利用率和可用性.首先比较和分析了RFN-B+树与传统B+树的空间效率,然后讨论了RFN-B+树索引文件的有效性以及支持这种有效性的全链接指针结构和两个备用模块:基于虚拟根结点的随机检索算法和重构结点的算法.     

Index structures for matching XML twigs using relational query processors

Various index structures have been proposed to speed up the evaluation of XML path expressions. However, existing XML path indices suffer from at least one of three limitations: they focus only on indexing the structure (relying on a separate index for node content), they are useful only for simple path expressions such as root-to-leaf paths, or they cannot be tightly integrated with a relational query processor. Moreover, there is no unified framework to compare these index structures. In this paper, we present a framework defining a family of index structures that includes most existing XML path indices. We also propose two novel index structures in this family, with different space–time tradeoffs, that are effective for the evaluation of XML branching path expressions (i.e., twigs) with value conditions. We also show how this family of index structures can be implemented using the access methods of the underlying relational database system. Finally, we present an experimental evaluation that shows the performance tradeoff between index space and matching time. The experimental results show that our novel indices achieve orders of magnitude improvement in performance for evaluating twig queries, albeit at a higher space cost, over the use of previously proposed XML path indices that can be tightly integrated with a relational query processor.     

基于倒排表与B+树的联合索引技术

为提高XML文档的查询效率,提出一种基于倒排表与B+树的联合索引技术。DTD结构索引和内容索引采用倒排表作为索引单位,XML文档索引使用B+树作为索引基本组织。在DTD结构索引的结点编码中设置标识信息,便于确定需要查询的文档。通过建立DTD结构索引、XML文档索引和内容索引,实现混合型XML文档的查询。理论分析与实验结果表明,该技术具有较小的空间开销和较高的查询效率。     

基于持久化内存的索引设计重新思考与优化

非易失性内存(non-volatile memory,NVM)是近几年来出现的一种新型存储介质.一方面,同传统的易失性内存一样,它有着低访问延迟、可字节寻址的特性;另一方面,与易失性内存不同的是,掉电后它存储的数据不会丢失,此外它还有着更高的密度以及更低的能耗开销.这些特性使得非易失性内存有望被大规模应用在未来的计算机系统中.非易失性内存的出现为构建高效的持久化索引提供了新的思路.由于非易失性硬件还处于研究阶段,因此大多数面向非易失性内存的索引研究工作基于模拟环境开展.在2019年4月英特尔发布了基于3D-XPoint技术的非易失性内存硬件apache pass(AEP),这使得研究人员可以基于真实的硬件环境去进行相关研究工作.首先评测了真实的非易失性内存器件,结果显示AEP的写延迟接近DRAM,而读延迟是DRAM的3~4倍.基于对硬件的实际评测结果,研究发现过去很多工作对非易失性内存的性能假设存在偏差,这使得过去的一些工作大多只针对写性能进行优化,并没有针对读性能进行优化.因此,重新审视了之前研究工作,针对过去的混合索引工作进行了读优化.此外,还提出了一种基于混合内存的异步缓存方法.实验结果表明,经过异步缓存方法优化后的混合索引读性能是优化前的1.8倍,此外,经过异步缓存优化后的持久化索引最多可以降低50%的读延迟.     

面向NVM存储系统的快速文件访问系统

NVM存储设备系统具备提供高吞吐的潜质,包括接近内存的读写速度、字节寻址特性和支持多路转发等优势。但现有的系统软件栈并没有针对NVM去设计,使得系统软件栈存在许多影响系统访问性能的因素。通过分析发现文件系统的锁机制具有较大的开销,这使得数据的并发访问在多核心环境下成为一个难题。为了缓解这些问题,设计了无锁的文件读写机制以及基于字节的读写接口。通过取消基于文件的锁机制改变了粗粒度的访问控制,利用自主管理请求提高了进程的并发度;在设计能够利用字节寻址的新的文件访问接口时,不仅考虑了NVM存储设备的读写非对称,还考虑了其读写操作的不同特性。这些设计减少了软件栈的开销,有利于发挥NVM特性来提供一个高并发、高吞吐和耐久的存储系统。最后利用开源NVM模拟器PMEM实现了FPMRW原型系统,使用Filebench通用测试工具对FPMRW进行测试与分析,结果显示,FPMRW相对EXT+PMEM和XFS+PMEM能提高3%~40%的系统吞吐率。