GreenB+Tree: an energy-efficient B+tree for MIMD architectures

In the current data-intensive landscape, B+trees are crucial data structures utilized across various fields like databases and web indexing. With the rise of data explosion, the demand for high-performance real-time query processing in database systems has surged. For instance, Alibaba’s PolarDB and AnalyticDB systems handle massive query volumes and real-time data processing, highlighting the need for efficient solutions. Traditional approaches leveraging GPUs for B+tree performance enhancement have yielded positive results but suffer from high energy consumption, making their widespread deployment in large data centers impractical. This paper introduces GreenB+Tree, an energy-efficient B+tree optimized for the PEZY-SC3s chip, known for its high energy efficiency and MIMD architecture, which mitigates common GPU memory and warp divergence issues. GreenB+Tree innovatively transforms the B+tree structure into two one-dimensional arrays, significantly reducing memory costs and computational overhead. It further incorporates query-agglomerated optimization (QAO) and the persistent data residency strategy (PDRS) to minimize global memory access and enhance cache efficiency. Experimental evaluations demonstrate that GreenB+Tree achieves a throughput of 62.6 Million Queries Per Second per Watt (MQPS/W), outperforming contemporary GPU-based solutions by approximately 4.5 times.