论文摘要
由于内存数据库具有比基于磁盘的数据库更高的查询响应速度和并发度，其被广泛应用于银行、证券交易所和在线购物等数据量庞大并且实时性要求高的商业领域。索引能够有效降低数据的搜索空间、提高内存数据库的查询效率，然而当前它却受到性能和效率的挑战。基于图形处理器的通用计算（GPGPU）在多个领域具有重要的研究价值和应用前景，也是当前研究的热点。目前图形处理器（GPU）上索引技术的研究已有一定的相关成果，然而这些研究成果存在着诸如：并行算法未充分利用硬件的资源、并行度不高，算法缺乏可扩展性且不能解决索引数据的更新等问题。因此，本文以如何充分利用GPU的硬件资源、最大限度地提高内存数据库索引的操作性能为主要研究内容，在相关研究的基础上，本文主要做了以下工作：1.对目前内存数据库索引技术的研究成果进行总结归纳，并且对GPU的硬件特点和编程技术做了相关综述。2.提出一种基于GPU T-树索引的并行计算方案，该方案通过分析T-树的节点间的父子关系，在GPU上实现对T-树的最大并行度构建。设计在GPU上T-树索引数据可任意伸缩的动态数组，解决GPU上尚无动态分配显存空间的问题；通过对各种构建T-树方案的理论和实验分析，提出的并行建树方案较传统的建树方案，在操作效率和空间利用率上均有明显的性能优势。为解决CUDA程序数据传输的瓶颈问题，通过页锁定内存的方式提高CPU和GPU间的数据传输速率；为适应未来硬件发展的需求，对算法的可扩展性进行相关研究；为验证方案的正确性，提出基于GPU T-树的遍历算法；为验证提出的并行方案的有效性，进行相关的实验论证。3.为加速多维数据的操作性能，提出一种基于GPU多维线性哈希索引的并行处理方案。该方案通过对传统哈希索引数据结构的扩展，利用2层的数据结构可实现哈希表在GPU上的任意收缩，从而解决多维数据在GPU上无法有效更新的问题。在哈希表的记录并行批量插入算法中，采用并行分裂哈希桶的方式可加速哈希表分裂的处理速度，从而提高了插入的效率；设计一个灵活的溢出桶管理机制，可提高多维哈希索引在GPU上的存储空间利用率；对提出的记录并行批量插入方案进行算法时间和空间复杂度的分析，并与传统的CPU算法进行相关对比；在各种硬件平台上对多维线性哈希索引记录的并行批量插入、批量删除和查询的操作性能进行相关的实验论证。4.提出一种基于GPU缓存敏感CSB+-树索引的无锁并行处理方案，该方案通过对传统的CSB+-树的结构改进，可实现CSB+-树的索引数据在GPU上动态更新。在GPU上提出基于树层和基于节点索引键CSB+-树两种并行构建算法，其中后者可实现对CSB+-树的最大并行度构建；通过在CSB+-树的内部节点添加填充位的方式，可减少GPU线程块里的线程分支数，从而提高CSB+-树的查询性能；通过对CSB+-树的查询算法使用共享存储器的可行性分析，指出传统的缓存敏感技术的思想在复杂的GPU内存框架中并不适合使用。为验证提出的并行方案的有效性，在多个硬件平台上进行相关的实验论证。5.在GPU平台上提出一种BD-树索引的并行计算方案，该方案通过修改传统BD-树的哈希函数，可实现对BD-树索引的并行处理。通过对传统BD-树的数据结构改进，可实现BD-树索引数据在GPU上的更新操作；通过分析BD-树的树形结构，可实现基于内部节点键的并行度方式构建BD-树；通过增加额外的空间开销，减少GPU原子函数的调用次数，可显著提高BD-树哈希表的数据插入效率；对BD-树并行构建算法进行空间复杂度的分析，与传统的构建算法相比，提出算法的空间利用率明显得到提高。同样，为验证提出方案的有效性，进行相关的实验论证。