{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:06:50Z","timestamp":1779131210915,"version":"3.51.4"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>Indexes are essential for efficient query processing in database systems, with ordered indexes particularly suited for supporting range queries. Non-volatile memory (NVM) technology offers fast, byte-addressable access and persistence across system failures, enabling rapid recovery without costly index reconstruction. While recent efforts have focused on building durable NVM-based indexes for point queries and updates, they often lack efficient support for concurrent range queries with correctness. We present PermART, a persistent, versioned adaptive radix tree that surpasses current NVM-based indexes in point query and update performance and supports efficient, consistent, range queries under concurrency. By integrating multiversioning into ART, we enable efficient, linearizable range queries while improving point operation performance through in-node logging. Our evaluation shows that our persistent ART matches or exceeds the performance of current NVM-based indexes for point queries and updates, while offering correct, linearizable range queries, which existing indexes do not provide.<\/jats:p>","DOI":"10.1145\/3802015","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["ART That Lasts: Persistent Multiversion Adaptive Radix Trees with Fast Atomic Range Queries"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-4437-0786","authenticated-orcid":false,"given":"Arash","family":"Khalaji","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0074-1031","authenticated-orcid":false,"given":"Trevor","family":"Brown","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-7036-0397","authenticated-orcid":false,"given":"Khuzaima","family":"Daudjee","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n. d.]. GitHub - sfu-dis\/bztree: An open-source BzTree implementation \u2014 github.com. https:\/\/github.com\/sfu-dis\/bztree\/tree\/master. [Accessed 22-09-2025]."},{"key":"e_1_2_1_2_1","unstructured":"[n. d.]. Take advantage of sparse indexes - Amazon DynamoDB \u2014docs.aws.amazon.com."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178489"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3164147"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484254"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223785"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/356842.356846"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/319996.319998"},{"key":"e_1_2_1_9_1","volume-title":"Concurrency Control and Recovery in Database Systems","author":"Bernstein Philip A.","unstructured":"Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley. http:\/\/research.microsoft.com\/en-us\/people\/philbe\/ccontrol.aspx"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196896"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627535.3638501"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35476-2_3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374542"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381898.3397212"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 18th International Conference on Distributed Computing and Networking","author":"Chatterjee Bapi","year":"2017","unstructured":"Bapi Chatterjee. 2017. Lock-free Linearizable 1-Dimensional Range Queries. In Proceedings of the 18th International Conference on Distributed Computing and Networking, Hyderabad, India, January 5-7, 2017. ACM, 9. http:\/\/dl.acm.org\/citation.cfm?id=3007771"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752947"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"2634","DOI":"10.14778\/3407790.3407850","article-title":"?Tree: a Persistent B-Tree with Low Tail Latency","volume":"13","author":"Chen Youmin","year":"2020","unstructured":"Youmin Chen, Youyou Lu, Kedong Fang, Qing Wang, and Jiwu Shu. 2020. ?Tree: a Persistent B-Tree with Low Tail Latency. Proc. VLDB Endow., Vol. 13, 11 (2020), 2634-2648. http:\/\/www.vldb.org\/pvldb\/vol13\/p2634-chen.pdf","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference (Boston, MA, USA) (USENIX ATC '18). USENIX Association, USA, 373\u2013385","author":"David Tudor","year":"2018","unstructured":"Tudor David, Aleksandar Dragojevi\u00e7, Rachid Guerraoui, and Igor Zablotchi. 2018. Log-free concurrent data structures. In Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference (Boston, MA, USA) (USENIX ATC '18). USENIX Association, USA, 373\u2013385."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2694344.2694359"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323197"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071615"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551808"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_24_1","volume-title":"Endurable Transient Inconsistency in Byte-Addressable Persistent B-Tree. In 16th USENIX Conference on File and Storage Technologies, FAST 2018","author":"Hwang Deukyeon","year":"2018","unstructured":"Deukyeon Hwang, Wook-Hee Kim, Youjip Won, and Beomseok Nam. 2018. Endurable Transient Inconsistency in Byte-Addressable Persistent B-Tree. In 16th USENIX Conference on File and Storage Technologies, FAST 2018, Oakland, CA, USA, February 12-15, 2018, Nitin Agrawal and Raju Rangaswami (Eds.). USENIX Association, 187-200. https:\/\/www.usenix.org\/conference\/fast18\/presentation\/hwang"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_23"},{"key":"e_1_2_1_26_1","first-page":"41","article-title":"Processing in the Hybrid OLTP & OLAP Main-Memory Database System HyPer","volume":"36","author":"Kemper Alfons","year":"2013","unstructured":"Alfons Kemper, Thomas Neumann, Jan Finis, Florian Funke, Viktor Leis, Henrik M\u00fche, Tobias M\u00fchlbauer, and Wolf R\u00f6diger. 2013. Processing in the Hybrid OLTP & OLAP Main-Memory Database System HyPer. IEEE Data Eng. Bull., Vol. 36, 2 (2013), 41-47. http:\/\/sites.computer.org\/debull\/A13june\/hyper1.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483589"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247488"},{"key":"e_1_2_1_29_1","volume-title":"WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems. In 15th USENIX Conference on File and Storage Technologies, FAST 2017","author":"Lee Se Kwon","year":"2017","unstructured":"Se Kwon Lee, K. Hyun Lim, Hyunsub Song, Beomseok Nam, and Sam H. Noh. 2017. WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems. In 15th USENIX Conference on File and Storage Technologies, FAST 2017, Santa Clara, CA, USA, February 27 - March 2, 2017, Geoff Kuenning and Carl A. Waldspurger (Eds.). USENIX Association, 257-270. https:\/\/www.usenix.org\/conference\/fast17\/technical-sessions\/presentation\/lee-se-kwon"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359635"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933349.2933352"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372728"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384355"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3337821.3337827"},{"key":"e_1_2_1_37_1","first-page":"1","volume-title":"ROART: Range-query Optimized Persistent ART. In 19th USENIX Conference on File and Storage Technologies, FAST 2021","author":"Ma Shaonan","year":"2021","unstructured":"Shaonan Ma, Kang Chen, Shimin Chen, Mengxing Liu, Jianglang Zhu, Hongbo Kang, and Yongwei Wu. 2021. ROART: Range-query Optimized Persistent ART. In 19th USENIX Conference on File and Storage Technologies, FAST 2021, February 23-25, 2021, Marcos K. Aguilera and Gala Yadgar (Eds.). USENIX Association, 1-16. https:\/\/www.usenix.org\/conference\/fast21\/presentation\/ma"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749436"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915251"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/348.318588"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_16"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_2_1_44_1","unstructured":"David P. Reed. 1978. Naming and synchronization in a decentralized computer system. Ph.D. Dissertation. Massachusetts Institute of Technology Cambridge MA USA. https:\/\/hdl.handle.net\/1721.1\/16279"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503221.3508441"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00049"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196895"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441602"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460874"},{"key":"e_1_2_1_50_1","first-page":"167","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015","author":"Yang Jun","year":"2015","unstructured":"Jun Yang, Qingsong Wei, Cheng Chen, Chundong Wang, Khai Leong Yong, and Bingsheng He. 2015. NV-Tree: Reducing Consistency Cost for NVM-based Single Level Systems. In Proceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015, Santa Clara, CA, USA, February 16-19, 2015, Jiri Schindler and Erez Zadok (Eds.). USENIX Association, 167-181. https:\/\/www.usenix.org\/conference\/fast15\/technical-sessions\/presentation\/yang"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372717"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802015","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:27:58Z","timestamp":1779128878000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802015"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802015"],"URL":"https:\/\/doi.org\/10.1145\/3802015","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}