{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:46:50Z","timestamp":1763459210536,"version":"3.45.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,18]],"date-time":"2017-07-18T00:00:00Z","timestamp":1500336000000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ACI-0324974, CCF-0540897\/05414009\/0541209\/0621439\/0621425\/0621511\/0634793\/0632838\/0937822\/0937860\/1162148\/1217708\/1314547\/1439084\/1617618, CNS-0540248\/0615215\/0627645\/1017058\/1408695\/1409238, IIS-1247726\/1251137"],"award-info":[{"award-number":["ACI-0324974, CCF-0540897\/05414009\/0541209\/0621439\/0621425\/0621511\/0634793\/0632838\/0937822\/0937860\/1162148\/1217708\/1314547\/1439084\/1617618, CNS-0540248\/0615215\/0627645\/1017058\/1408695\/1409238, IIS-1247726\/1251137"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-FG02-08ER25853"],"award-info":[{"award-number":["DE-FG02-08ER25853"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001474","name":"Singapore-MIT Alliance for Research and Technology Centre","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001474","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006234","name":"Sandia National Laboratories","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006234","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2016,8,8]]},"abstract":"\n Most B-tree articles assume that all\n N<\/jats:italic>\n keys have the same size\n K<\/jats:italic>\n , that\n f<\/jats:italic>\n =\n B<\/jats:italic>\n \/\n K<\/jats:italic>\n keys fit in a disk block, and therefore that the search cost is\n O<\/jats:italic>\n (log\n \n f<\/jats:italic>\n + 1\n <\/jats:sub>\n N<\/jats:italic>\n ) block transfers. When keys have variable size, B-tree operations have no nontrivial performance guarantees, however.\n <\/jats:p>\n \n This article provides B-tree-like performance guarantees on dictionaries that contain keys of different sizes in a model in which keys must be stored and compared as opaque objects. The resulting\n atomic-key dictionaries<\/jats:italic>\n exhibit performance bounds in terms of the average key size and match the bounds when all keys are the same size. Atomic-key dictionaries can be built with minimal modification to the B-tree structure, simply by choosing the pivot keys properly.\n <\/jats:p>\n \n This article describes both static and dynamic atomic-key dictionaries. In the static case, if there are\n N<\/jats:italic>\n keys with average size\n K<\/jats:italic>\n , the search cost is\n O<\/jats:italic>\n (\u2308\n K<\/jats:italic>\n \/\n B<\/jats:italic>\n \u2309log\n \n 1 + \u2308\n B<\/jats:italic>\n \/\n K<\/jats:italic>\n \u2309\n <\/jats:sub>\n N<\/jats:italic>\n ) expected transfers. It is not possible to transform these expected bounds into worst-case bounds. The cost to build the tree is\n O<\/jats:italic>\n (\n NK<\/jats:italic>\n ) operations and\n O<\/jats:italic>\n (\n NK\/B<\/jats:italic>\n ) transfers if all keys are presented in sorted order. If not, the cost is the sorting cost.\n <\/jats:p>\n \n For the dynamic dictionaries, the amortized cost to insert a key \u03ba of arbitrary length at an arbitrary rank is dominated by the cost to search for \u03ba. Specifically, the amortized cost to insert a key \u03ba of arbitrary length and random rank is\n O<\/jats:italic>\n (\u2308\n K<\/jats:italic>\n \/\n B<\/jats:italic>\n \u2309log\n \n 1 + \u2308\n B<\/jats:italic>\n \/\n K<\/jats:italic>\n \u2309\n <\/jats:sub>\n N<\/jats:italic>\n + |\u03ba|\/\n B<\/jats:italic>\n ) transfers. A dynamic-programming algorithm is shown for constructing a search tree with minimal expected cost.\n <\/jats:p>\n \n This article also gives a cache-oblivious static atomic-key B-tree, which achieves the same asymptotic performance as the static B-tree dictionary, mentioned previously. A cache-oblivious data structure or algorithm is not parameterized by the block size\n B<\/jats:italic>\n or memory size\n M<\/jats:italic>\n in the memory hierarchy; rather, it is universal, working simultaneously for all possible values of\n B<\/jats:italic>\n or\n M<\/jats:italic>\n . On a machine with block size\n B<\/jats:italic>\n , if there are\n N<\/jats:italic>\n keys with average size\n K<\/jats:italic>\n , search operations costs\n O<\/jats:italic>\n (\u2308\n K<\/jats:italic>\n \/\n B<\/jats:italic>\n \u2309log\n \n 1 + \u2308\n B<\/jats:italic>\n \/\n K<\/jats:italic>\n \u2309\n <\/jats:sub>\n N<\/jats:italic>\n ) block transfers in expectation. This cache-oblivious layout can be built in\n O<\/jats:italic>\n (\n N<\/jats:italic>\n log(\n NK<\/jats:italic>\n )) processor operations.\n <\/jats:p>","DOI":"10.1145\/2907945","type":"journal-article","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T07:59:22Z","timestamp":1468915162000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["B-Trees and Cache-Oblivious B-Trees with Different-Sized Atomic Keys"],"prefix":"10.1145","volume":"41","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roozbeh","family":"Ebrahimi","sequence":"additional","affiliation":[{"name":"Google Inc., CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haodong","family":"Hu","sequence":"additional","affiliation":[{"name":"Shanghai University of Finance and Economics, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bradley C.","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"MIT CSAIL, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","volume-title":"Efficient Tree Layout in a Multilevel Memory Hierarchy. arXiv:cs.DS\/0211010. (November","author":"Alstrup Stephen","year":"2002","unstructured":"Stephen Alstrup, Michael A. Bender, Erik D. Demaine, Martin Farach-Colton, J. Ian Munro, Theis Rauhe, and Mikkel Thorup. 2002. Efficient Tree Layout in a Multilevel Memory Hierarchy. arXiv:cs.DS\/0211010. (November 2002). http:\/\/www.arXiv.org\/abs\/cs.DS\/0211010."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/320521.320530"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/640160.640162"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796541"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701389956"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545385"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.014"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/646388.690192"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142385"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807125"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222017"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109621"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545386"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313681"},{"key":"e_1_2_1_17_1","volume-title":"Stafford","author":"Clark William A.","year":"1969","unstructured":"William A. Clark, Kent A. Salmond, and Thomas S. Stafford. 1969. Method and Means for Generating Compressed Keys. US Patent No. 3,593,309, Filed Jan. 3, 1969."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_29"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/357994.358025"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301973"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796479"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071383"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808675"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1014"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210031"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02017342"},{"volume-title":"Sorting and Searching","author":"Knuth Donald E.","key":"e_1_2_1_29_1","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison Wesley, Reading, MA."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/4021.4026"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/359810.359839"},{"volume-title":"Release 4.8. (August","year":"2009","key":"e_1_2_1_32_1","unstructured":"Oracle. 2009. Oracle Berkeley DB Programmer\u2019s Reference Guide, Release 4.8. (August 2009). http:\/\/www.oracle.com\/technology\/documentation\/berkeley-db\/db\/index.html."},{"volume-title":"Cache-Oblivious Algorithms. Master\u2019s thesis. Department of Electrical Engineering and Computer Science","author":"Prokop Harald","key":"e_1_2_1_33_1","unstructured":"Harald Prokop. 1999. Cache-Oblivious Algorithms. Master\u2019s thesis. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/319540.319565"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288540"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.124.0351"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2907945","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2907945","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2907945","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:40:46Z","timestamp":1763458846000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2907945"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,18]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,8,8]]}},"alternative-id":["10.1145\/2907945"],"URL":"https:\/\/doi.org\/10.1145\/2907945","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2016,7,18]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}