When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories

Summary: Extendible Radix Tree (ERT) for persistent memory combines a radix-tree with per-node extendible hashing to achieve large fanout, small height, and constant-time in-node lookups, reducing random reads during traversal. Range queries use partial ordering in each node's hash table; inserts/updates are incremental with limited writes; experiments show up to 2.65x search, 4.41x insert, and 2.43x range-query speedups over state-of-the-art PM indexes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hadbb27b415c2e152
Venue: SIGMOD
Year: 2023
Pagerank: 5.8776022e-05
Overall Rank: 6,075 | 59.28%
DOI: 10.1145/3588959
PDF: Download (CC BY 4.0)

Incoming Non-self Citations Over Time

Authors

1. Ke Wang (Shanghai Qi Zhi Institute; Yale University)
2. Guanqun Yang (New York University; Shanghai Qi Zhi Institute)
3. Yiwei Li (Tsinghua University)
4. Huanchen Zhang (Shanghai Qi Zhi Institute; Tsinghua University)
5. Mingyu Gao (Shanghai Qi Zhi Institute; Tsinghua University)

BibTeX Citation

@inproceedings{wang_sigmod23,
        title = {{When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories}},
        author = {Wang, Ke and Yang, Guanqun and Li, Yiwei and Zhang, Huanchen and Gao, Mingyu},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588959},
        url = {https://dl.acm.org/doi/10.1145/3588959},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,103	LITS: An Optimized Learned Index for Strings	2024	VLDB	5.5824915e-05
7,831	Buffered Persistence in B+ Trees	2024	SIGMOD	5.4290292e-05
10,701	DART: A Lock-free Two-layer Hashed ART Index for Disaggregated Memory	2026	SIGMOD	4.9605343e-05
11,612	Sorting on Byte-Addressable Storage: The Resurgence of Tree Structure	2024	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
23	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00055523999
504	FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory	2016	SIGMOD	0.00017195543
632	Persistent B+-Trees in Non-Volatile Main Memory	2015	VLDB	0.00015366735
906	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.00013129817
964	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012798312
967	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB	0.00012766144
1,366	Dash: Scalable Hashing on Persistent Memory	2020	VLDB	0.00010879316
1,431	Write-Behind Logging	2017	VLDB	0.00010667031
1,863	LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory	2020	VLDB	9.4679185e-05
1,865	PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors	2011	VLDB	9.4644494e-05
2,247	Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?	2019	SIGMOD	8.7591557e-05
2,288	DPTree: Differential Indexing for Persistent Memory	2020	VLDB	8.6817411e-05
4,461	Memory Management Techniques for Large-Scale Persistent-Main-Memory Systems	2017	VLDB	6.5752676e-05
6,080	NBTree: a Lock-free PM-friendly Persistent B+-Tree for eADR-enabled PM Systems	2022	VLDB	5.8759147e-05
6,690	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	5.6917141e-05
8,046	PiBench Online: Interactive Benchmarking of Persistent Memory Indexes	2020	VLDB	5.3849769e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	632	Persistent B+-Trees in Non-Volatile Main Memory	2015	VLDB
2	11,980	Hamming Tree: The Case for Memory-Aware Bit Flipping Reduction for NVM Indexing	2021	CIDR
3	10,491	ART That Lasts: Persistent Multiversion Adaptive Radix Trees with Fast Atomic Range Queries	2026	SIGMOD
4	2,288	DPTree: Differential Indexing for Persistent Memory	2020	VLDB
5	12,943	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB
6	12,369	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS
7	1,849	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
8	2,755	Evaluating Persistent Memory Range Indexes	2020	VLDB
9	4,534	Persistent Memory Hash Indexes: An Experimental Evaluation	2021	VLDB
10	6,963	The Past, Present and Future of Indexing on Persistent Memory	2022	VLDB