{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T05:13:19Z","timestamp":1767849199352,"version":"3.49.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2021,9,17]],"date-time":"2021-09-17T00:00:00Z","timestamp":1631836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"crossref","award":["62072419"],"award-info":[{"award-number":["62072419"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>The advance of byte-addressable persistent memory (PM) makes it a hot topic to revisit traditional tree indices such as B+-tree and radix tree, and a few new persistent memory-friendly tree indices have been proposed. However, due to the special features of persistent memory compared to DRAM and the limitations of B+-tree-like indices, it is much harder to optimize both search and write performance for tree indices on persistent memory. As a result, most existing indices for persistent memory, e.g., WB-tree, proposed to improve write performance while sacrificing search performance. Aiming to optimize both write and search performance for tree indices on persistent memory, in this paper, we first propose a novel Two-Layer Architecture (TLA) for constructing tree indices on persistent memory. The key idea, of TLA is to organize the index with a search-optimized top layer and a write-optimized bottom layer, letting the top layer optimize search performance and the bottom layer improve write performance. By adopting efficient structures for the two layers, TLA can boost both write and search performance for tree indices on persistent memory. Following the TLA architecture, we present a new index called TLBtree (Two-Layer B+-tree) offering high search and write performance for persistent memory. Moreover, we develop a concurrent TLBtree to support non-blocking read operations in multi-core environment. We evaluate our proposals under a server equipped with real Intel Optane persistent memory. The results show that TLBtree outperforms the state-of-the-art tree indices, including WB-tree, Fast&amp;Fair, and FPTree, in both search and write performance. Also, the concurrent TLBtree can achieve up to 3.7x speedup than its competitors under the multi-core environment.<\/jats:p>","DOI":"10.1145\/3476981","type":"journal-article","created":{"date-parts":[[2021,9,17]],"date-time":"2021-09-17T18:36:51Z","timestamp":1631903811000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Two Birds With One Stone: Boosting Both Search and Write Performance for Tree Indices on Persistent Memory"],"prefix":"10.1145","volume":"20","author":[{"given":"Yongping","family":"Luo","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei, China"}]},{"given":"Peiquan","family":"Jin","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei, China"}]},{"given":"Zhou","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei, China"}]},{"given":"Junchen","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei, China"}]},{"given":"Bin","family":"Cheng","sequence":"additional","affiliation":[{"name":"Tencent Inc., Shenzhen, China"}]},{"given":"Qinglin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Tencent Inc., Shenzhen China"}]}],"member":"320","published-online":{"date-parts":[[2021,9,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3164147"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3131848"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394025"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672375"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752947"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407850"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806908"},{"key":"e_1_2_1_9_1","unstructured":"Brendan D. Gregg. 2020. Linux Perf Examples. http:\/\/www.brendangregg.com\/perf.html.  Brendan D. Gregg. 2020. Linux Perf Examples. http:\/\/www.brendangregg.com\/perf.html."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3446095.3446101"},{"key":"e_1_2_1_11_1","volume-title":"Dasfaa","author":"Huang Chenchen","unstructured":"Chenchen Huang , Huiqi Hu , and Aoying Zhou . 2021. BPTree: An optimized index with batch persistence on optane DC PM . In Dasfaa . Springer , Taipei, Taiwan , 478\u2013486. Chenchen Huang, Huiqi Hu, and Aoying Zhou. 2021. BPTree: An optimized index with batch persistence on optane DC PM. In Dasfaa. Springer, Taipei, Taiwan, 478\u2013486."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/3189759.3189777"},{"key":"e_1_2_1_13_1","volume-title":"Transactional Synchronization With Intel Core 4th Generation Processor","unstructured":"Intel. 2012. Transactional Synchronization With Intel Core 4th Generation Processor . Intel. 2012. Transactional Synchronization With Intel Core 4th Generation Processor."},{"key":"e_1_2_1_14_1","unstructured":"Intel. 2015. Intel 64 and IA-32 Architectures Software Developer\u2019s Manual.  Intel. 2015. Intel 64 and IA-32 Architectures Software Developer\u2019s Manual."},{"key":"e_1_2_1_15_1","unstructured":"Intel. 2020. Intel Optane Technology. https:\/\/www.intel.com\/content\/www\/us\/en\/architecture-and-technology\/intel-optane-technology.html.  Intel. 2020. Intel Optane Technology. https:\/\/www.intel.com\/content\/www\/us\/en\/architecture-and-technology\/intel-optane-technology.html."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335449"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129263"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-020-07288-w"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359635"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933349.2933352"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384355"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2018.00029"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389134"},{"key":"e_1_2_1_25_1","volume-title":"ICA3PP","author":"Luo Yongping","unstructured":"Yongping Luo , Zhaole Chu , Peiquan Jin , and Shouhong Wan . 2020. Efficient sorting and join on NVM-based hybrid memory . In ICA3PP . Springer , New York, USA , 15\u201330. Yongping Luo, Zhaole Chu, Peiquan Jin, and Shouhong Wan. 2020. Efficient sorting and join on NVM-based hybrid memory. In ICA3PP. Springer, New York, USA, 15\u201330."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196908"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915251"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2678373.2665712"},{"key":"e_1_2_1_30_1","volume-title":"Nvm malloc: Memory allocation for NVRAM.Adms@Vldb 15","author":"Schwalb David","year":"2015","unstructured":"David Schwalb , Tim Berning , Martin Faust , Markus Dreseler , and Hasso Plattner . 2015. Nvm malloc: Memory allocation for NVRAM.Adms@Vldb 15 ( 2015 ), 61\u201372. David Schwalb, Tim Berning, Martin Faust, Markus Dreseler, and Hasso Plattner. 2015. Nvm malloc: Memory allocation for NVRAM.Adms@Vldb 15 (2015), 61\u201372."},{"key":"e_1_2_1_31_1","unstructured":"UNIST Data Intensive Computing Lab. 2020. FAST&FAIR Source Code. https:\/\/github.com\/DICL\/FAST_FAIR.  UNIST Data Intensive Computing Lab. 2020. FAST&FAIR Source Code. https:\/\/github.com\/DICL\/FAST_FAIR."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3329785.3329930"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1960475.1960480"},{"key":"e_1_2_1_34_1","volume-title":"Icde","author":"Wang Tianzheng","unstructured":"Tianzheng Wang , Justin J. Levandoski , and Per-\u00c5ke Larson . 2018. Easy lock-free indexing in non-volatile memory . In Icde . IEEE Computer Society , Paris, France , 461\u2013472. Tianzheng Wang, Justin J. Levandoski, and Per-\u00c5ke Larson. 2018. Easy lock-free indexing in non-volatile memory. In Icde. IEEE Computer Society, Paris, France, 461\u2013472."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/3154690.3154724"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386708"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2750482.2750495"},{"key":"e_1_2_1_38_1","volume-title":"Ispa","author":"Yang Liu","unstructured":"Liu Yang , Peiquan Jin , and Shouhong Wan . 2019. BF-Join: An efficient hash join algorithm for DRAM-NVM-Based hybrid memory systems . In Ispa . IEEE , Xiamen, China , 875\u2013882. Liu Yang, Peiquan Jin, and Shouhong Wan. 2019. BF-Join: An efficient hash join algorithm for DRAM-NVM-Based hybrid memory systems. In Ispa. IEEE, Xiamen, China, 875\u2013882."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915222"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372717"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476981","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476981","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:46Z","timestamp":1750188646000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476981"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,17]]},"references-count":40,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3476981"],"URL":"https:\/\/doi.org\/10.1145\/3476981","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,17]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}