{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T18:33:58Z","timestamp":1764873238898,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T00:00:00Z","timestamp":1343779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p>\n            Foster B-trees are a new variant of B-trees that combines advantages of prior B-tree variants optimized for many-core processors and modern memory hierarchies with flash storage and nonvolatile memory. Specific goals include: (i) minimal concurrency control requirements for the data structure, (ii) efficient migration of nodes to new storage locations, and (iii) support for continuous and comprehensive self-testing. Like B\n            <jats:sup>link<\/jats:sup>\n            -trees, Foster B-trees optimize latching without imposing restrictions or specific designs on transactional locking, for example, key range locking. Like write-optimized B-trees, and unlike B\n            <jats:sup>link<\/jats:sup>\n            -trees, Foster B-trees enable large writes on RAID and flash devices as well as wear leveling and efficient defragmentation. Finally, they support continuous and inexpensive yet comprehensive verification of all invariants, including all cross-node invariants of the B-tree structure. An implementation and a performance evaluation show that the Foster B-tree supports high concurrency and high update rates without compromising consistency, correctness, or read performance.\n          <\/jats:p>","DOI":"10.1145\/2338626.2338630","type":"journal-article","created":{"date-parts":[[2012,9,11]],"date-time":"2012-09-11T22:21:06Z","timestamp":1347402066000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":54,"title":["Foster b-trees"],"prefix":"10.1145","volume":"37","author":[{"given":"Goetz","family":"Graefe","sequence":"first","affiliation":[{"name":"HP Labs, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hideaki","family":"Kimura","sequence":"additional","affiliation":[{"name":"Brown University, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harumi","family":"Kuno","sequence":"additional","affiliation":[{"name":"HP Labs, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,9,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734663.1734671"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263762"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/320521.320530"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Bernstein P. A. and Newcomer E. 2009. Transaction Processing 2nd ed. Morgan Kaufmann.  Bernstein P. A. and Newcomer E. 2009. Transaction Processing 2 nd ed. Morgan Kaufmann.","DOI":"10.1016\/B978-1-55860-623-4.00004-4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2014699.2014921"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191915"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/358769.358784"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/176979.176981"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/360363.360369"},{"key":"e_1_2_1_11_1","volume-title":"Write-Optimized B-trees. In Proceedings of the International Conference on Very Large Databases (VLDB'04)","author":"Graefe G.","year":"2004","unstructured":"Graefe , G. 2004 . Write-Optimized B-trees. In Proceedings of the International Conference on Very Large Databases (VLDB'04) . 672--683. Graefe, G. 2004. Write-Optimized B-trees. In Proceedings of the International Conference on Very Large Databases (VLDB'04). 672--683."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806908"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000028"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2109196.2109197"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2180912.2180917"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2304510.2304521"},{"volume-title":"Proceedings of the German Database Conference Datenbanksysteme f\u00fcr B\u00fcro, Technik und Wissenschaft (BTW'09)","author":"Graefe G.","key":"e_1_2_1_17_1","unstructured":"Graefe , G. and Stonecipher , R . 2009. Efficient verification of B-tree integrity . In Proceedings of the German Database Conference Datenbanksysteme f\u00fcr B\u00fcro, Technik und Wissenschaft (BTW'09) . 27--46. Graefe, G. and Stonecipher, R. 2009. Efficient verification of B-tree integrity. In Proceedings of the German Database Conference Datenbanksysteme f\u00fcr B\u00fcro, Technik und Wissenschaft (BTW'09). 27--46."},{"key":"e_1_2_1_18_1","volume-title":"Transaction Processing: Concepts and Techniques. Morgan Kaufmann.","author":"Gray J.","year":"1992","unstructured":"Gray , J. and Reuter , A . 1992 . Transaction Processing: Concepts and Techniques. Morgan Kaufmann. Gray, J. and Reuter, A. 1992. Transaction Processing: Concepts and Techniques. Morgan Kaufmann."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Conference on Telecommunication Technology and Applications (ICTTA'06)","volume":"2","author":"Jaluta I.","unstructured":"Jaluta , I. and Majumda , D . 2006. Efficient space management for B-tree structure-modification operations . In Proceedings of the International Conference on Telecommunication Technology and Applications (ICTTA'06) . Vol. 2 . 2909--2912. Jaluta, I. and Majumda, D. 2006. Efficient space management for B-tree structure-modification operations. In Proceedings of the International Conference on Telecommunication Technology and Applications (ICTTA'06). Vol. 2. 2909--2912."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0140-6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516365"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920928"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"K\u00fcspert K. 1985. Fehlererkennung und fehlerbehandlung in speicherungsstrukturen von datenbanksystemen. Informatik Fachberichte 99.  K\u00fcspert K. 1985. Fehlererkennung und fehlerbehandlung in speicherungsstrukturen von datenbanksystemen. Informatik Fachberichte 99.","DOI":"10.1007\/978-3-642-70288-4"},{"volume-title":"Proceedings of the ACM Fall Joint Computer Conference. IEEE Computer Society Press","author":"Lanin V.","key":"e_1_2_1_24_1","unstructured":"Lanin , V. and Shasha , D . 1986. A symmetric concurrent B-tree algorithm . In Proceedings of the ACM Fall Joint Computer Conference. IEEE Computer Society Press , Los Alamitos, CA, 380--389. Lanin, V. and Shasha, D. 1986. A symmetric concurrent B-tree algorithm. In Proceedings of the ACM Fall Joint Computer Conference. IEEE Computer Society Press, Los Alamitos, CA, 380--389."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/319628.319663"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'93)","author":"Lomet D. B.","year":"1993","unstructured":"Lomet , D. B. 1993 . Key range locking strategies for improved concurrency . In Proceedings of the International Conference on Very Large Databases (VLDB'93) . 655--664. Lomet, D. B. 1993. Key range locking strategies for improved concurrency. In Proceedings of the International Conference on Very Large Databases (VLDB'93). 655--664."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/603867.603878"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978124"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050042"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'95)","author":"Lomet D. B.","key":"e_1_2_1_30_1","unstructured":"Lomet , D. B. and Tuttle , M. R . 1995. Redo recovery after system crashes . In Proceedings of the International Conference on Very Large Databases (VLDB'95) . 457--468. Lomet, D. B. and Tuttle, M. R. 1995. Redo recovery after system crashes. In Proceedings of the International Conference on Very Large Databases (VLDB'95). 457--468."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872806"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'90)","author":"Mohan C.","year":"1990","unstructured":"Mohan , C. 1990 . ARIES\/KVL: A key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes . In Proceedings of the International Conference on Very Large Databases (VLDB'90) . 392--405. Mohan, C. 1990. ARIES\/KVL: A key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes. In Proceedings of the International Conference on Very Large Databases (VLDB'90). 392--405."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/645480.655433"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/128765.128770"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130338"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920959"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2021017.2021019"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/325405.325409"},{"key":"e_1_2_1_39_1","first-page":"11","article-title":"PALM: Parallel architecture-friendly latch-free modifications to B&plus; trees on many-core processors","volume":"4","author":"Sewall J.","year":"2011","unstructured":"Sewall , J. , Chhugani , J. , Kim , C. , Satish , N. , and Dubey , P. 2011 . PALM: Parallel architecture-friendly latch-free modifications to B&plus; trees on many-core processors . Proc. VLDB 4 , 11 . Sewall, J., Chhugani, J., Kim, C., Satish, N., and Dubey, P. 2011. PALM: Parallel architecture-friendly latch-free modifications to B&plus; trees on many-core processors. Proc. VLDB 4, 11.","journal-title":"Proc. VLDB"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/103140.103145"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2338626.2338630","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2338626.2338630","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:49:00Z","timestamp":1750236540000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2338626.2338630"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1145\/2338626.2338630"],"URL":"https:\/\/doi.org\/10.1145\/2338626.2338630","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2012,8]]},"assertion":[{"value":"2012-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-09-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}