Efficient Batch Search Algorithm for B+ Tree Index Structures with Level-Wise Traversal on FPGAs Max Tzschoppe
∗ , Martin Wilhelm
∗ , Sven Groppe
† , Thilo Pionteck
∗
∗ Institute for Information Technology and Communications, Otto-von-Guericke University Magdeburg, Germany
arXiv:2604.21117v1 [cs.AR] 22 Apr 2026
† Institute of Computer Science, TU Bergakademie Freiberg, Germany
Abstract—This paper introduces a search algorithm for index structures based on a B+ tree, specifically optimized for execution on a field-programmable gate array (FPGA). Our implementation efficiently traverses and reuses tree nodes by processing a batch of search keys level by level. This approach reduces costly global memory accesses, improves reuse of loaded B+ tree nodes, and enables parallel search key comparisons directly on the FPGA. Using a high-level synthesis (HLS) approach, we developed a highly flexible and configurable search kernel design supporting variable batch sizes, customizable node sizes, and arbitrary tree depths. The final design was implemented on an AMD Alveo U250 Data Center Accelerator Card, and was evaluated against the B+ tree search algorithm from the TLX library running on an AMD EPYC 7542 processor (2.9 GHz). With a batch size of 1000 search keys, a B+ tree containing one million entries, and a tree order of 16, we measured a 4.9× speedup for the single-kernel FPGA design compared to a single-threaded CPU implementation. Running four kernel instances in parallel on the FPGA resulted in a 2.1× performance improvement over a CPU implementation using 16 threads. Index Terms—Index Structure, B+ Tree, Search Algorithm, FPGA Hardware Acceleration
I. I NTRODUCTION The growing demand for high-throughput analysis of largescale datasets poses significant challenges to core components of modern database systems. One essential aspect is main memory capacity, which has grown over the last decade to several terabytes in today’s servers. As a result, many database systems now operate entirely in-memory [1], giving rise to specialized in-memory database (IMDB) systems that drastically reduce access latencies. Index structures are a fundamental component of these modern IMDB systems. They store search keys together with pointers to the corresponding data records, enabling queries to be executed efficiently without scanning entire tables. Consequently, the performance of index structures is critical for overall database performance and has increasingly become a primary system bottleneck [2]. Index structures support not only search operations but also insertions and deletions. Nevertheless, search performance is the dominant factor for query efficiency, particularly in the context of data warehouses, which form the backbone for managing diverse and interconnected data sources. This is especially evident in online analytical processing (OLAP) workloads, which consist mainly of read-intensive SQL queries [3]. OLAP workloads are central to business intelligence applications, where insights are derived from large volumes of historical data. In these scenarios, queries often focus on a
relatively small hot subset of the dataset. Such subsets are frequently cached in order to reduce query latency and system load [4]. Since these subsets typically represent historical data that changes infrequently, the cached structures remain mostly static, require only occasional updates, and are commonly implemented using index structures. Another important scenario involving large volumes of predominantly static data is found in machine learning (ML) and large language model training pipelines. These pipelines often rely on aggregated data originating from data warehouses [5], which necessitates efficient access to vast amounts of structured and semi-structured data. As the scale of such workloads continues to grow, further improvements in query latency and throughput become increasingly important. Tree-based index structures, such as B-trees and B+ trees, are widely used in database systems due to their efficient search performance, which is characterized by logarithmic time complexity [6]. In particular, the B+ tree benefits from variable node sizes, which reduce tree depth and improve lookup efficiency. Its balanced structure and the organization of data exclusively at the leaf level also enable options for hardware acceleration. Optimized index structures based on B+ trees have been developed for CPU execution [7] as well as for offloading tree operations to hardware accelerators such as FPGAs [8]–[10] and GPUs [10], [11]. On CPUs, query processing typically involves individual lookups per request combined with a linear or binary search within each tree node, which limits throughput and parallelism. In contrast, hardware accelerators lack the high clock frequencies and advanced caching hierarchies of CPUs but they offer the advantage of massive parallelism and customizable data paths. GPUs and FPGAs therefore offer significant potential for accelerating such workloads by leveraging their inherent parallelism and enabling efficient memory access strategies. Accordingly, this work focuses on the design and implementation of a novel FPGA-optimized search algorithm for B+ trees. Our design loads individual nodes from the DDR memory of the FPGA card and processes all corresponding search queries simultaneously to minimize costly memory accesses. Comparisons are performed in parallel across all key entries within a node, utilizing a custom comparison logic based on a Cascading Bitwise Priority Comparison (CBPC) combined with a priority encoder. For evaluation purposes, we developed a fully automated testing framework focused on comprehensive and reliable assessments. To ensure an
unbiased workload, both the search keys and the tree entries are randomly generated. We evaluated the design on the AMD Alveo U250 Data Center Accelerator Card and compared the results against single- and multi-threaded CPU execution to ensure a realistic test scenario. To the best of our knowledge, no prior work has implemented or analyzed a complete B+ tree search algorithm on an FPGA. The proposed design supports fully flexible tree sizes, constrained only by the available DDR memory, and allows an arbitrary batch size (the number of search keys) up to a predefined maximum. A feature of this approach is that both parameters, tree size and batch size, can be adjusted at runtime. Since the comparison and buffering logic depend on the tree order (the maximum number of key entries per node), we evaluate multiple design variants with fixed tree orders to enable a comprehensive design space exploration. The remainder of this paper is structured as follows. Sec. II reviews related work on tree acceleration using FPGAs and GPUs. Sec. III provides essential background on the B+ tree structure. Sec. IV introduces our FPGA-optimized B+ tree search algorithm and describes the proposed design in detail. Sec. V presents a comprehensive evaluation of our approach, including various measurement results. Finally, Sec. VI concludes the paper with a summary of the key findings. II. R ELATED W ORK Trees are indispensable for implementing efficient index structures. The following related work section focuses on how tree operations can be accelerated using GPUs or FPGAs. Tree Operation Acceleration on FPGAs. Several research groups have investigated the use of FPGAs to accelerate Btree operations. Liu et al. [7] present the Honeycomb system, which accelerates get and scan operations on an FPGA. They report a throughput improvement of 2× for scan-heavy workloads compared to a multi-threaded CPU implementation. This particular workload is well-suited for FPGA execution. This means that the observed performance gains may not be applicable to more realistic workloads. Melikoglu et al. [8] implemented an optimized B-tree search algorithm on an FPGA and compared it with a non-optimized baseline version, achieving a throughput gain of 8×. The study lacks a comparison against CPU-based search performance and is primarily relevant in the context of hardware architecture research. Heinrich et al. [9] proposed a hybrid approach in which a B+ tree is distributed between the CPU and FPGA. Their design accelerates the upper levels of the tree on the FPGA while completing the search on the CPU. They report a maximum speedup of 2.3× compared to pure CPU execution. However, accelerating only the upper tree levels can become a bottleneck for very large trees, where the number of nodes per level increases significantly in the lower levels. Tree operation acceleration on GPUs. In addition to FPGA-based approaches, several works have investigated GPU acceleration for tree operations. Shahvarani et al. [11] proposed a hybrid design in which a B+ tree is partitioned between the CPU and GPU, with the lower tree levels processed
on the GPU. The authors report a speedup of 2.4× over a CPU-only execution. Their comparison is made against a single-threaded CPU implementation, whereas modern multithreaded CPU-based B+ tree designs would likely yield significantly better performance. Another notable example of GPUbased acceleration is presented by Koppehel et al. [12], who introduce CuART, a scalable and parallel engine for lookup and update operations on adaptive radix trees, implemented in CUDA. The design leverages warp-level parallelism and memory access strategies to maximize throughput. CuART achieves up to a 5× speedup for mixed workloads compared to a single-threaded CPU baseline. However, similar to previous works, it lacks a direct comparison against optimized multithreaded CPU tree implementations. Overall, the presented related works on accelerating tree operations using FPGAs and GPUs demonstrates promising speedups but often relies on limited or unbalanced comparisons. Many studies evaluate performance against singlethreaded CPU baselines rather than modern multi-threaded implementations, reducing the validity of claimed gains. Additionally, several FPGA-based approaches only accelerate upper tree levels or rely on host memory, introducing bottlenecks that limit scalability for large tree structures. With our proposed FPGA design, we address these limitations by implementing a complete B+ tree search algorithm over all tree levels that supports fully flexible tree sizes. Unlike prior work, we perform a fair and comprehensive comparison against multi-threaded CPU implementations to assess realistic performance gains. III. B+ T REE BACKGROUND The B+ tree is a widely adopted index structure used in both open-source [13], [14] and commercial [15], [16] databases and file systems, supporting efficient query operations on large, sorted datasets [6]. The concept of B-trees was originally developed by Bayer et al. [17], with the B+ tree being an extension that organizes all data entries at the leaf level, while internal nodes contain only keys. Two key characteristics define the B+ tree: 1) Its balanced tree structure ensures consistent key lookup times with logarithmic time complexity. 2) Its adjustable node size allows for a high fan-out, which minimizes the height of the tree. In addition for file-intensive operations, the B+ tree’s structure, where all leaf nodes are linked in a linear sequence, enables efficient sequential access from the leftmost to the rightmost leaf node. A small example of a B+ tree is shown in Fig. 1, where the green node represents an internal node and the blue nodes correspond to leaf nodes. B+ Tree Metrics. The order of a B+ tree, denoted by m, defines the maximum number of child pointers per inner node. Consequently, the maximum number of keys kmax in an inner node is kmax = m − 1. To maintain the balanced structure of the tree, each internal node must have at least m 2 child pointers, meaning it must be at least half full. To estimate the size of a full B+ tree, the maximum number of nodes
10
15
Search Key Index
Search Keys [1000] S8 S7 S6 S5
5
10
15
19
Result FIFO [1000]
20
#1 A2 #7 A1 #4 A0
Fig. 1. Simple and small B+ tree structure with order m = 3. Ai
Ph−1 Nmax can be calculated as: Nmax = i=0 mi where h denotes the height (i.e., the number of levels) of the tree. Another important metric is the maximum number of keys per tree level, given by Lmax = mh · kmax = mh · (m − 1). This value indicates how many keys can be stored at a given level before the tree must grow in height by adding a new level.
DDR
Ni
Load Node
+1
Sj Compare Logic #? A?
Fig. 2. Search Algorithm Overview.
IV. FPGA-O PTIMIZED B+ T REE S EARCH A LGORITHM The following section presents our FPGA-optimized B+ tree search algorithm, outlining the core concept, the memory organization, and the architecture of the search procedure. A. Idea Conventionally, multiple search queries are processed sequentially, with each query starting after the previous one has completed. In contrast, our approach reinvents this concept by collecting queries and processing them in large batches. The HLS design was kept as simple and modular as possible. The development of an efficient implementation is guided by two key principles. First, the design should process as many steps of the algorithm in parallel as possible to take advantage of the hardware design. Second, memory accesses should be minimized, as they are costly in terms of latency. Fig. 2 provides an overview of the proposed implementation strategy. The core idea is to process queries in batches of search keys S by traversing the B+ tree level by level, while storing intermediate results in a FIFO buffer. Each entry in the result FIFO contains two fields: the address A of a node and the number # of search keys that need to be compared with that node. The general flow of our search algorithm proceeds as follows: a node N is loaded from the address specified in the first FIFO entry. Once the node is available, it is forwarded to the comparison logic, where the corresponding number of search keys # are sequentially compared against the search keys S defined by them. Each comparison is done in parallel and produces a new node address and a number of associated search keys. Fig. 2 illustrates how node N0 is loaded from address A0 . The label #4 indicates that four search keys need to be processed for this node. As a result, node N0 is compared with search keys S5 through S8 . During each iteration, the SearchKeyIndex is incremented, and the comparison results are written to the result FIFO. This approach preserves the processing order and simplifies access to the search keys. Since the batch of queries is sorted, progressively smaller sub-batches are passed to each subsequent level during successive memory access. This approach minimizes overhead by
ensuring that all queries targeting the same node are processed in a single memory access. In summary, the entire query batch is processed level by level, loading only the nodes required for the current set, and this enables an efficient level-wise traversal strategy. However, the benefit diminishes for higher tree levels due to the fewer queries per node if the queries are uniformly distributed. B. B+ Tree Memory Organization On the CPU, the B+ tree resides in main memory, and its nodes are connected via pointers. To transfer this structure to an FPGA, a mapper is required to transform the hierarchical tree into a flat array representation. This transformation is performed using a breadth-first search (BFS) algorithm. The resulting flat tree array includes both internal and leaf nodes. To ensure a simplified and uniform memory layout, all nodes are padded to have the same size. We chose to embed the child addresses directly within each node to avoid additional address computation on the FPGA. slot use
depth
4B
4B
keys [kmax] 24B
32B
32B
child addresses [kmax+1] 32B
8B
8B
8B
innerNode slot use
depth
4B
4B
keys [kmax] 24B
32B
32B
data [kmax] 32B
8B
8B
8B
8B
leafNode
Fig. 3. Node Layout
The node layout for inner and leaf nodes are illustrated in Fig. 3. Each node contains the number of active entries (slotUse), the level at which the node is located (depth) and node keys (key). The inner node ends up with the addresses of the child nodes (childAddress). The leaf node contains the actual data (data), with the last 8-bytes are left unused to maintain the same node size as an inner node. The sizes of the key, childAddress and data sections depend on the maximum number of key entries per node, denoted as
kmax . The node size Nsize depends on the tree order m as described in Sec. III and can be calculated as: kmax + 1 Nsize = 32 B + 32 B · kmax + 32 B · (1) 4 = 40 B · (kmax + 1) = 40 B · m To maximize the data throughput between host and FPGA, the array of nodes is partitioned into 32-byte chunks. This uniform sizing enables a simplified memory access module and loading nodes from memory becomes more efficient and implementation-friendly.
Search Key
Node Keys
Sj
Ki
1 8-bit Compare LT EQ GT
Ki+1
32 8-bit Compare LT EQ GT
1 8-bit Compare LT EQ GT
CBPC Reduction Logic leq[i]
eq[i]
32 8-bit Compare LT EQ GT
Kn 1 8-bit Compare LT EQ GT
CBPC Reduction Logic leq[i+1]
eq[i+1]
32 8-bit Compare LT EQ GT
CBPC Reduction Logic leq[n]
eq[n]
Priority Encoder
LEQ true/false
EQ true/false
C. Search Key Memory Organization Search queries are collected by the host and transferred in batches to the memory of the FPGA board. Each batch consists of a 32-byte search key. Since the search keys are required during every iteration of the search process, a buffer with a fixed maximum length is implemented in the design. Before the search process begins, the entire batch is preloaded from memory into the buffer implemented using BRAM. This significantly reduces the access latency for search keys during execution. To avoid array partitioning and to stay within the available BRAM resources of the FPGA, the buffer size is set to accommodate 1000 entries. D. Result Memory Organization To enable batch processing of search queries, the B+ tree is traversed level by level. This approach requires that intermediate results from each level are stored in a result FIFO. This FIFO serves a dual purpose. First, it temporarily holds intermediate results, which include the child address for the next node and the number of search keys assigned to that specific child node. Second it stores the final search results. Thanks to the uniform structure of inner and leaf nodes, managing this process is straightforward. While processing internal nodes, 8-byte child address entries and an additional 4 bytes for the number of associated search keys are stored. When the traversal reaches the leaf level, the result format switches: each entry is either a -1 (indicating the search key was not found) or a 8-byte data value if a match is found—both of which are written to the same FIFO. The size of the FIFO is determined by the batch size. E. Parallel Key Comparison The design’s main component is the comparison module, which is responsible for comparing search queries with the currently loaded node. When a node is transferred from the memory to the FPGA, all search keys associated with that node are processed together. This coordination is managed by the result FIFO, which provides the number of keys to be compared with the node. This is feasible because the search keys are sorted and stored in BRAM, allowing for a simple step-by-step traversal of all search terms at each level. The flow of the key comparisons is depicted in Fig. 4. The number of key comparisons per node is determined by kmax , which must be specified prior to synthesis. This implies that each search key must be compared against all kmax entries in
Fig. 4. Key Comparison Procedure.
the node to determine the correct child node address. Each individual comparison involves comparing a 32-byte search key with a 32-byte node key. This is implemented using 32 parallel 8-bit comparators, each producing a 3-bit result indicating whether the corresponding byte is less than, equal to, or greater than its counterpart. For each comparison, only one of these three bits can be active. To determine which child node a search key should be routed to, it is sufficient to evaluate whether the key is less than or equal to the node entry, with equality also being used for identifying exact matches in the leaf nodes. Therefore, the 32 per-byte comparison results are reduced to a single comparison outcome using a Cascading Bitwise Priority Comparison (CBPC) unit. The CBPC is composed entirely of combinatorial logic and resolves the 32 intermediate results in a single step into one final comparison result. This 32-byte comparison is performed in parallel for each of the kmax slots in the node. Consequently, kmax comparison outcomes (each indicating less/equal or equal) are generated. These are further reduced to a single final decision using a priority encoder. The combination of parallel 8-bit comparators, the CBPC, and the priority encoder encourages the HLS tool to synthesize highly parallel and efficient comparison logic. F. Search Algorithm The execution of the entire search algorithm can be described as follows: Before the actual search begins, all search keys are transferred from global memory into the FPGA’s BRAM. Subsequently, a node—initially the root node—is loaded from memory. These load operations utilize burst reads to fully exploit the available memory bandwidth. Each search key is then compared in parallel with the keys of the root node, as described in Sec. IV-E. Every comparison yields the child address of the node to which the search key must be passed next. If the same child address corresponds to multiple search keys, a counter is incremented accordingly. This counter ultimately reflects the number of search keys associated with that specific child node. Both the child address and the corresponding count are stored in the result FIFO. After processing the root node, the next iteration begins with the second level of the tree. Based on the first child
address stored in the result FIFO, the corresponding next node is loaded, and the procedure is repeated until the leaf level is reached. At the leaf level, the result FIFO no longer contains child addresses but instead holds the actual results or data entries corresponding to the search queries. In the final step, these results are collected and written back to the global memory using burst writes so that they can be further accessed and processed by the host.
platform used is an AMD Alveo U250 Data Center Accelerator Card operating at 300 MHz. Host
FPGA Card Global Memory
CPU
DDR[0]
DDR[2]
DDR
DDR[3]
G. Kernel Parallelism The proposed design is resource-efficient enough to be able to implement multiple kernel instances on the same device. This opens up further optimization potential by executing identical search kernels in parallel on the FPGA, given that multiple memory controllers are available. This concept is illustrated in Fig. 5b, where P denotes the parallelization parameter. Batch
Batch
Kernel
Kernel
1
1
2 P
(a) Single Instance
(b) Multiple Instances
Fig. 5. Batch distribution for single and multiple kernel instances.
The batch of search keys can be evenly distributed based on the parallelization factor P, allowing either a larger number of keys to be processed simultaneously or a reduction in execution time for the same batch size. V. E VALUATION The presented FPGA design for the B+ tree search algorithm was developed using the AMD Vitis high-level synthesis (HLS) flow. The system architecture consists of a CPU and an FPGA connected via PCIe. In the following sections, the system architecture is described in detail, and the performance of the FPGA-based design is analyzed and compared to a CPU-based B+ tree search algorithm. A. System Architecture An overview of the hybrid system architecture is provided in Fig. 6, which consists of two main components: the host system and the FPGA board. The host system includes a CPU with its own DDR memory, while the FPGA board comprises programmable logic (PL) and four DDR memory modules, each with a capacity of 16 GB. The DDR memory on the FPGA board is referred to as global memory, which can be accessed by the CPU via PCIe and by the PL via AXI Stream interfaces. Specifically, the host system is equipped with an AMD EPYC 7542 processor running at a base frequency of 2.9 GHz and a turbo frequency of up to 3.4 GHz. The FPGA
FPGA
DDR[1] BRAM
Fig. 6. System Architecture
As the focus of this work is on accelerating a static B+ tree, the index structure is maintained on the host system. For this purpose, we utilize the B+ tree implementation provided by the TLX Library [18]. The B+ trees are generated using the TLX library and we employ host-side code to transform the tree structure into flat arrays suitable for transfer to the FPGA’s global memory. Based on formula (1) and the available global memory, trees with up to 1.6 billion entries can be stored, corresponding to approximately 25 million nodes for m = 64 and up to 100 million nodes for m = 16. Additionally, we generate random tree entries and search keys to build the B+ tree and corresponding query batches. To verify the correctness of the FPGA-based search, the same query batch is evaluated using the TLX search function, and the results are compared. B. Timing Methodology The timing measurement of a single search request can be divided into two main phases. The first phase encompasses the initialization steps performed on the host side, including the construction and transformation of the B+ tree, the OpenCL setup, the FPGA programming, and the transfer of the tree structure to the global memory. These steps are part of a onetime initialization process and are not repeated for every new search request. For each subsequent query, only the new batch of search keys needs to be transferred to the FPGA. The second phase begins with the kernel execution on the FPGA. This includes the kernel initialization as well as the Compute Unit (CU) execution, where the actual search operation takes place. The dependencies and the temporal flow of these steps are illustrated in Fig. 7a. Before initiating the next request, the host system must read the previous results, generate a new batch of search queries, and write this batch to the global memory. The pipelined timing scenario is illustrated in Fig. 7b. The host can overlap data transfers and result collection with ongoing kernel execution. This is feasible because the search keys are preloaded into the FPGA’s BRAM, eliminating the need for global memory access during computation. For a sufficiently large batch size data transfers and host-side operations can be fully masked by the FPGA’s kernel execution time and no additional timing overhead occurs compared to a pure CPU-based execution.
1
Host
1
2
1
FPGA
2
3n
2 Time
(a) Single Kernel
1
Host
1
FPGA
3 2
2 1 2
Time
4 1 X xi xIQM = · n n
(2)
i= 4 +1
Additionally, we use the interquartile range (IQR), the difference between the upper and lower quartiles, to capture variability [19]. In the following plots, the IQR is visualized as error bars, indicating the range within which the central half of the data lies. D. Resource Utilization
(b) Pipelined Single Kernel
Host
OpenCL init
Kernel
write to DDR
read from DDR
CU
Fig. 7. Interaction between Host and FPGA.
For our measurements, we use a system with a static B+ tree index structure that is transferred to the FPGA once and reused thereafter. Therefore, the overhead of this one-time initialization phase becomes negligible in a productive system. The experimental results are obtained using the flow shown in Fig. 7a. For all results, we report the the kernel and compute unit execution times according to Fig. 7b, as these are the decisive execution times. C. Experimental Setup To conduct a comprehensive analysis of the proposed design, we analyzed multiple test configurations. For the B+ tree construction, we vary the tree size (the number of entries in the tree), the tree order m, and the batch size (the number of search keys processed in one iteration). The tree size is independent of the hardware design and is limited only by the available DDR memory on the FPGA board. In our evaluation, we selected tree sizes ranging from 1 to 10 million entries. The tree order must be set prior to synthesis, as it defines the node size and determines structural aspects of the comparison logic. Consequently, we implemented separate hardware designs for three different tree orders: m = 16, m = 32, and m = 64. The batch size is configurable at runtime, with a maximum of 1000 queries, and can be varied within this range during testing. In general, we conduct timing measurements for both the FPGA and CPU implementations of the search algorithm. For the FPGA, we integrate trace logic capable of recording timestamps for kernel execution, compute unit activity, and OpenCL API calls. On the host side, timing is measured using the chrono module from the standard C++ library. To obtain more meaningful and robust results, each configuration is repeated multiple times: 10 iterations for the FPGA measurements and 100 for the CPU measurements. Due to occasional significant outliers in the CPU timings, we report the results using the interquartile mean xIQM . This metric discards the lower and upper quartiles (i.e., the lowest and highest 25% of values) and computes the arithmetic mean over the central 50% of the data [19]:
The FPGA resource utilization is summarized in Tab. I for both single and four-kernel instance designs. To contextualize the results, the table provides both the absolute number of FPGA resources used (Total) and the available resources (Available) for individual designs. Their difference reflects the resource utilization consumed by the FPGA shell and the system. Single Instance Utilization. For the single instance designs, it is evident that the maximum achievable frequency is maintained for the configurations with m = 16 and m = 32. In contrast, the design with m = 64 achieves only approximately two-third of the maximum frequency, indicating that higherorder trees introduce timing challenges due to the increased parallel logic in the search and comparison blocks. All three designs demonstrate very efficient resource usage, utilizing only 0.74-1.71% of the available Look-Up Tables (LUTs) and 0.33-0.76% of the Flip-Flops (FFs). The moderate increase in resource usage from m = 16 to m = 64 is a direct result of the design structure. As the number of tree orders increases to m = 32 and m = 64, the utilization of LUTs increases by factors of 1.5× and 1.8×, respectively. The Block-RAM and Digital Signal Processing (DSP) unit utilization remains constant across all configurations. This consistency can be attributed to the fact that the allocated memory for search keys and result buffers does not vary with the tree order. Only the size of the currently loaded node changes, implying that node data is stored using distributed RAM, rather than BRAM. Four Instances Utilization. The resource utilization of the four-instance design scales similarly to the single-instance design, as the kernel is simply instantiated four times, leading to a roughly fourfold increase in overall resource usage. The design is generally timing-bound. The configurations with m = 16 and m = 32 are close to the target frequency and the synthesis fails with timing violations for the configuration with m = 64 since no further modifications are made to the search kernel. E. FPGA Performance In the following, we present the measured timing results for the FPGA designs. These measurements were conducted as described in Sec.V-B and Fig.7a. Single Instance Designs. Fig. 8 presents the Kernel and Compute Unit execution times for the three single-instance FPGA designs. The tree size is fixed at one million entries, while the batch size varies from 1 to 1000 search keys. There
TABLE I FPGA R ESOURCE U TILIZATION
Total Available m = 16 m = 32 m = 64 Available m = 16 1. Inst. 2. Inst. 3. Inst. 4. Inst. m = 32 1. Inst. 2. Inst. 3. Inst. 4. Inst.
1 726 208 1 624 067 11 991 15 374 27 750 1 522 722 47 576 11 885 11 866 11 870 11 955 61 400 15 331 15 336 15 370 15 363
300.0 300.0 199.4 293.2
300.0
Util. in % 94.08 0.74 0.95 1.71 88.21 3.12 0.78 0.78 0.78 0.79 4.03 1.01 1.01 1.01 1.01
LUT as Mem 790 192 769 486 1090 1098 1344 754 684 4360 1090 1090 1090 1090 4392 1098 1098 1098 1098
Util. in % 97.38 0.14 0.14 0.17 95.51 0.58 0.14 0.14 0.14 0.14 0.58 0.15 0.15 0.15 0.15
m = 16 m = 16 m = 32 m = 32 m = 64 m = 64
3,000 Time in µs
LUT
2,000
FF
Util. in %
3 456 000 3 291 026 10 861 15 695 24 954 3 139 326 43 431 10 864 10 825 10 869 10 873 62 668 15 711 15 602 15 671 15 684
1,000
BRAM
Util. in %
2688 2282 22 22 22 2068 88 22 22 22 22 88 22 22 22 22
95.23 0.33 0.48 0.76 90.84 1.38 0.35 0.34 0.35 0.35 2.00 0.50 0.50 0.50 0.50
84.9 0.96 0.96 0.96 76.93 4.26 1.06 1.06 1.06 1.06 4.26 1.06 1.06 1.06 1.06
DSP 12 288 12 284 0 0 0 12 275 0 0 0 0 0 0 0 0 0 0
Util. in % 99.97 0 0 0 99.89 0 0 0 0 0 0 0 0 0 0
m = 16 1 Inst m = 16 1 Inst m = 32 1 Inst m = 32 1 Inst m = 16 4 Inst m = 16 4 Inst m = 32 4 Inst m = 32 4 Inst
2,000 Time in µs
4 Instances
1 Inst.
Clock Freq. in MHz
1,500 1,000 500
0 0
200
400
600
800
1,000
Batch Size
0 0
200
400
600
800
1,000
Batch Size Fig. 8. Single Instance Designs - CU ( ) and Kernel ( ) execution times with a fix tree size of 1 million entries. Each configuration is 10× repeated.
is a constant overhead of approximately 150 µs between the kernel and CU times. The CU time reflects the duration for transferring nodes between global memory and the FPGA, as well as the duration for executing all search operations for the given batch. As expected, the time per search key decreases as batch sizes increase. As the batch size increases, more comparisons are required, and additional tree nodes must be loaded from global memory. This leads to a corresponding increase in execution times across all configurations. The notably slower performance observed for the tree order m = 64 is due to the fact that this design operates at only two-thirds of the maximum achievable clock frequency. Overall, the smallest tree order, m = 16, consistently delivers the best performance across all batch sizes. Four Instance Designs. Beside the three baseline designs, we evaluate two optimized configurations in which the same kernel is instantiated four times, with each instance assigned to a dedicated DDR memory bank. The results for tree orders m = 16 and m = 32 are shown in Fig. 9. These results demonstrate that kernel-level parallelism and batch distribution across four independent kernels, each obtaining 250 search keys, significantly reduce the kernel execution time. With a batch size of 1000, the CU execution times for the
Fig. 9. Four Instance Designs - CU ( ) and Kernel ( ) execution times with a fix tree size of 1 million entries. Each configuration is 10× repeated.
single- and four-instance designs show a speedup of 3.4×, which approaches the ideal 4× acceleration. In terms of kernel execution time, speedups of 2.5× and 2.6× are achieved for tree orders m = 16 and m = 32, respectively. These lower speedups compared to the CU times are primarily due to kernel initialization and setup overhead. F. CPU and FPGA Performance Comparison In the following part, the presented FPGA results are compared against a pure CPU execution using the search function provided by the TLX Library [18]. The search algorithm in this work is specifically designed for FPGA execution and performs worse on a pure CPU compared to the TLX search algorithm. Single-Threaded CPU. Fig. 10 shows the kernel execution times for all three tree orders measured on the FPGA, alongside the corresponding search execution times for the same batches on a single-threaded CPU. The FPGA consistently outperforms the CPU across all configurations. The single instance FPGA design achieves with m = 16 a speedup of 4.9× compared to the single threaded CPU search. The CPU measurements exhibit high variability, which may be due to the task not having exclusive access to the CPU core.
10,000 5,000 0 0
200
400
600
800
1,000
2→3
3→4
4→5
5→6
tree levels 1 Inst 4 Inst 1 Thread 2 Threads 4 Threads 16 Threads
12,500 Time in µs
Time in µs
1→2
m = 16 FPGA m = 32 FPGA m = 64 FPGA m = 16 CPU m = 32 CPU m = 64 CPU
15,000
10,000 7,500 5,000 2,500
Batch Size Fig. 10. Single-Threaded CPU - FPGA kernel ( ) and CPU search ( ) execution times with a fix tree size of 1 million entries. FPGA configuration is 10× and CPU is 100× repeated.
0 100
101
102 103 104 105 Number of keys in tree
106
107
10,000 4 Inst 1 Thread 2 Threads 4 Threads 16 Threads
Time in µs
8,000 6,000 4,000
Fig. 12. Varying Tree Sizes - FPGA kernel ( ) and CPU search ( ) execution times with a fix batch size of 1000 search keys and a tree order of m = 16. FPGA configuration is 10× and CPU is 100× repeated.
2,000 0 0
200
400
600
800
1,000
design at small tree sizes compared to the four-instance variant is due to the fact that the kernel instances are not launched at exactly the same time; the start times of the instances are shifted, which slightly increases the reported execution time. In summary, all results of the evaluation are presented in Table II.
Batch Size Fig. 11. Multi-Threaded CPU - FPGA kernel ( ) and CPU search ( ) execution times with a fix tree size of 1 million entries and a tree order of m = 16. FPGA configuration is 10× and CPU is 100× repeated.
It can be concluded that the FPGA and CPU implementations achieve optimal performance with a tree order of m = 16. Therefore, only the m = 16 tree order will be considered in the following. Multi-Threaded CPU. Database queries on CPUs are typically distributed across multiple threads. We analyze multithreaded CPU performance in Fig. 11. Following the same strategy as with the four-instance FPGA design, the batch is evenly divided among the available CPU threads. We vary the number of threads up to 16, observing a saturation point beyond which additional threads yield minimal performance gains. At very small batch sizes, the multi-threaded CPU execution performs worse than the single-threaded case due to synchronization overhead. However, this effect becomes negligible as the batch size increases. The maximum speedup achieved by the four-instance FPGA design over the 16-thread CPU configuration is 2.1× at a batch size of 1000. Varying Tree Sizes. Fig. 12 shows the execution time for varying tree sizes, ranging from 1 entry to 10 million entries, using a fixed batch size of 1000. The 16-threaded CPU configuration outperforms the single-instance FPGA implementation for trees larger than 100,000 entries. However, the four-kernel FPGA design still outperforms the 16-threaded CPU version at a tree size of 1 million entries. The results for tree sizes larger than 1 million follow the same trend, with slight performance improvements. At 10 million entries, a speedup of 2.15× is achieved. The slightly better performance of the single-instance FPGA
TABLE II S PEEDUP OVERVIEW Tree Order Comparison1 CU m = 16 1 Inst. with 4 Inst. 3.4× FPGA m = 32 1 Inst. with 4 Inst. 3.4× FPGA m = 16 1 Inst. with 1 Thread & CPU m = 16 4 Inst. with 16 Threads 1 based on batch size of 1000 and tree size of 1 million
Kernel 2.5× 2.6× 4.9× 2.1×
VI. C ONCLUSION The evaluation demonstrates significant performance improvements for B+ tree search on the AMD Alveo U250 Data Center Accelerator Card. The proposed approach achieves a speedup of up to 4.9× for the single-instance design and 2.1× for the four-instance design compared to single- and multithreaded CPU implementations, respectively. These gains are enabled by a dedicated hardware-optimized search algorithm that effectively exploits the parallelism of the FPGA while improving memory access efficiency. The results further show that the proposed design is highly scalable and particularly effective for static B+ trees. This characteristic makes it well suited for use as an index structure for caching hot subsets in data warehouse environments, where data remains largely unchanged and query performance is critical. Overall, the design utilizes only a small fraction of the available hardware resources while maintaining scalability with increasing tree sizes. As the tree grows, the execution time per search operation decreases, highlighting the efficiency of the approach for large-scale workloads.
R EFERENCES [1] A. T. Kabakus and R. Kara, “A performance evaluation of in-memory databases,” Journal of King Saud University - Computer and Information Sciences, vol. 29, no. 4, pp. 520–525, Oct. 2017. [2] O. Kocberber, B. Grot, J. Picorel, B. Falsafi, K. Lim, and P. Ranganathan, “Meet the walkers: accelerating index traversals for inmemory databases,” in Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture, ser. MICRO-46. ACM, Dec. 2013, pp. 468–479. [3] M. Jarke, Fundamentals of Data Warehouses, 1st ed., M. Lenzerini, Y. Vassiliou, and P. Vassiliadis, Eds. Berlin/Heidelberg: Springer Berlin Heidelberg, 2003, description based on publisher supplied metadata and other sources. [4] H. Nicholson, P. Chrysogelos, and A. Ailamaki, “HPCache: memoryefficient OLAP through proportional caching revisited,” The VLDB Journal, vol. 33, no. 6, pp. 1775–1791, Dec. 2023. [5] T. Bodner, A. Böhm, M. Böther, A. Klimovic, D. Durner, M. Grund, A. Kipf, I. Oukid, B. Schiefer, P. Parchas, H. Gildhoff, P. Unterbrunner, T. Karnagel, J. Giceva, T. Ziegler, and M. Hentschel, “Opinion Pieces of the BTW 2025 Workshop On Advances in Cloud Data Management,” Datenbank-Spektrum, vol. 25, no. 3, pp. 187–195, Nov. 2025. [6] M. Schneider, Implementierungskonzepte fuer Datenbanksysteme, 1st ed. Springer Berlin Heidelberg, 2004. [7] J. Liu, A. Dragojević, S. Fleming, A. Katsarakis, D. Korolija, I. Zablotchi, H.-C. Ng, A. Kalia, and M. Castro, “Honeycomb: Ordered key-value store acceleration on an FPGA-based smartNIC,” IEEE Transactions on Computers, vol. 73, no. 3, pp. 857–871, Mar. 2024. [8] O. Melikoglu, O. Ergin, B. Salami, J. Pavon, O. Unsal, and A. Cristal, “A novel FPGA-based high throughput accelerator for binary search trees,” in 2019 International Conference on High Performance Computing & Simulation (HPCS). IEEE, Jul. 2019, pp. 612–619. [9] D. Heinrich, S. Werner, M. Stelzner, C. Blochwitz, T. Pionteck, and S. Groppe, “Hybrid FPGA approach for a b+ tree in a semantic web
database system,” in 2015 10th International Symposium on Reconfigurable Communication-centric Systems-on-Chip (ReCoSoC). IEEE, Jun. 2015, pp. 1–8. [10] J. Fang, Y. T. B. Mulder, J. Hidders, J. Lee, and H. P. Hofstee, “Inmemory database acceleration on FPGAs: a survey,” The VLDB Journal, vol. 29, no. 1, pp. 33–59, Oct. 2019. [11] A. Shahvarani and H.-A. Jacobsen, “A hybrid b+-tree as solution for inmemory indexing on CPU-GPU heterogeneous computing platforms,” in Proceedings of the 2016 International Conference on Management of Data, ser. SIGMOD/PODS’16. ACM, Jun. 2016, pp. 1523–1538. [12] M. Koppehel, T. Groth, S. Groppe, and T. Pionteck, “CuART - a CUDA-based, scalable radix-tree lookup and update engine,” in 50th International Conference on Parallel Processing, ser. ICPP 2021. ACM, Aug. 2021, pp. 1–10. [13] Oracle. (2025, Jul.) Mysql 8.4. [Online]. Available: https://dev.mysql. com/doc/refman/8.0/en/innodb-index-types.html [14] PostgreSQL Global Development Group. (2025) Postgresql 17.5. [Online]. Available: https://www.postgresql.org/docs/current/ indexes-types.html [15] IBM Corporation. (2025, Jan.) Db2 database. IBM Corporation. [Online]. Available: https://www.ibm.com/docs/en/db2/12.1.0?topic= indexes-index-structure [16] Oracle. (2025, Apr.) Oracle database, database concepts, 21c. Oracle. [Online]. Available: https://docs.oracle.com/en/database/oracle/ oracle-database/21/cncpt/indexes-and-index-organized-tables.html [17] R. Bayer and E. M. McCreight, “Organization and maintenance of large ordered indexes,” Acta Informatica, vol. 1, no. 3, pp. 173–189, 1972. [18] T. Bingmann. (2018) TLX: Collection of sophisticated C++ data structures, algorithms, and miscellaneous helpers. [Online]. Available: https://panthema.net/tlx [19] Y. Dodge, The concise encyclopedia of statistics. Springer Science + Business Medi, 2008.