{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T22:41:05Z","timestamp":1780094465461,"version":"3.54.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,1,29]],"date-time":"2022-01-29T00:00:00Z","timestamp":1643414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61902242, 61925206, 62132014"],"award-info":[{"award-number":["61902242, 61925206, 62132014"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"HighTech Support Program from Shanghai Committee of Science and Technology","award":["20ZR1428100"],"award-info":[{"award-number":["20ZR1428100"]}]},{"name":"National Key Research and Development Program of China","award":["2020AAA0108500"],"award-info":[{"award-number":["2020AAA0108500"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2022,2,28]]},"abstract":"<jats:p>\n                    We present XIndex, which is a concurrent index library and designed for fast queries. It includes a concurrent ordered index (XIndex-R) and a concurrent hash index (XIndex-H). Similar to a recent proposal of the learned index, the indexes in XIndex use learned models to optimize index efficiency. Compared with the learned index, for the ordered index, XIndex-R is able to handle concurrent writes effectively and adapts its structure according to runtime workload characteristics. For the hash index, XIndex-H is able to avoid the resize operation blocking concurrent writes. Furthermore, the indexes in XIndex can index string keys much more efficiently than the learned index. We demonstrate the advantages of XIndex with YCSB, TPC-C (KV), which is a TPC-C-inspired benchmark for key-value stores, and micro-benchmarks. Compared with ordered indexes of Masstree and Wormhole, XIndex-R achieves up to 3.2\u00d7 and 4.4\u00d7 performance improvement on a 24-core machine. Compared with hash indexes of Intel TBB HashMap, XIndex-H achieves up to 3.1\u00d7 speedup. The performance further improves by 91% after adding the optimizations on indexing string keys. The library is open-sourced.\n                    <jats:xref ref-type=\"fn\">\n                      <jats:sup>1<\/jats:sup>\n                    <\/jats:xref>\n                  <\/jats:p>","DOI":"10.1145\/3478289","type":"journal-article","created":{"date-parts":[[2022,1,29]],"date-time":"2022-01-29T14:07:01Z","timestamp":1643465221000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["The Concurrent Learned Indexes for Multicore Data Storage"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0220-5726","authenticated-orcid":false,"given":"Zhaoguo","family":"Wang","sequence":"first","affiliation":[{"name":"Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University and Shanghai AI Laboratory and Engineering Research Center for Domain-specific Operating Systems, Ministry of Education, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haibo","family":"Chen","sequence":"additional","affiliation":[{"name":"Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University and Shanghai AI Laboratory and Engineering Research Center for Domain-specific Operating Systems, Ministry of Education, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Youyun","family":"Wang","sequence":"additional","affiliation":[{"name":"Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University and Shanghai AI Laboratory and Engineering Research Center for Domain-specific Operating Systems, Ministry of Education, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7757-5708","authenticated-orcid":false,"given":"Chuzhe","family":"Tang","sequence":"additional","affiliation":[{"name":"Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University and Shanghai AI Laboratory and Engineering Research Center for Domain-specific Operating Systems, Ministry of Education, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huan","family":"Wang","sequence":"additional","affiliation":[{"name":"Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University and Shanghai AI Laboratory and Engineering Research Center for Domain-specific Operating Systems, Ministry of Education, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,29]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/3154690.3154725"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263762"},{"key":"e_1_3_2_4_2","article-title":"STX B+ Tree C++ Template Classes","author":"Bingmann Timo","year":"2013","unstructured":"Timo Bingmann. 2013. STX B+ Tree C++ Template Classes. https:\/\/panthema.net\/2007\/stx-btree\/. (2013).","journal-title":"https:\/\/panthema.net\/2007\/stx-btree\/"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196896"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375681"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_61"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1837853.1693488"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1837853.1693488"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672375"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840441"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/3489146.3489201"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2248487.2150998"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2248487.2150998"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/3488766.3488775"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556575"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463710"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/800212.806505"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/285243.285287"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_3_2_24_2","article-title":"OpenStreetMap on AWS","author":"Foundation OpenStreetMap","unstructured":"OpenStreetMap Foundation. 2019. OpenStreetMap on AWS. https:\/\/aws.amazon.com\/public-datasets\/osm. Accessed: 2019-4-24.","journal-title":"https:\/\/aws.amazon.com\/public-datasets\/osm"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/367390.367400"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2338626.2338630"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2656332"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"issue":"3","key":"e_1_3_2_30_2","first-page":"64","article-title":"The periodic table of data structures","volume":"41","author":"Idreos Stratos","year":"2018","unstructured":"Stratos Idreos, Kostas Zoumpatianos, Manos Athanassoulis, Niv Dayan, Brian Hentschel, Michael S. Kester, Demi Guo, Lukas M. Maas, Wilson Qin, Abdul Wasay, and Yiyou Sun. 2018. The periodic table of data structures. IEEE Data Eng. Bull. 41, 3 (2018), 64\u201375. http:\/\/sites.computer.org\/debull\/A18sept\/p64.pdf.","journal-title":"IEEE Data Eng. Bull."},{"issue":"2","key":"e_1_3_2_31_2","first-page":"47","article-title":"Learning data structure alchemy","volume":"42","author":"Idreos Stratos","year":"2019","unstructured":"Stratos Idreos, Kostas Zoumpatianos, Subarna Chatterjee, Wilson Qin, Abdul Wasay, Brian Hentschel, Mike S. Kester, Niv Dayan, Demi Guo, Minseo Kang, and Yiyou Sun. 2019. Learning data structure alchemy. IEEE Data Eng. Bull. 42, 2 (2019), 47\u201358. http:\/\/sites.computer.org\/debull\/A19june\/p47.pdf.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3199671"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/3277355.3277450"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_3_2_35_2","volume-title":"CIDR 2019, 9th Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 13-16, 2019, Online Proceedings","author":"Kraska Tim","year":"2019","unstructured":"Tim Kraska, Mohammad Alizadeh, Alex Beutel, Ed H. Chi, Ani Kristo, Guillaume Leclerc, Samuel Madden, Hongzi Mao, and Vikram Nathan. 2019. SageDB: A learned database system. In CIDR 2019, 9th Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 13-16, 2019, Online Proceedings. www.cidrdb.org. http:\/\/cidrdb.org\/cidr2019\/papers\/p117-kraska-cidr19.pdf."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/319566.319567"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/359863.359878"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359628"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557077"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_3_2_43_2","article-title":"A scalable learned index scheme in storage systems","volume":"1905","author":"Li Pengfei","year":"2019","unstructured":"Pengfei Li, Yu Hua, Pengfei Zuo, and Jingnan Jia. 2019. A scalable learned index scheme in storage systems. CoRR abs\/1905.06256 (2019). arXiv:1905.06256 http:\/\/arxiv.org\/abs\/1905.06256.","journal-title":"CoRR"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.5555\/2930583.2930594"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_3_2_47_2","first-page":"509","volume-title":"Parallel and Distributed Computing and Systems","author":"Mckenney Paul","year":"1998","unstructured":"Paul Mckenney and John Slingwine. 1998. Read-copy update: Using execution history to solve concurrency problems. In Parallel and Distributed Computing and Systems. 509\u2013518."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/128765.128770"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3267809.3267824"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.5555\/1352079.1352134"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.5555\/1768570.1768582"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2007.4401029"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147958"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522713"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592804"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303955"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.5555\/3489146.3489148"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915222"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_3_2_63_2","first-page":"465","volume-title":"11th USENIX Symposium on Operating Systems Design and Implementation, OSDI\u201914, Broomfield, CO, USA, October 6-8, 2014","author":"Zheng Wenting","year":"2014","unstructured":"Wenting Zheng, Stephen Tu, Eddie Kohler, and Barbara Liskov. 2014. Fast databases with fast durability and recovery through multicore parallelism. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI\u201914, Broomfield, CO, USA, October 6-8, 2014, Jason Flinn and Hank Levy (Eds.). USENIX Association, 465\u2013477. https:\/\/www.usenix.org\/conference\/osdi14\/technical-sessions\/presentation\/zheng_wenting."}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3478289","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3478289","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T15:31:33Z","timestamp":1750174293000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3478289"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,29]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2,28]]}},"alternative-id":["10.1145\/3478289"],"URL":"https:\/\/doi.org\/10.1145\/3478289","relation":{"is-referenced-by":[{"id-type":"doi","id":"10.1007\/s10619-026-07460-8","asserted-by":"object"}]},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,29]]},"assertion":[{"value":"2020-08-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":"2022-01-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}