Optimizing the B+tree Index with Hotness Awareness and Adaptivity

The B+tree index has been widely used in modern computer systems for accelerating data access and computing. However, the traditional B+tree indexes all the keys within the dataset, yielding a large index file, especially on large datasets. We note that skewed query workloads are common in real applications, which usually focus on a small portion of the whole dataset. Inspired by such an observation, this paper proposes a new hotness-aware adaptive index, called RFB+tree, which includes a hot index in fast storage (e.g., Solid-State Drive, SSD) and a full B+tree in slow storage like magnetic hard disks (HDD). The hot tree only indexes the keys that are recently accessed and adds an extra field called range flag for every key in it to determine which intervals have been indexed. With such a mechanism, we demonstrate that the search efficiency can be improved by lowering the tree height. We conduct experiments on real devices to compare the RFB+tree with several baselines, including the ordinary B+tree and the adaptive merging approach, under the public YCSB workloads. The results suggest the efficiency and effectiveness of our proposal.