{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:24:49Z","timestamp":1760441089407,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","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":["J. ACM"],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p>\n            One-dimensional range queries, as one of the most basic type of queries in databases, have been studied extensively in the literature. For large databases, the goal is to build an external index that is optimized for disk block accesses (or I\/Os). The problem is well understood in the static case. Theoretically, there exists an index of linear size that can answer a range query in O(1 +\n            <jats:italic>KB<\/jats:italic>\n            ) I\/Os, where\n            <jats:italic>K<\/jats:italic>\n            is the output size and\n            <jats:italic>B<\/jats:italic>\n            is the disk block size, but it is highly impractical. In practice, the standard solution is the B-tree, which answers a query in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sub>B<\/jats:sub>\n            <jats:italic>NM<\/jats:italic>\n            +\n            <jats:italic>KB<\/jats:italic>\n            ) I\/Os on a data set of size\n            <jats:italic>N<\/jats:italic>\n            , where\n            <jats:italic>M<\/jats:italic>\n            is the main memory size. For typical values of\n            <jats:italic>N, M<\/jats:italic>\n            , and\n            <jats:italic>B<\/jats:italic>\n            , log\n            <jats:sub>B<\/jats:sub>\n            <jats:italic>NM<\/jats:italic>\n            can be considered a constant.\n          <\/jats:p>\n          <jats:p>\n            However, the problem is still wide open in the dynamic setting, when insertions and deletions of records are to be supported. With smart buffering, it is possible to speed up updates significantly to\n            <jats:italic>o<\/jats:italic>\n            (1) I\/Os amortized. Indeed, several dynamic B-trees have been proposed, but they all cause certain levels of degradation in the query performance, with the most interesting tradeoff point at\n            <jats:italic>O<\/jats:italic>\n            (1\n            <jats:italic>B<\/jats:italic>\n            log\n            <jats:italic>NM<\/jats:italic>\n            ) I\/Os for updates and\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>NM<\/jats:italic>\n            +\n            <jats:italic>KB<\/jats:italic>\n            ) I\/Os for queries. In this article, we prove that the query-update tradeoffs of all the known dynamic B-trees are optimal, when log\n            <jats:sub>B<\/jats:sub>\n            <jats:italic>NM<\/jats:italic>\n            is a constant. This implies that one should not hope for substantially better solutions for all practical values of the parameters. Our lower bounds hold in a dynamic version of the\n            <jats:italic>indexability model<\/jats:italic>\n            , which is of independent interests. Dynamic indexability is a clean yet powerful model for studying dynamic indexing problems, and can potentially lead to more interesting lower bound results.\n          <\/jats:p>","DOI":"10.1145\/2339123.2339129","type":"journal-article","created":{"date-parts":[[2012,9,4]],"date-time":"2012-09-04T12:50:47Z","timestamp":1346763047000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Dynamic Indexability and the Optimality of B-Trees"],"prefix":"10.1145","volume":"59","author":[{"given":"Ke","family":"Yi","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380842"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236460"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1021-x"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.304010"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9126-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1822"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248393"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 546--554","author":"Brodal G. S.","key":"e_1_2_1_11_1","unstructured":"Brodal , G. S. and Fagerberg , R . 2003. Lower bounds for external memory dictionaries . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 546--554 . Brodal, G. S. and Fagerberg, R. 2003. Lower bounds for external memory dictionaries. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 546--554."},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 859--860","author":"Buchsbaum A. L.","key":"e_1_2_1_12_1","unstructured":"Buchsbaum , A. L. , Goldwasser , M. , Venkatasubramanian , S. , and Westbrook , J. R . 2000. On external memory graph traversal . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 859--860 . Buchsbaum, A. L., Goldwasser, M., Venkatasubramanian, S., and Westbrook, J. R. 2000. On external memory graph traversal. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 859--860."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263688"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/505241.505244"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Iacono J.","key":"e_1_2_1_16_1","unstructured":"Iacono , J. , and P\u01cetra\u015fcu , M . 2012. Using hashing to solve the dictionary problem (in external memory) . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Iacono, J., and P\u01cetra\u015fcu, M. 2012. Using hashing to solve the dictionary problem (in external memory). In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms."},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 16--25","author":"Jagadish H. V.","key":"e_1_2_1_17_1","unstructured":"Jagadish , H. V. , Narayan , P. P. S. , Seshadri , S. , Sudarshan , S. , and Kanneganti , R . 1997. Incremental organization for data recording and warehousing . In Proceedings of the International Conference on Very Large Data Bases. 16--25 . Jagadish, H. V., Narayan, P. P. S., Seshadri, S., Sudarshan, S., and Kanneganti, R. 1997. Incremental organization for data recording and warehousing. In Proceedings of the International Conference on Very Large Data Bases. 16--25."},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 235--246","author":"Jermaine C.","key":"e_1_2_1_18_1","unstructured":"Jermaine , C. , Datta , A. , and Omiecinski , E . 1999. A novel index supporting high volume data waresshouse insertion . In Proceedings of the International Conference on Very Large Data Bases. 235--246 . Jermaine, C., Datta, A., and Omiecinski, E. 1999. A novel index supporting high volume data waresshouse insertion. In Proceedings of the International Conference on Very Large Data Bases. 235--246."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275494"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060606"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275493"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2339123.2339129","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2339123.2339129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:21:08Z","timestamp":1750238468000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2339123.2339129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1145\/2339123.2339129"],"URL":"https:\/\/doi.org\/10.1145\/2339123.2339129","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2012,8]]},"assertion":[{"value":"2009-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}