HyperTree: High Concurrent B+tree Index Accelerator

B+tree is the most commonly used index structure to improve query performance in relational databases. It maintains the order of key attributes in the database by building a balanced tree. The index improves database query performance but introduces index maintenance overheads, which include index updating, index deletion and index insertion, because of the high sequential order of the B+tree. Additionally, the performance of the B+tree will be further damaged by the huge amount of data under the circumstance of big data. Therefore, it is significant to balance index performance between the requirement of query and maintenance in B+tree systems while improving the index operation efficiency. To tackle these problems in big data applications, a domain-specific B+tree accelerator, called HyperTree, is proposed to boost the performance of B+tree operations including both index query and index maintenance. HyperTree co-optimizes both memory bandwidth and computation efficiency to fully utilize resources on the domain-specific accelerator. Specifically, to improve memory bandwidth utilization, the structures of the node and the B+tree are designed based on the characteristic of high bandwidth utilization in memory burst read/write; to improve computation parallelism and concurrency, multiple homogeneous computing engines and multiple data channels are configured to fully utilize hardware resources and reduce control overheads. In addition, to eliminate the block of index maintenance operations, a sub-tree system is proposed to uncouple the nodes in B+tree. The results of experiments show that compared with CPU, the FPGA-based B+tree accelerator achieves 6.84 times boosts in the throughput of query transactions and 29.14 times boosts in the throughput of index insertion.