RLART: An Adaptive Radix Tree Based on Deep Reinforcement Learning

Adaptive Radix Tree (ART) is an efficient data structure for key-based lookup and insertion operations. It finds extensive applications in various domains, including database management systems, network routing, operating systems, and storage systems. Compared to traditional prefix trees, its aim is to provide enhanced space and time efficiency. By utilizing appropriate node types and efficient search strategies, it optimizes the time and space complexities of search and insertion operations. During the construction of ART, frequent memory allocations and deallocations result in suboptimal performance, introducing additional memory overhead. Traditional methods struggle to address these drawbacks. To mitigate this issue, we draw inspiration from Deep Reinforcement Learning (DRL) and develop a DRL based model to determine how to select node types for creating new nodes, rather than relying on currently employed manual heuristics. Importantly, the ART constructed using DRL-based methods doesn’t necessitate replacing the existing index and query processing algorithms deployed in the current database infrastructure. Experimental results on both real and synthetic datasets containing 200 million objects clearly indicate the superiority of our DRL-based index construction approach over conventional methods for building ART in terms of performance.