多核处理器支持的频繁访问B＋-Tree

Frequent access B＋-Tree based on chip multi-procrssor

传统B＋-Tree自顶向下访问模式不适应于频繁访问应用模式，面向多核处理器支持，提出了针对频繁访问的FAB＋-Tree（Frequent Access B＋-Tree）。在B＋-Tree的基础上增加了Hash辅助索引，使得访问B＋-Tree是可以直接定位到叶结点，并利用基于内存的直接访问表及位矢量列表提高更新性能。同时基于共享L2-Cache多核处理器，提出了基于流水线的FAB＋-Tree多线程访问模块，并优化了该模块的共享Cache访问性能。基于开源数据库Ingres实现了FAB＋-Tree和多线程访问模块，实验结果表明B＋-Tree的访问性能得到显著提高。

Traditional Top-Down access model of B＋-Tree is not proper for the applications of frequent access. Supported by CMP （Chip Multi-Processor） , this paper presents FAB＋-Tree （Frequent Access B＋-Tree） , which is based on B＋-Tree and supplemented by a hash indexing, and the hash indexing could let FAB＋-Tree access leaf nodes directly. Memory-based direct-access table and bit vector are used to improve the update performance. At the same time, basing on shared L2-Cache CMP, we presents multithreaded FAB＋-Tree access module using pipelined execution model. In the experiments, we implemented FAB^-Tree and multithreaded FAB＋-Tree access module in Ingres, and the performance analysis and experimental results show that performance of B＋-Tree has been improved remarkably.