SEDIT: Space-Efficient Discriminative Bit Tree for Hybrid Memory Indexing

Byte-addressable persistent memory (PM) and DRAM-PM hybrid memory have been heavily studied in the storage domain. Given the relative latency and bandwidth advantages of DRAM, it is aptly suited as the indexing space in storage systems. However, compared to PM, DRAM is more expensive and offers smaller capacity, leading to constraints in indexing space resources. Consequently, it is imperative to design an index structure for hybrid memory that is DRAM-friendly while maintaining high indexing performance. To address this challenge, we propose SEDIT, a space-efficient discriminative bit tree as the DRAM-resided index structure. Instead of storing actual keys in the index node, SEDIT stores the positions of keys’ discriminative bits in a cache-friendly and pointer-free manner. To speed up indexing operations, we design a COW-based pyramid-enabled swift bit location strategy. We conduct extensive experiments to evaluate both the space overhead and access performance for SEDIT. The results demonstrate that SEDIT remarkably reduces the DRAM space consumption, and gains competitive or better indexing performance compared with its counterparts.