{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T17:07:56Z","timestamp":1773248876424,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,2,1]],"date-time":"2008-02-01T00:00:00Z","timestamp":1201824000000},"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. Storage"],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p>B-trees are used by many file systems to represent files and directories. They provide guaranteed logarithmic time key-search, insert, and remove. File systems like WAFL and ZFS use shadowing, or copy-on-write, to implement snapshots, crash recovery, write-batching, and RAID. Serious difficulties arise when trying to use b-trees and shadowing in a single system.<\/jats:p>\n          <jats:p>This article is about a set of b-tree algorithms that respects shadowing, achieves good concurrency, and implements cloning (writeable snapshots). Our cloning algorithm is efficient and allows the creation of a large number of clones.<\/jats:p>\n          <jats:p>We believe that using our b-trees would allow shadowing file systems to better scale their on-disk data structures.<\/jats:p>","DOI":"10.1145\/1326542.1326544","type":"journal-article","created":{"date-parts":[[2008,2,28]],"date-time":"2008-02-28T14:02:33Z","timestamp":1204207353000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":65,"title":["B-trees, shadowing, and clones"],"prefix":"10.1145","volume":"3","author":[{"given":"Ohad","family":"Rodeh","sequence":"first","affiliation":[{"name":"IBM Haifa Research Labs, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2008,2,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Bayer R. and McCreight E. 1972. Organization and maintenance of large ordered indices. Acta Informatica 173--189.  Bayer R. and McCreight E. 1972. Organization and maintenance of large ordered indices. Acta Informatica 173--189.","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263762"},{"key":"e_1_2_1_3_1","unstructured":"Best S. 2002. Journaling file systems. Linux Mag.  Best S. 2002. Journaling file systems. Linux Mag."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_5_1","volume-title":"Write-Optimized B-trees. In Proceedings of the International Conference on Very Large Database (VLDB), 672--683","author":"Graefe G.","year":"2004","unstructured":"Graefe , G. 2004 . Write-Optimized B-trees. In Proceedings of the International Conference on Very Large Database (VLDB), 672--683 . Graefe, G. 2004. Write-Optimized B-trees. In Proceedings of the International Conference on Very Large Database (VLDB), 672--683."},{"key":"e_1_2_1_6_1","volume-title":"Transaction Processing: Concepts and Techniques. Mogran Kaufmann.","author":"Gray J.","year":"1993","unstructured":"Gray , J. and Reuter , A . 1993 . Transaction Processing: Concepts and Techniques. Mogran Kaufmann. Gray, J. and Reuter, A. 1993. Transaction Processing: Concepts and Techniques. Mogran Kaufmann."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 19th Annual Symposium on Foundations of Computer Science.","author":"Guibas L.","unstructured":"Guibas , L. and Sedgewick , R . 1978. A dichromatic framework for balanced trees . In Proceedings of the 19th Annual Symposium on Foundations of Computer Science. Guibas, L. and Sedgewick, R. 1978. A dichromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science."},{"key":"e_1_2_1_8_1","volume-title":"USENIX Conference on File and Storage Technologies (work in progress report).","author":"Henson V.","unstructured":"Henson , V. , Ahrens , M. , and Bonwick , J . 2003. Automatic performance tuning in the Zettabyte file system . In USENIX Conference on File and Storage Technologies (work in progress report). Henson, V., Ahrens, M., and Bonwick, J. 2003. Automatic performance tuning in the Zettabyte file system. In USENIX Conference on File and Storage Technologies (work in progress report)."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the USENIX Technical Conference.","author":"Hitz D.","unstructured":"Hitz , D. , Lau , J. , and Malcolm , M . 1994. File system design for an NFS file server appliance . In Proceedings of the USENIX Technical Conference. Hitz, D., Lau, J., and Malcolm, M. 1994. File system design for an NFS file server appliance. In Proceedings of the USENIX Technical Conference."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the ACM Fall Joint Computer Conference","author":"Lanin V.","unstructured":"Lanin , V. and Shasha , D . 1986. A symmetric concurrent B-tree algorithm . In Proceedings of the ACM Fall Joint Computer Conference , Dallas, TX, 380--389. Lanin, V. and Shasha, D. 1986. A symmetric concurrent B-tree algorithm. In Proceedings of the ACM Fall Joint Computer Conference, Dallas, TX, 380--389."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/319628.319663"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/603867.603878"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130336"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/989.990"},{"key":"e_1_2_1_15_1","volume-title":"USENIX Conference on File and Storage Technologies (FAST).","author":"Megiddo N.","unstructured":"Megiddo , N. and Modha , D. S . 2003. ARC: A self-tuning, low overhead replacement cache . In USENIX Conference on File and Storage Technologies (FAST). Megiddo, N. and Modha, D. S. 2003. ARC: A self-tuning, low overhead replacement cache. In USENIX Conference on File and Storage Technologies (FAST)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.422.0250"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130338"},{"key":"e_1_2_1_18_1","volume-title":"the 11th International Conference on Very Large Data Bases.","author":"Mond Y.","unstructured":"Mond , Y. and Raz , Y . 1985. Concurrency control in B&plus; trees databases using preparatory operations . In the 11th International Conference on Very Large Data Bases. Mond, Y. and Raz, Y. 1985. Concurrency control in B&plus; trees databases using preparatory operations. In the 11th International Conference on Very Large Data Bases."},{"key":"e_1_2_1_19_1","unstructured":"Reiser H. 2004. ReiserFS. http:\/\/www.namesys.com\/.  Reiser H. 2004. ReiserFS. http:\/\/www.namesys.com\/."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Rosenberg J. Henskens F. Brown A. Morrison R. and Munro D. 1990. Stability in a persistent store based on a large virtual memory. Secur. Persist. 229--245.  Rosenberg J. Henskens F. Brown A. Morrison R. and Munro D. 1990. Stability in a persistent store based on a large virtual memory. Secur. Persist. 229--245.","DOI":"10.1007\/978-1-4471-3178-6_16"},{"key":"e_1_2_1_22_1","volume-title":"USENIX Conference on File and Storage Technologies (FAST).","author":"Soules C.","year":"2003","unstructured":"Soules , C. , Goodson , G. , Strunk , J. , and Ganger , G . 2003 . Metadata efficiency in a comprehensive versioning file system . In USENIX Conference on File and Storage Technologies (FAST). Soules, C., Goodson, G., Strunk, J., and Ganger, G . 2003. Metadata efficiency in a comprehensive versioning file system. In USENIX Conference on File and Storage Technologies (FAST)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263046"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the USENIX Technical Conference, 1--14","author":"Sweeny A.","unstructured":"Sweeny , A. , Doucette , D. , Hu , W. , Anderson , C. , Nishimoto , M. , and Peck , G . 1996. Scalability in the XFS file system . In Proceedings of the USENIX Technical Conference, 1--14 . Sweeny, A., Doucette, D., Hu, W., Anderson, C., Nishimoto, M., and Peck, G. 1996. Scalability in the XFS file system. In Proceedings of the USENIX Technical Conference, 1--14."}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1326542.1326544","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1326542.1326544","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:25Z","timestamp":1750254985000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1326542.1326544"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1145\/1326542.1326544"],"URL":"https:\/\/doi.org\/10.1145\/1326542.1326544","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2]]},"assertion":[{"value":"2007-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}