{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:49Z","timestamp":1750309489901,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T00:00:00Z","timestamp":1738972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2025,5,31]]},"abstract":"<jats:p>\n            Key-value stores in Cloud environments can contain more than 2\n            <jats:sup>45<\/jats:sup>\n            unique elements and be larger than 100 PByte. B\n            <jats:sup>+<\/jats:sup>\n            -Trees are well suited for these larger-than-memory datasets and seamlessly index data stored on thousands of secondary storage devices. Unfortunately, it is often uneconomical to even store all inner tree nodes in memory for these dataset sizes. Therefore, lookup performance is affected by the additional IOs for reading inner nodes.\n          <\/jats:p>\n          <jats:p>\n            This number of inner nodes can be reduced by increasing the size of leaf nodes. We propose HLN-Trees, which support huge leaf nodes without increasing the IO sizes for individual index operations. They partition leaf nodes in arrays of independent subnodes and combine ideas from BD-trees with rebalancing, learning key deviations, and storing locality predictors. HLN-Trees have been initially designed for uniform random key distributions and support arbitrary key distributions through an additional layer of hashing in leaf nodes. HLN-Trees decrease the number of inner nodes by up to 256\u00d7 for uniform random key distributions and by 16\u00d7 to 64\u00d7 for arbitrary ones compared to B\n            <jats:sup>+<\/jats:sup>\n            -Trees, while keeping their performance at the same level even at high concurrency levels. We show analytically and through real-world and synthetic benchmarks that HLN-Trees also outperform state-of-the-art learned indexes for secondary storage.\n          <\/jats:p>","DOI":"10.1145\/3707641","type":"journal-article","created":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T07:01:58Z","timestamp":1736233318000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["HLN-Tree: A memory-efficient B+-Tree with huge leaf nodes and locality predictors"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3083-2775","authenticated-orcid":false,"given":"Andr\u00e9","family":"Brinkmann","sequence":"first","affiliation":[{"name":"Institute of Computer Science, Johannes Gutenberg University Mainz, Mainz, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3786-7102","authenticated-orcid":false,"given":"Reza","family":"Salkhordeh","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Johannes Gutenberg University Mainz, Mainz, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-5704-3255","authenticated-orcid":false,"given":"Florian","family":"Wiegert","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Johannes Gutenberg University Mainz, Mainz, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1677-4644","authenticated-orcid":false,"given":"Peng","family":"Wang","sequence":"additional","affiliation":[{"name":"Huawei Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5780-7900","authenticated-orcid":false,"given":"Yao","family":"Xin","sequence":"additional","affiliation":[{"name":"Huawei Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0233-5838","authenticated-orcid":false,"given":"Renhai","family":"Chen","sequence":"additional","affiliation":[{"name":"Huawei Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-5496-5522","authenticated-orcid":false,"given":"Huang","family":"Keji","sequence":"additional","affiliation":[{"name":"Huawei Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0283-7050","authenticated-orcid":false,"given":"Gong","family":"Zhang","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co Ltd, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142548"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526121"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733094"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00061-8"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196896"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375681"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1457838.1457895"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.04.015"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_3_2_14_2","article-title":"The FNV Non-cryptographic Hash Algorithm, Version 17","author":"Fowler Glenn","year":"2019","unstructured":"Glenn Fowler, Landon Curt Noll, Kiem-Phong Vo, Donald Eastlake, and Tony Hansen. 2019. The FNV Non-cryptographic Hash Algorithm, Version 17. Internet Draft, Network Working Group. (May2019).","journal-title":"Internet Draft, Network Working Group"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462078"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806908"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1561\/1900000028"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2338626.2338630"},{"key":"e_1_3_2_19_2","unstructured":"Mikio Hirabayashi. 2020. Tkrzw: A Set of Implementations of DBM. https:\/\/dbmx.net\/tkrzw\/"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0406-1"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICIS.2010.9"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/151284.151286"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2016.7897082"},{"key":"e_1_3_2_24_2","article-title":"SOSD: A benchmark for learned indexes","volume":"1911","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2019. SOSD: A benchmark for learned indexes. CoRR abs\/1911.13014 (2019). http:\/\/arxiv.org\/abs\/1911.13014","journal-title":"CoRR"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/080728743"},{"key":"e_1_3_2_26_2","unstructured":"Youngjae Lee and Jinglei Ren. 2023. YCSB-cpp: YCSB Written in C++ for LevelDB RocksDB and LMDB. https:\/\/github.com\/ls4154\/YCSB-cpp"},{"key":"e_1_3_2_27_2","first-page":"99","volume-title":"21st USENIX Conference on File and Storage Technologies (FAST)","author":"Li Pengfei","year":"2023","unstructured":"Pengfei Li, Yu Hua, Pengfei Zuo, Zhangyu Chen, and Jiajie Sheng. 2023. ROLEX: A scalable RDMA-oriented learned key-value store for disaggregated memory systems. In 21st USENIX Conference on File and Storage Technologies (FAST). 99\u2013114."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920990"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1986.7266204"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3588962"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/49346.50067"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2019.00-20"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3033273"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.14778\/3570690.3570704"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319870"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/356643.356645"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2485732.2485748"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2018.03.002"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_10"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49543-6_13"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.14778\/2095686.2095688"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300075"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00054"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289075"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.14778\/3561261.3561270"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483551"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380583"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3654954"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3654948"},{"key":"e_1_3_2_52_2","first-page":"375","volume-title":"16th USENIX Symposium on Operating Systems Design and Implementation (OSDI)","author":"Zhong Yuhong","year":"2022","unstructured":"Yuhong Zhong, Haoyu Li, Yu Jian Wu, Ioannis Zarkadas, Jeffrey Tao, Evan Mesterhazy, Michael Makris, Junfeng Yang, Amy Tai, Ryan Stutsman, et al.2022. XRP: In-kernel storage functions with eBPF. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 375\u2013393."},{"key":"e_1_3_2_53_2","first-page":"269","volume-title":"6th USENIX Conference on File and Storage Technologies (FAST)","author":"Zhu Benjamin","year":"2008","unstructured":"Benjamin Zhu, Kai Li, and R. Hugo Patterson. 2008. Avoiding the disk bottleneck in the data domain deduplication file system. In 6th USENIX Conference on File and Storage Technologies (FAST). 269\u2013282."}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707641","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3707641","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:38Z","timestamp":1750295858000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707641"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,8]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,5,31]]}},"alternative-id":["10.1145\/3707641"],"URL":"https:\/\/doi.org\/10.1145\/3707641","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2025,2,8]]},"assertion":[{"value":"2024-02-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-31","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}