基于GPU的内存数据库索引技术研究

由于内存数据库具有比基于磁盘的数据库更高的查询响应速度和并发度，其被广泛应用于银行、证券交易所和在线购物等数据量庞大并且实时性要求高的商业领域。索引能够有效降低数据的搜索空间、提高内存数据库的查询效率，然而当前它却受到性能和效率的挑战。 基于图形处理器的通用计算（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-树并行构建算法进行空间复杂度的分析，与传统的构建算法相比，提出算法的空间利用率明显得到提高。同样，为验证提出方案的有效性，进行相关的实验论证。