{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T19:23:33Z","timestamp":1774121013213,"version":"3.50.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>Internet applications increasingly rely on scalable data structures that must support high throughput and store huge amounts of data. These data structures can be hard to implement efficiently. Recent proposals have overcome this problem by giving up on generality and implementing specialized interfaces and functionality (e.g., Dynamo [4]). We present the design of a more general and flexible solution: a fault-tolerant and scalable distributed B-tree. In addition to the usual B-tree operations, our B-tree provides some important practical features: transactions for atomically executing several operations in one or more B-trees, online migration of B-tree nodes between servers for load-balancing, and dynamic addition and removal of servers for supporting incremental growth of the system.<\/jats:p>\n          <jats:p>Our design is conceptually simple. Rather than using complex concurrency and locking protocols, we use distributed transactions to make changes to B-tree nodes. We show how to extend the B-tree and keep additional information so that these transactions execute quickly and efficiently. Our design relies on an underlying distributed data sharing service, Sinfonia [1], which provides fault tolerance and a light-weight distributed atomic primitive. We use this primitive to commit our transactions. We implemented our B-tree and show that it performs comparably to an existing open-source B-tree and that it scales to hundreds of machines. We believe that our approach is general and can be used to implement other distributed data structures easily.<\/jats:p>","DOI":"10.14778\/1453856.1453922","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"598-609","source":"Crossref","is-referenced-by-count":84,"title":["A practical scalable distributed B-tree"],"prefix":"10.14778","volume":"1","author":[{"given":"Marcos K.","family":"Aguilera","sequence":"first","affiliation":[{"name":"Microsoft Research Silicon Valley, Mountain View, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Golab","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mehul A.","family":"Shah","sequence":"additional","affiliation":[{"name":"HP Laboratories, Palo Alto, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294278"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/824472.825527"},{"key":"e_1_2_1_3_1","first-page":"205","volume-title":"Proc. SOSP '06","author":"Chang F.","year":"2006","unstructured":"F. Chang , J. Dean , S. Ghemawat , W. C. Hsieh , D. A. Wallach , M. Burrows , T. Chandra , A. Fikes , and R. Gruber . Bigtable: A distributed storage system for structured data . In Proc. SOSP '06 , pages 205 -- 218 , Nov. 2006 . F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. Gruber. Bigtable: A distributed storage system for structured data. In Proc. SOSP '06, pages 205--218, Nov. 2006."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_5_1","first-page":"319","volume-title":"Proc. OSDI '00","author":"Gribble S.","year":"2000","unstructured":"S. Gribble , E. Brewer , J. Hellersteiu , and D. Culler . Scalable, distributed data structures for Internet service construction . In Proc. OSDI '00 , pages 319 -- 332 , Oct. 2000 . S. Gribble, E. Brewer, J. Hellersteiu, and D. Culler. Scalable, distributed data structures for Internet service construction. In Proc. OSDI '00, pages 319--332, Oct. 2000."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872048"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/165123.165164"},{"key":"e_1_2_1_8_1","volume-title":"High Performance","year":"2008","unstructured":"HyperTable. HyperTable : An Open Source , High Performance , Scalabe Database , 2008 . Online: http:\/\/hypertable.org\/. HyperTable. HyperTable: An Open Source, High Performance, Scalabe Database, 2008. Online: http:\/\/hypertable.org\/."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/319566.319567"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/319628.319663"},{"key":"e_1_2_1_12_1","first-page":"342","volume-title":"Proc. VLDB '94","author":"Litwin W.","year":"1994","unstructured":"W. Litwin , M.-A. Neimat , and D. Schneider . RP*: A Family of Order Preserving Scalable Distributed Data Structures . In Proc. VLDB '94 , pages 342 -- 353 , Sept. 1994 . W. Litwin, M.-A. Neimat, and D. Schneider. RP*: A Family of Order Preserving Scalable Distributed Data Structures. In Proc. VLDB '94, pages 342--353, Sept. 1994."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/236711.236713"},{"key":"e_1_2_1_14_1","first-page":"105","volume-title":"Proc. OSDI '04","author":"MacCormick J.","year":"2004","unstructured":"J. MacCormick , N. Murphy , M. Najork , C. Thekkath , and L. Zhou . Boxwood: Abstractions as the foundation for storage infrastructure . In Proc. OSDI '04 , pages 105 -- 120 , Dec. 2004 . J. MacCormick, N. Murphy, M. Najork, C. Thekkath, and L. Zhou. Boxwood: Abstractions as the foundation for storage infrastructure. In Proc. OSDI '04, pages 105--120, Dec. 2004."},{"key":"e_1_2_1_15_1","first-page":"392","volume-title":"Proc. VLDB '90","author":"Mohan C.","year":"1990","unstructured":"C. Mohan . ARIES\/KVL : A key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes . In Proc. VLDB '90 , pages 392 -- 405 , Aug. 1990 . C. Mohan. ARIES\/KVL: A key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes. In Proc. VLDB '90, pages 392--405, Aug. 1990."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383072"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/325405.325409"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/224964.224987"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376693"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383071"},{"key":"e_1_2_1_21_1","unstructured":"Sun Microsystems. Lustre 2008. Online: http:\/\/lustre.org\/.  Sun Microsystems. Lustre 2008. Online: http:\/\/lustre.org\/."},{"key":"e_1_2_1_22_1","unstructured":"The Apache Software Foundation. Hadoop 2008. Online: http:\/\/hadoop.apache.org\/.  The Apache Software Foundation. Hadoop 2008. Online: http:\/\/hadoop.apache.org\/."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453922","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:11:25Z","timestamp":1672225885000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453922"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453922","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}