{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T06:52:40Z","timestamp":1770533560053,"version":"3.49.0"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T00:00:00Z","timestamp":1764288000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T00:00:00Z","timestamp":1764288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["2337806"],"award-info":[{"award-number":["2337806"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    B-trees are widely recognized as one of the most important index structures in database systems, providing efficient query processing capabilities. Over the past few decades, many techniques have been developed to enhance the efficiency of B-trees from various perspectives. Among them,\n                    <jats:italic>B-tree compression<\/jats:italic>\n                    is an important technique introduced as early as the 1970s to improve both space efficiency and query performance. Since then, several B-tree compression techniques have been developed. However, to our surprise, we have found that these B-tree compression techniques were\n                    <jats:italic>never<\/jats:italic>\n                    compared against each other in prior works. Consequently, many important questions remain unanswered, such as whether B-tree compression is truly effective or not. If it is effective, under what scenarios and which B-tree compression methods should be employed? In this paper, we conduct an experimental evaluation of seven widely used B-tree compression techniques using both synthetic and real datasets. Based on our evaluation, we present lessons and insights regarding the use of B-tree compression that can be leveraged to guide system design decisions in modern databases.\n                  <\/jats:p>","DOI":"10.1007\/s00778-025-00950-8","type":"journal-article","created":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T02:01:07Z","timestamp":1764295267000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Evaluation of B-tree Compression Techniques"],"prefix":"10.1007","volume":"35","author":[{"given":"Sikang","family":"Sun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chuqing","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shreya","family":"Ballijepalli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3039-1175","authenticated-orcid":false,"given":"Jianguo","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,11,28]]},"reference":[{"key":"950_CR1","unstructured":"Key Normalization (https:\/\/wiki.postgresql.org\/wiki\/Key_normalization)"},{"key":"950_CR2","unstructured":"Webspam-uk2007 dataset (2007). https:\/\/chato.cl\/webspam\/datasets\/uk2007\/"},{"key":"950_CR3","unstructured":"Snap memetracker dataset (2008). https:\/\/www.kaggle.com\/datasets\/snap\/snap-memetracker"},{"key":"950_CR4","unstructured":"The default page size change of sqlite 3.12.0 (2022). https:\/\/www.sqlite.org\/pgszchng2016.html"},{"key":"950_CR5","unstructured":"Source code of wiredtiger\u2019s b-tree implementation (2022). https:\/\/github.com\/wiredtiger\/wiredtiger\/tree\/develop\/src\/btree"},{"key":"950_CR6","unstructured":"CREATE INDEX Statement in SAP HANA (https:\/\/help.sap.com\/docs\/SAP_HANA_PLATFORM\/4fe29514fd584807ac9f2a04f6754767\/20d44b4175191014a940afff4b47c7ea.html) (2023)"},{"key":"950_CR7","unstructured":"Database page layout in postgresql 16 (2023). https:\/\/www.postgresql.org\/docs\/current\/storage-page-layout.html"},{"key":"950_CR8","unstructured":"Myisam source code in mysql (2023). https:\/\/github.com\/mysql\/mysql-server\/tree\/a246bad76b9271cb4333634e954040a970222e0a\/storage\/myisam"},{"key":"950_CR9","unstructured":"Mysql reference manual (2023). https:\/\/dev.mysql.com\/doc\/refman\/8.0\/en\/key-space.html#:~:text=Prefix%20compression%20is%20used%20on,when%20you%20create%20the%20table"},{"key":"950_CR10","unstructured":"Tpc-h benchmark (2023). https:\/\/www.tpc.org\/tpch\/"},{"key":"950_CR11","unstructured":"Wikipedia articles titles (2023). https:\/\/dumps.wikimedia.org\/enwiki\/latest\/"},{"key":"950_CR12","unstructured":"Wiredtiger documentation (2023). https:\/\/source.wiredtiger.com\/11.1.0\/file_formats.html#file_formats_compression"},{"key":"950_CR13","doi-asserted-by":"crossref","unstructured":"Abadi, D.J., Madden, S., Ferreira, M.: Integrating compression and execution in column-oriented database systems. In: SIGMOD, pp. 671\u2013682 (2006)","DOI":"10.1145\/1142473.1142548"},{"key":"950_CR14","unstructured":"Al-Mamun, A., Wu, H., He, Q., Wang, J., Aref, W.G.: A Survey of Learned Indexes for the Multi-dimensional Space. CoRR abs\/2403.06456 (2024)"},{"issue":"1","key":"950_CR15","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/s007780050031","volume":"6","author":"G Antoshenkov","year":"1997","unstructured":"Antoshenkov, G.: Dictionary-Based Order-Preserving String Compression. VLDB J. 6(1), 26\u201339 (1997)","journal-title":"VLDB J."},{"key":"950_CR16","doi-asserted-by":"crossref","unstructured":"Antoshenkov, G., Lomet, D., Murray, J.: Order Preserving String Compression. In: ICDE, pp. 655\u2013663 (1996)","DOI":"10.1109\/ICDE.1996.492216"},{"key":"950_CR17","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.M.: Organization and Maintenance of Large Ordered Indices. Acta Informatica 1, 173\u2013189 (1972)","journal-title":"Acta Informatica"},{"issue":"1","key":"950_CR18","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/320521.320530","volume":"2","author":"R Bayer","year":"1977","unstructured":"Bayer, R., Unterauer, K.: Prefix B-Trees. ACM Transactions on Database Systems (TODS) 2(1), 11\u201326 (1977)","journal-title":"ACM Transactions on Database Systems (TODS)"},{"issue":"2","key":"950_CR19","first-page":"1462","volume":"2","author":"B Bhattacharjee","year":"2009","unstructured":"Bhattacharjee, B., Lim, L., Malkemus, T., Mihaila, G.A., Ross, K.A., Lau, S., McCarthur, C., Toth, Z., Sherkat, R.: Efficient Index Compression in DB2 LUW. VLDB 2(2), 1462\u20131473 (2009)","journal-title":"VLDB"},{"key":"950_CR20","doi-asserted-by":"crossref","unstructured":"Binnig, C., Hildenbrand, S., F\u00e4rber, F.: Dictionary-based Order-preserving String Compression for Main Memory Column Stores. In: SIGMOD, pp. 283\u2013296 (2009)","DOI":"10.1145\/1559845.1559877"},{"key":"950_CR21","doi-asserted-by":"crossref","unstructured":"Bohannon, P., McIlroy, P., Rastogi, R.: Main-Memory Index Structures with Fixed-Size Partial Keys. In: S.\u00a0Mehrotra, T.K. Sellis (eds.) SIGMOD, pp. 163\u2013174 (2001)","DOI":"10.1145\/375663.375681"},{"key":"950_CR22","unstructured":"Breddemann, L.: What is cpb+-tree in sap hana? (2020). https:\/\/www.lbreddemann.org\/what-is-cpb-tree-in-sap-hana\/"},{"key":"950_CR23","doi-asserted-by":"crossref","unstructured":"Bumbulis, P., Bowman, I.T.: A Compact B-tree. In: SIGMOD, pp. 533\u2013541 (2002)","DOI":"10.1145\/564691.564753"},{"key":"950_CR24","unstructured":"Canadi, I.: Converged index: The secret sauce behind rockset\u2019s fast queries (2019). https:\/\/rockset.com\/blog\/converged-indexing-the-secret-sauce-behind-rocksets-fast-queries\/"},{"key":"950_CR25","doi-asserted-by":"crossref","unstructured":"Chen, Z., Gehrke, J., Korn, F.: Query Optimization In Compressed Database Systems. In: SIGMOD, pp. 271\u2013282 (2001)","DOI":"10.1145\/375663.375692"},{"key":"950_CR26","unstructured":"Christman, G.: Compression features included with oracle database enterprise edition (2022). https:\/\/blogs.oracle.com\/dbstorage\/post\/compression-features-included-with-oracle-database-enterprise-edition"},{"issue":"2","key":"950_CR27","first-page":"121","volume":"11","author":"D Comer","year":"1979","unstructured":"Comer, D.: The Ubiquitous B-Tree. CSUR 11(2), 121\u2013137 (1979)","journal-title":"The Ubiquitous B-Tree. CSUR"},{"key":"950_CR28","doi-asserted-by":"crossref","unstructured":"Diaconu, C., Freedman, C., Ismert, E., Larson, P., Mittal, P., Stonecipher, R., Verma, N., Zwilling, M.: Hekaton: SQL server\u2019s memory-optimized OLTP engine. In: SIGMOD, pp. 1243\u20131254 (2013)","DOI":"10.1145\/2463676.2463710"},{"key":"950_CR29","doi-asserted-by":"crossref","unstructured":"Ding, J., Minhas, U.F., Yu, J., Wang, C., Do, J., Li, Y., Zhang, H., Chandramouli, B., Gehrke, J., Kossmann, D., Lomet, D.B., Kraska, T.: ALEX: An Updatable Adaptive Learned Index. In: SIGMOD, pp. 969\u2013984 (2020)","DOI":"10.1145\/3318464.3389711"},{"key":"950_CR30","doi-asserted-by":"crossref","unstructured":"Gao, C., Ballijepalli, S., Wang, J.: Revisiting B-tree Compression: An Experimental Study. Proc. ACM Manag. Data 2(3), 169:1\u2013169:25 (2024)","DOI":"10.1145\/3654972"},{"key":"950_CR31","doi-asserted-by":"crossref","unstructured":"Graefe, G.: A Survey of B-tree Locking Techniques. TODS 35(3), 16:1\u201316:26 (2010)","DOI":"10.1145\/1806907.1806908"},{"issue":"4","key":"950_CR32","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1561\/1900000028","volume":"3","author":"G Graefe","year":"2011","unstructured":"Graefe, G.: Modern B-Tree Techniques. Foundations and Trends in Databases 3(4), 203\u2013402 (2011)","journal-title":"Foundations and Trends in Databases"},{"key":"950_CR33","doi-asserted-by":"crossref","unstructured":"Graefe, G., Larson, P.: B-Tree Indexes and CPU Caches. In: ICDE, pp. 349\u2013358 (2001)","DOI":"10.1109\/ICDE.2001.914847"},{"key":"950_CR34","doi-asserted-by":"publisher","unstructured":"Hankins, R.A., Patel, J.M.: Effect of node size on the performance of cache-conscious b+-trees. In: Proceedings of the 2003 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS \u201903, p. 283-294. Association for Computing Machinery, New York, NY, USA (2003). https:\/\/doi.org\/10.1145\/781027.781063","DOI":"10.1145\/781027.781063"},{"key":"950_CR35","unstructured":"Hao, X., Lamb, A.: Using stringview \/ german style strings to make queries faster: Part 1- reading parquet (2024). https:\/\/datafusion.apache.org\/blog\/2024\/09\/13\/string-view-german-style-strings-part-1\/"},{"issue":"2","key":"950_CR36","doi-asserted-by":"publisher","first-page":"1496","DOI":"10.14778\/1454159.1454211","volume":"1","author":"R Kallman","year":"2008","unstructured":"Kallman, R., Kimura, H., Natkins, J., Pavlo, A., Rasin, A., Zdonik, S.B., Jones, E.P.C., Madden, S., Stonebraker, M., Zhang, Y., Hugg, J., Abadi, D.J.: H-store: A High-performance, Distributed Main memory Transaction Processing System. Proc. VLDB Endow. 1(2), 1496\u20131499 (2008)","journal-title":"Proc. VLDB Endow."},{"key":"950_CR37","doi-asserted-by":"crossref","unstructured":"Kim, C., Chhugani, J., Satish, N., Sedlar, E., Nguyen, A.D., Kaldewey, T., Lee, V.W., Brandt, S.A., Dubey, P.: FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs. In: SIGMOD, pp. 339\u2013350 (2010)","DOI":"10.1145\/1807167.1807206"},{"key":"950_CR38","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.is.2016.07.004","volume":"62","author":"S Kim","year":"2016","unstructured":"Kim, S., Lee, J., Satti, S.R., Moon, B.: SBH: Super Byte-aligned Hybrid Bitmap Compression. Inf. Syst. 62, 155\u2013168 (2016)","journal-title":"Inf. Syst."},{"key":"950_CR39","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 3: Sorting and Searching, The Art of Computer Programming, vol.\u00a03, 2nd edn. Addison-Wesley, Reading, Massachusetts (1998)"},{"key":"950_CR40","doi-asserted-by":"crossref","unstructured":"Kraska, T., Beutel, A., Chi, E.H., Dean, J., Polyzotis, N.: The Case for Learned Index Structures. In: SIGMOD, pp. 489\u2013504 (2018)","DOI":"10.1145\/3183713.3196909"},{"key":"950_CR41","doi-asserted-by":"crossref","unstructured":"Lang, H., Beischl, A., Leis, V., Boncz, P.A., Neumann, T., Kemper, A.: Tree-Encoded Bitmaps. In: SIGMOD, pp. 937\u2013967 (2020)","DOI":"10.1145\/3318464.3380588"},{"key":"950_CR42","doi-asserted-by":"publisher","unstructured":"Leis, V., Kemper, A., Neumann, T.: The adaptive radix tree: Artful indexing for main-memory databases. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 38\u201349 (2013). https:\/\/doi.org\/10.1109\/ICDE.2013.6544812","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"950_CR43","doi-asserted-by":"crossref","unstructured":"Levandoski, J.J., Lomet, D.B., Sengupta, S.: The Bw-Tree: A B-tree for New Hardware Platforms. In: ICDE, pp. 302\u2013313 (2013)","DOI":"10.1109\/ICDE.2013.6544834"},{"issue":"11","key":"950_CR44","first-page":"2586","volume":"14","author":"C Liu","year":"2021","unstructured":"Liu, C., Jiang, H., Paparrizos, J., Elmore, A.J.: Decomposed Bounded Floats for Fast Compression and Queries. PVLDB 14(11), 2586\u20132598 (2021)","journal-title":"PVLDB"},{"key":"950_CR45","doi-asserted-by":"crossref","unstructured":"Liu, C., Umbenhower, M., Jiang, H., Subramaniam, P., Ma, J., Elmore, A.J.: Mostly Order Preserving Dictionaries. In: ICDE, pp. 1214\u20131225 (2019)","DOI":"10.1109\/ICDE.2019.00111"},{"issue":"3","key":"950_CR46","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1145\/603867.603878","volume":"30","author":"DB Lomet","year":"2001","unstructured":"Lomet, D.B.: The Evolution of Effective B-tree: Page Organization and Techniques: A Personal Account. SIGMOD Record 30(3), 64\u201369 (2001)","journal-title":"SIGMOD Record"},{"key":"950_CR47","unstructured":"Neumann, T., Freitag, M.J.: Umbra: A Disk-Based System with In-Memory Performance. In: Conference on Innovative Data Systems Research (CIDR) (2020)"},{"issue":"12","key":"950_CR48","first-page":"1816","volume":"8","author":"T Pelkonen","year":"2015","unstructured":"Pelkonen, T., Franklin, S., Cavallaro, P., Huang, Q., Meza, J., Teller, J., Veeraraghavan, K.: Gorilla: A Fast, Scalable. In-Memory Time Series Database. PVLDB 8(12), 1816\u20131827 (2015)","journal-title":"In-Memory Time Series Database. PVLDB"},{"issue":"1","key":"950_CR49","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/s13222-022-00409-y","volume":"22","author":"J Schmei\u00dfer","year":"2022","unstructured":"Schmei\u00dfer, J., Sch\u00fcle, M.E., Leis, V., Neumann, T., Kemper, A.: B$$ ^{\\text{2 }}$$-Tree: Page-Based String Indexing in Concurrent Environments. Datenbank-Spektrum 22(1), 11\u201322 (2022)","journal-title":"Datenbank-Spektrum"},{"key":"950_CR50","doi-asserted-by":"crossref","unstructured":"Theodorakis, G., Clarkson, J., Webber, J.: An Empirical Evaluation of Variable-length Record B+Trees on a Modern Graph Database System. In: International Conference on Data Engineering Workshops (ICDEW), pp. 343\u2013349 (2024)","DOI":"10.1109\/ICDEW61823.2024.00051"},{"key":"950_CR51","doi-asserted-by":"crossref","unstructured":"Wang, J., Lin, C., Papakonstantinou, Y., Swanson, S.: An Experimental Study of Bitmap Compression vs. Inverted List Compression. In: SIGMOD, pp. 993\u20131008 (2017)","DOI":"10.1145\/3035918.3064007"},{"key":"950_CR52","doi-asserted-by":"crossref","unstructured":"Wang, Z., Pavlo, A., Lim, H., Leis, V., Zhang, H., Kaminsky, M., Andersen, D.G.: Building a Bw-Tree Takes More Than Just Buzz Words. In: SIGMOD, pp. 473\u2013488 (2018)","DOI":"10.1145\/3183713.3196895"},{"issue":"1","key":"950_CR53","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1132863.1132864","volume":"31","author":"K Wu","year":"2006","unstructured":"Wu, K., Otoo, E.J., Shoshani, A.: Optimizing Bitmap Indices with Efficient Compression. TODS 31(1), 1\u201338 (2006)","journal-title":"TODS"},{"key":"950_CR54","doi-asserted-by":"publisher","unstructured":"Xu, H., Li, A., Wheatman, B., Marneni, M., Pandey, P.: Bp-tree: Overcoming the point-range operation tradeoff for in-memory b-trees. Proc. VLDB Endow. 16(11), 2976-2989 (2023).https:\/\/doi.org\/10.14778\/3611479.3611502","DOI":"10.14778\/3611479.3611502"},{"issue":"12","key":"950_CR55","first-page":"2059","volume":"12","author":"C Zhan","year":"2019","unstructured":"Zhan, C., Su, M., Wei, C., Peng, X., Lin, L., Wang, S., Chen, Z., Li, F., Pan, Y., Zheng, F., Chai, C.: AnalyticDB: Real-time OLAP Database System at Alibaba Cloud. VLDB 12(12), 2059\u20132070 (2019)","journal-title":"VLDB"},{"key":"950_CR56","doi-asserted-by":"crossref","unstructured":"Zhang, F., Wan, W., Zhang, C., Zhai, J., Chai, Y., Li, H., Du, X.: CompressDB: Enabling Efficient Compressed Data Direct Processing for Various Databases. In: SIGMOD, pp. 1655\u20131669 (2022)","DOI":"10.1145\/3514221.3526130"},{"issue":"2","key":"950_CR57","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00778-020-00636-3","volume":"30","author":"F Zhang","year":"2021","unstructured":"Zhang, F., Zhai, J., Shen, X., Wang, D., Chen, Z., Mutlu, O., Chen, W., Du, X.: TADOC: Text Analytics Directly on Compression. VLDB J. 30(2), 163\u2013188 (2021)","journal-title":"VLDB J."},{"key":"950_CR58","doi-asserted-by":"crossref","unstructured":"Zhang, H., Andersen, D.G., Pavlo, A., Kaminsky, M., Ma, L., Shen, R.: Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes. In: SIGMOD, pp. 1567\u20131581 (2016)","DOI":"10.1145\/2882903.2915222"},{"key":"950_CR59","doi-asserted-by":"crossref","unstructured":"Zhang, H., Liu, X., Andersen, D.G., Kaminsky, M., Keeton, K., Pavlo, A.: Order-Preserving Key Compression for In-Memory Search Trees. In: SIGMOD, pp. 1601\u20131615 (2020)","DOI":"10.1145\/3318464.3380583"},{"key":"950_CR60","doi-asserted-by":"crossref","unstructured":"Ziegler, T., Vani, S.T., Binnig, C., Fonseca, R., Kraska, T.: Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks. In: SIGMOD, pp. 741\u2013758 (2019)","DOI":"10.1145\/3299869.3300081"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-025-00950-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-025-00950-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-025-00950-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T07:27:39Z","timestamp":1770449259000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-025-00950-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,28]]},"references-count":60,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["950"],"URL":"https:\/\/doi.org\/10.1007\/s00778-025-00950-8","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,28]]},"assertion":[{"value":"12 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"4"}}