{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T15:35:25Z","timestamp":1772724925278,"version":"3.50.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,12,9]]},"abstract":"<jats:p>Persistent memory (PM) is fundamentally changing the way database index structures are built by enabling persistence, high performance, and (near) instant recovery all on the memory bus. Prior work has proposed many techniques to tailor index structure designs for PM, but they were mostly based on volatile DRAM with simulation due to the lack of real PM hardware. Until today is it unclear how these techniques will actually perform on real PM hardware.<\/jats:p>\n          <jats:p>\n            With the recent released Intel Optane DC Persistent Memory, for the first time, this paper provides a comprehensive evaluation of recent persistent index structures. We focus on B\n            <jats:sup>+<\/jats:sup>\n            -Tree-based range indexes and carefully choose four representative index structures for evaluation: wBTree, NV-Tree, BzTree and FPTree. These four tree structures cover a wide, representative range of techniques that are essential building blocks of PM-based index structures. For fair comparison, we used an unified programming model for all trees and developed\n            <jats:italic>PiBench<\/jats:italic>\n            , a benchmarking framework which targets PM-based indexes. Through empirical evaluation using representative workloads, we identify key, effective techniques, insights and caveats to guide the making of future PM-based index structures.\n          <\/jats:p>","DOI":"10.14778\/3372716.3372728","type":"journal-article","created":{"date-parts":[[2020,1,6]],"date-time":"2020-01-06T20:19:37Z","timestamp":1578341977000},"page":"574-587","source":"Crossref","is-referenced-by-count":76,"title":["Evaluating persistent memory range indexes"],"prefix":"10.14778","volume":"13","author":[{"given":"Lucas","family":"Lersch","sequence":"first","affiliation":[{"name":"TU Dresden &amp; SAP SE"}]},{"given":"Xiangpeng","family":"Hao","sequence":"additional","affiliation":[{"name":"Simon Fraser University"}]},{"given":"Ismail","family":"Oukid","sequence":"additional","affiliation":[{"name":"Snowflake Computing"}]},{"given":"Tianzheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Simon Fraser University"}]},{"given":"Thomas","family":"Willhalm","sequence":"additional","affiliation":[{"name":"Intel Deutschland GmbH"}]}],"member":"320","published-online":{"date-parts":[[2020,1,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Direct Access for files. https:\/\/www.kernel.org\/doc\/Documentation\/filesystems\/dax.txt.  Direct Access for files. https:\/\/www.kernel.org\/doc\/Documentation\/filesystems\/dax.txt."},{"key":"e_1_2_1_2_1","unstructured":"Ext4 Filesystem. https:\/\/www.kernel.org\/doc\/Documentation\/filesystems\/ext4.txt.  Ext4 Filesystem. https:\/\/www.kernel.org\/doc\/Documentation\/filesystems\/ext4.txt."},{"key":"e_1_2_1_3_1","unstructured":"Intel 64 and IA-32 Architectures Optimization Reference Manual. https:\/\/software.intel.com\/en-us\/download\/intel-64-and-ia-32-architectures-optimization-reference-manual.  Intel 64 and IA-32 Architectures Optimization Reference Manual. https:\/\/software.intel.com\/en-us\/download\/intel-64-and-ia-32-architectures-optimization-reference-manual."},{"key":"e_1_2_1_4_1","unstructured":"The SGI XFS Filesystem. https:\/\/www.kernel.org\/doc\/Documentation\/filesystems\/xfs.txt.  The SGI XFS Filesystem. https:\/\/www.kernel.org\/doc\/Documentation\/filesystems\/xfs.txt."},{"key":"e_1_2_1_5_1","volume-title":"AgigaTech Non-Volatile RAM","year":"2017","unstructured":"AgigaTech. AgigaTech Non-Volatile RAM . 2017 . http:\/\/www.agigatech.com\/nvram.php. AgigaTech. AgigaTech Non-Volatile RAM. 2017. http:\/\/www.agigatech.com\/nvram.php."},{"issue":"5","key":"e_1_2_1_6_1","first-page":"553","article-title":"A High-Performance Latch-free Range Index for Non-Volatile Memory","volume":"11","author":"Arulraj J.","year":"2018","unstructured":"J. Arulraj , J. Levandoski , U. F. Minhas , and P.-A. Larson . BzTree : A High-Performance Latch-free Range Index for Non-Volatile Memory . PVLDB , 11 ( 5 ): 553 -- 565 , 2018 . J. Arulraj, J. Levandoski, U. F. Minhas, and P.-A. Larson. BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory. PVLDB, 11(5):553--565, 2018.","journal-title":"PVLDB"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734714.1734731"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1145\/2983990.2984019","volume-title":"Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA","author":"Bhandari K.","year":"2016","unstructured":"K. Bhandari , D. R. Chakrabarti , and H.-J. Boehm . Makalu: Fast Recoverable Allocation of Non-volatile Memory . In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2016 , pages 677 -- 694 , 2016. K. Bhandari, D. R. Chakrabarti, and H.-J. Boehm. Makalu: Fast Recoverable Allocation of Non-volatile Memory. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2016, pages 677--694, 2016."},{"key":"e_1_2_1_9_1","first-page":"21","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR)","author":"Chen S.","year":"2011","unstructured":"S. Chen , P. B. Gibbons , and S. Nath . Rethinking Database Algorithms for Phase Change Memory . In Proceedings of the Conference on Innovative Data Systems Research (CIDR) , pages 21 -- 31 , 2011 . S. Chen, P. B. Gibbons, and S. Nath. Rethinking Database Algorithms for Phase Change Memory. In Proceedings of the Conference on Innovative Data Systems Research (CIDR), pages 21--31, 2011."},{"key":"e_1_2_1_10_1","volume-title":"Persistent B+-Trees in Non-Volatile Main Memory. PVLDB, 8(7):786--797","author":"Chen S.","year":"2015","unstructured":"S. Chen and Q. Jin . Persistent B+-Trees in Non-Volatile Main Memory. PVLDB, 8(7):786--797 , 2015 . S. Chen and Q. Jin. Persistent B+-Trees in Non-Volatile Main Memory. PVLDB, 8(7):786--797, 2015."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_12_1","volume-title":"A Revolutionary Breakthrough in Memory Technology. 3D XPoint Launch Keynote","author":"Crooke R.","year":"2015","unstructured":"R. Crooke and M. Durcan . A Revolutionary Breakthrough in Memory Technology. 3D XPoint Launch Keynote , 2015 . R. Crooke and M. Durcan. A Revolutionary Breakthrough in Memory Technology. 3D XPoint Launch Keynote, 2015."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3277355.3277392"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592814"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the BSDCan Conference","author":"Evans J.","year":"2006","unstructured":"J. Evans . A Scalable Concurrent malloc (3) Implementation for FreeBSD . In Proceedings of the BSDCan Conference , 2006 . J. Evans. A Scalable Concurrent malloc (3) Implementation for FreeBSD. In Proceedings of the BSDCan Conference, 2006."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/191843.191886"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/IEDM.2005.1609379"},{"key":"e_1_2_1_18_1","first-page":"187","volume-title":"16th USENIX Conference on File and Storage Technologies (FAST 18)","author":"Hwang D.","year":"2018","unstructured":"D. Hwang , W.-H. Kim , Y. Won , and B. Nam . Endurable Transient Inconsistency in Byte-Addressable Persistent B+-Tree . In 16th USENIX Conference on File and Storage Technologies (FAST 18) , pages 187 -- 200 , 2018 . D. Hwang, W.-H. Kim, Y. Won, and B. Nam. Endurable Transient Inconsistency in Byte-Addressable Persistent B+-Tree. In 16th USENIX Conference on File and Storage Technologies (FAST 18), pages 187--200, 2018."},{"key":"e_1_2_1_19_1","volume-title":"Persistent Memory Development Kit","year":"2018","unstructured":"Intel. Persistent Memory Development Kit . 2018 . http:\/\/pmem.io\/pmdk. Intel. Persistent Memory Development Kit. 2018. http:\/\/pmem.io\/pmdk."},{"key":"e_1_2_1_20_1","volume-title":"Intel Optane DC Persistent Memory Readies for Widespread Deployment","author":"Intel Corporation","year":"2018","unstructured":"Intel Corporation . Intel Optane DC Persistent Memory Readies for Widespread Deployment . 2018 . https:\/\/newsroom.intel.com\/news\/intel-optane-dc-persistent-memory-readies-widespread-deployment\/. Intel Corporation. Intel Optane DC Persistent Memory Readies for Widespread Deployment. 2018. https:\/\/newsroom.intel.com\/news\/intel-optane-dc-persistent-memory-readies-widespread-deployment\/."},{"key":"e_1_2_1_21_1","volume-title":"Processor Counter Monitor","author":"Intel Corporation et al.","year":"2019","unstructured":"Intel Corporation et al. Processor Counter Monitor . 2019 . https:\/\/github.com\/opcm\/pcm. Intel Corporation et al. Processor Counter Monitor. 2019. https:\/\/github.com\/opcm\/pcm."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872362.2872410"},{"key":"e_1_2_1_23_1","volume-title":"Basic Performance Measurements of the Intel Optane DC Persistent Memory Module. arXiv preprint arXiv.1903.05714","author":"Izraelevitz J.","year":"2019","unstructured":"J. Izraelevitz , J. Yang , L. Zhang , J. Kim , X. Liu , A. Memaripour , Y. J. Soh , Z. Wang , Y. Xu , S. R. Dulloor , Basic Performance Measurements of the Intel Optane DC Persistent Memory Module. arXiv preprint arXiv.1903.05714 , 2019 . J. Izraelevitz, J. Yang, L. Zhang, J. Kim, X. Liu, A. Memaripour, Y. J. Soh, Z. Wang, Y. Xu, S. R. Dulloor, et al. Basic Performance Measurements of the Intel Optane DC Persistent Memory Module. arXiv preprint arXiv.1903.05714, 2019."},{"key":"e_1_2_1_24_1","volume-title":"Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth D. E.","year":"2014","unstructured":"D. E. Knuth . Art of Computer Programming, Volume 3: Sorting and Searching . Addison-Wesley Professional , 2014 . Section 6.4: Hashing. D. E. Knuth. Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley Professional, 2014. Section 6.4: Hashing."},{"key":"e_1_2_1_25_1","first-page":"257","volume-title":"WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems. In 15th USENIX Conference on File and Storage Technologies (FAST 17)","author":"Lee S. K.","year":"2017","unstructured":"S. K. Lee , K. H. Lim , H. Song , B. Nam , and S. H. Noh . WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems. In 15th USENIX Conference on File and Storage Technologies (FAST 17) , pages 257 -- 270 , 2017 . S. K. Lee, K. H. Lim, H. Song, B. Nam, and S. H. Noh. WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems. In 15th USENIX Conference on File and Storage Technologies (FAST 17), pages 257--270, 2017."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3337821.3337827"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321481"},{"key":"e_1_2_1_30_1","first-page":"31","volume-title":"Write-Optimized Dynamic Hashing for Persistent Memory. In 17th USENIX Conference on File and Storage Technologies (FAST 19)","author":"Nam M.","year":"2019","unstructured":"M. Nam , H. Cha , Y. ri Choi , S. H. Noh , and B. Nam . Write-Optimized Dynamic Hashing for Persistent Memory. In 17th USENIX Conference on File and Storage Technologies (FAST 19) , pages 31 -- 44 , 2019 . M. Nam, H. Cha, Y. ri Choi, S. H. Noh, and B. Nam. Write-Optimized Dynamic Hashing for Persistent Memory. In 17th USENIX Conference on File and Storage Technologies (FAST 19), pages 31--44, 2019."},{"issue":"11","key":"e_1_2_1_31_1","first-page":"1166","volume":"10","author":"Oukid I.","year":"2017","unstructured":"I. Oukid , D. Booss , A. Lespinasse , W. Lehner , T. Willhalm , and G. Gomes . Memory Management Techniques for Large-Scale Persistent-Main-Memory Systems. PVLDB , 10 ( 11 ): 1166 -- 1177 , 2017 . I. Oukid, D. Booss, A. Lespinasse, W. Lehner, T. Willhalm, and G. Gomes. Memory Management Techniques for Large-Scale Persistent-Main-Memory Systems. PVLDB, 10(11):1166--1177, 2017.","journal-title":"Memory Management Techniques for Large-Scale Persistent-Main-Memory Systems. PVLDB"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915251"},{"key":"e_1_2_1_33_1","volume-title":"Intel Software Documentation, 2016","author":"Rudoff A.","year":"2016","unstructured":"A. Rudoff . Deprecating the PCOMMIT Instruction . Intel Software Documentation, 2016 . https:\/\/software.intel.com\/en-us\/blogs\/ 2016 \/09\/12\/deprecate-pcommit-instruction. A. Rudoff. Deprecating the PCOMMIT Instruction. Intel Software Documentation, 2016. https:\/\/software.intel.com\/en-us\/blogs\/2016\/09\/12\/deprecate-pcommit-instruction."},{"key":"e_1_2_1_34_1","first-page":"4","volume-title":"Proceedings of the 3rd VLDB Workshop on In-Memory Data Mangement and Analytics","author":"Schwalb D.","unstructured":"D. Schwalb , M. Dreseler , M. Uflacker , and H. Plattner . NVC-Hashmap: A persistent and Concurrent Hashmap For Non-Volatile Memories . In Proceedings of the 3rd VLDB Workshop on In-Memory Data Mangement and Analytics , page 4 . ACM, 2015. D. Schwalb, M. Dreseler, M. Uflacker, and H. Plattner. NVC-Hashmap: A persistent and Concurrent Hashmap For Non-Volatile Memories. In Proceedings of the 3rd VLDB Workshop on In-Memory Data Mangement and Analytics, page 4. ACM, 2015."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature06932"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522713"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196897"},{"key":"e_1_2_1_38_1","first-page":"61","volume-title":"Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory. In 9th USENIX Conference on File and Storage Technologies (FAST 11)","author":"Venkataraman S.","year":"2011","unstructured":"S. Venkataraman , N. Tolia , P. Ranganathan , R. H. Campbell , Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory. In 9th USENIX Conference on File and Storage Technologies (FAST 11) , pages 61 -- 75 , 2011 . S. Venkataraman, N. Tolia, P. Ranganathan, R. H. Campbell, et al. Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory. In 9th USENIX Conference on File and Storage Technologies (FAST 11), pages 61--75, 2011."},{"key":"e_1_2_1_39_1","unstructured":"Viking Technology. DDR4 NVDIMM. 2017. http:\/\/www.vikingtechnology.com\/products\/nvdimm\/ddr4-nvdimm\/.  Viking Technology. DDR4 NVDIMM. 2017. http:\/\/www.vikingtechnology.com\/products\/nvdimm\/ddr4-nvdimm\/."},{"key":"e_1_2_1_40_1","volume-title":"Scalable Logging Through Emerging Non-Volatile Memory. PVLDB, 7(10):865--876","author":"Wang T.","year":"2014","unstructured":"T. Wang and R. Johnson . Scalable Logging Through Emerging Non-Volatile Memory. PVLDB, 7(10):865--876 , 2014 . T. Wang and R. Johnson. Scalable Logging Through Emerging Non-Volatile Memory. PVLDB, 7(10):865--876, 2014."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3015274.3015276"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00049"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2010.2070050"},{"key":"e_1_2_1_44_1","first-page":"349","volume-title":"Proceedings of the 2017 USENIX Annual Technical Conference, USENIX ATC '17","author":"Xia F.","year":"2017","unstructured":"F. Xia , D. Jiang , J. Xiong , and N. Sun . HiKV: A Hybrid Index Key-value Store for DRAM-NVM Memory Systems . In Proceedings of the 2017 USENIX Annual Technical Conference, USENIX ATC '17 , pages 349 -- 362 , 2017 . F. Xia, D. Jiang, J. Xiong, and N. Sun. HiKV: A Hybrid Index Key-value Store for DRAM-NVM Memory Systems. In Proceedings of the 2017 USENIX Annual Technical Conference, USENIX ATC '17, pages 349--362, 2017."},{"key":"e_1_2_1_45_1","first-page":"323","volume-title":"NOVA: A Log-structured File System for Hybrid Volatile\/Non-volatile Main Memories. In 14th USENIX Conference on File and Storage Technologies (FAST 16)","author":"Xu J.","year":"2016","unstructured":"J. Xu and S. Swanson . NOVA: A Log-structured File System for Hybrid Volatile\/Non-volatile Main Memories. In 14th USENIX Conference on File and Storage Technologies (FAST 16) , pages 323 -- 338 , 2016 . J. Xu and S. Swanson. NOVA: A Log-structured File System for Hybrid Volatile\/Non-volatile Main Memories. In 14th USENIX Conference on File and Storage Technologies (FAST 16), pages 323--338, 2016."},{"key":"e_1_2_1_46_1","volume-title":"An Empirical Guide to the Behavior and Use of Scalable Persistent Memory","author":"Yang J.","year":"2019","unstructured":"J. Yang , J. Kim , M. Hoseinzadeh , J. Izraelevitz , and S. Swanson . An Empirical Guide to the Behavior and Use of Scalable Persistent Memory , 2019 . J. Yang, J. Kim, M. Hoseinzadeh, J. Izraelevitz, and S. Swanson. An Empirical Guide to the Behavior and Use of Scalable Persistent Memory, 2019."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2479621"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915222"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2015.7208275"},{"key":"e_1_2_1_50_1","first-page":"461","volume-title":"Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)","author":"Zuo P.","year":"2018","unstructured":"P. Zuo , Y. Hua , and J. Wu . Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18) , pages 461 -- 476 , 2018 . P. Zuo, Y. Hua, and J. Wu. Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pages 461--476, 2018."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3372716.3372728","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:02:12Z","timestamp":1672221732000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3372716.3372728"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,9]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,9]]}},"alternative-id":["10.14778\/3372716.3372728"],"URL":"https:\/\/doi.org\/10.14778\/3372716.3372728","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,12,9]]}}}