A B^ε-organized table using Markov decision process for main memory database engines

Main memory databases are increasingly preferred in modern applications for real-time data processing due to their exceptional throughput performance. However, implementing index organization within these engines presents significant challenges. This paper addresses these challenges by introducing a novel index organization, the Bε-organized table, which leverages the Bε-tree index and an optimization algorithm combined with Markov Decision Processes. The Bε-organized table enables efficient data access by storing the latest versions in the leaf nodes of the Bε-tree index and incorporating two effective contention management mechanisms. The Markov Decision Process-based optimization algorithm identifies optimal configurations for achieving high performance with the Bε-organized table across diverse workloads. We have integrated the Bε-organized table into a widely studied open-source main memory database system. Our extensive experimental results, conducted using standard benchmarks, demonstrate that the Bε-organized table outperforms state-of-the-art storage organizations-such as heap organization and conventional index organization-achieving up to 1.7× higher performance under TPC-C workloads and up to 2.5× higher performance under YCSB workloads.