Hybrid FPGA approach for a B<sup>+</sup> tree in a Semantic Web database system

Abstract

In this paper we present a hybrid index structure which is allocated in a Field Programmable Gate Array (FPGA) and a traditional CPU-based host system. The used index structure of this system is a B <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup> -tree which is a common index used in disk based databases. The hybrid index is divided into two parts. The lower levels of the B <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup> -tree, especially the leaves where the values are stored, are located on the host system while the root and the most upper levels with the interior nodes are stored on the FPGA. We speed up the search in the upper levels of our hybrid index by applying an FPGA accelerated parallel search. In the evaluation we show how the amount of keys inside the interior nodes on the FPGA and the order of the B <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup> -tree take an impact on the whole hybrid system. The results show that the computation time of the software system can be halved.