HAD B+-Tree: A Hotness-Aware Adaptive B+-Tree for SSD/HDD-Based Hybrid Storage Architecture

Modern database systems have widely used B+-tree to index data. However, the traditional B+-tree will index all the keys within the dataset, yielding a large index size on big datasets. We note skewed query workloads are common in real applications, focusing on a small portion of the dataset. To this end, indexing the whole dataset is not necessary. Motivated by such an observation, we propose a new hotness-aware adaptive index called HAD B+-tree, which includes a hot B+-tree and a warm B+-tree on SSD and a full B+-tree on HDD. The hot and warm B+-trees index the keys that are frequently queried. The full B+-tree is stored on HDD to reduce storage costs. We maintain the hotness of keys through a heat-tracking table to determine which keys need to be indexed on the hot or warm tree. With such a mechanism, we demonstrate that search efficiency can be improved by controlling the height of the trees. We conduct experiments on real devices to compare the HAD B+-tree with the ordinary B+-tree and the adaptive merging under the YCSB workloads. The results suggest the efficiency and effectiveness of the HAD B+-tree.