Fast and Space-Efficient In-Memory Indexes (Hash Tables, B-trees)
Cache- and space-efficient in-memory hash tables and ordered indexes for scalable systems.
In-memory indexes — hash tables and ordered structures like B-trees — sit on the critical path of modern data systems. This project designs indexes that are simultaneously fast, space-efficient, and concurrency-friendly.
We built IcebergHT (Pandey et al., 2023), a high-performance hash table with stability and low associativity, and Zombie Hashing (Chesetti et al., 2025), which reclaims the cost of tombstones in deletion-heavy workloads. For ordered data we designed the BP-tree (Xu et al., 2023) and a locality-optimized, concurrent in-memory B-skiplist (Luo et al., 2025), and we have studied how learned indexes perform for external-memory joins (Chesetti & Pandey, 2025).