{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/150198"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/150198","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"BP-Tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B⁺-trees","abstract":"This thesis presents the BP-tree, an efficient concurrent key-value store based on the B⁺-tree, that uses large leaf nodes to optimize for range-query performance without sacrificing update speed by using large leaf nodes. B⁺-trees are a fundamental data structure for implementing in-memory indexes in databases and storage systems. B⁺- trees support both point operations (i.e., inserts and finds) and range operations (i.e., iterators and maps). There is an inherent tradeoff between point and range operations however, since the optimal node size for point operations is much smaller than the optimal node size for range operations. To avoid any slowdown in point operations, this thesis introduces a novel insert-optimized array called the buffered partitioned array (BPA) to efficiently organize data in leaf nodes. Using the buffered partitioned array, the BP-tree overcomes the decades-old tradeoff between point and range operations in B⁺-trees. Experiments show that on 48 hyperthreads, the BP-tree supports slightly faster (by about 1.1×) point operations than the best-case configuration for B+-trees for point operations while supporting between 1.4×–1.7× faster range operations. On workloads generated from the Yahoo! Cloud Serving Benchmark (YCSB), the BP-tree is faster (by about 1.1×) on all point operation workloads compared to the B⁺-tree, and slower (by about 1.15×) on the short range operation workload compared to the B⁺-tree. Furthermore, this work extends the YCSB to include large scan and map workloads, commonly found in database applications, and find that the BP-tree is between 1.2×–1.4× faster than the B⁺-tree on these workloads. This thesis contains my joint work with Helen Xu, Brian Wheatman, Manoj Marneni, and Prashant Pandey.","abstract_html":"This thesis presents the BP-tree, an efficient concurrent key-value store based on the B⁺-tree, that uses large leaf nodes to optimize for range-query performance without sacrificing update speed by using large leaf nodes. B⁺-trees are a fundamental data structure for implementing in-memory indexes in databases and storage systems. B⁺- trees support both point operations (i.e., inserts and finds) and range operations (i.e., iterators and maps). There is an inherent tradeoff between point and range operations however, since the optimal node size for point operations is much smaller than the optimal node size for range operations. To avoid any slowdown in point operations, this thesis introduces a novel insert-optimized array called the buffered partitioned array (BPA) to efficiently organize data in leaf nodes. Using the buffered partitioned array, the BP-tree overcomes the decades-old tradeoff between point and range operations in B⁺-trees. Experiments show that on 48 hyperthreads, the BP-tree supports slightly faster (by about 1.1×) point operations than the best-case configuration for B+-trees for point operations while supporting between 1.4×–1.7× faster range operations. On workloads generated from the Yahoo! Cloud Serving Benchmark (YCSB), the BP-tree is faster (by about 1.1×) on all point operation workloads compared to the B⁺-tree, and slower (by about 1.15×) on the short range operation workload compared to the B⁺-tree. Furthermore, this work extends the YCSB to include large scan and map workloads, commonly found in database applications, and find that the BP-tree is between 1.2×–1.4× faster than the B⁺-tree on these workloads. This thesis contains my joint work with Helen Xu, Brian Wheatman, Manoj Marneni, and Prashant Pandey.","abstract_has_math":false,"creators":["Li, Amanda"],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Xu, Helen","Leiserson, Charles E."],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-02","date_published":"2023-02","updated_at":"2026-07-22T22:21:57Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"rights_urls":["http://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/150198","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Xu, Helen","Leiserson, Charles E."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Li, Amanda"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2023-03-31T14:39:04Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2023-03-31T14:39:04Z"]},{"key":"dc:date.issued","label":"Date","values":["2023-02"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master","Master of Engineering in Electrical Engineering and Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright MIT"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/150198"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This thesis presents the BP-tree, an efficient concurrent key-value store based on the B⁺-tree, that uses large leaf nodes to optimize for range-query performance without sacrificing update speed by using large leaf nodes. B⁺-trees are a fundamental data structure for implementing in-memory indexes in databases and storage systems. B⁺- trees support both point operations (i.e., inserts and finds) and range operations (i.e., iterators and maps). There is an inherent tradeoff between point and range operations however, since the optimal node size for point operations is much smaller than the optimal node size for range operations. To avoid any slowdown in point operations, this thesis introduces a novel insert-optimized array called the buffered partitioned array (BPA) to efficiently organize data in leaf nodes. Using the buffered partitioned array, the BP-tree overcomes the decades-old tradeoff between point and range operations in B⁺-trees. Experiments show that on 48 hyperthreads, the BP-tree supports slightly faster (by about 1.1×) point operations than the best-case configuration for B+-trees for point operations while supporting between 1.4×–1.7× faster range operations. On workloads generated from the Yahoo! Cloud Serving Benchmark (YCSB), the BP-tree is faster (by about 1.1×) on all point operation workloads compared to the B⁺-tree, and slower (by about 1.15×) on the short range operation workload compared to the B⁺-tree. Furthermore, this work extends the YCSB to include large scan and map workloads, commonly found in database applications, and find that the BP-tree is between 1.2×–1.4× faster than the B⁺-tree on these workloads. This thesis contains my joint work with Helen Xu, Brian Wheatman, Manoj Marneni, and Prashant Pandey."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:title","label":"Title","values":["BP-Tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B⁺-trees"]}]}],"canonical_facts":{"dc:contributor.advisor":["Xu, Helen","Leiserson, Charles E."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Li, Amanda"],"dc:date.accessioned":["2023-03-31T14:39:04Z"],"dc:date.available":["2023-03-31T14:39:04Z"],"dc:date.issued":["2023-02"],"dc:description.abstract":["This thesis presents the BP-tree, an efficient concurrent key-value store based on the B⁺-tree, that uses large leaf nodes to optimize for range-query performance without sacrificing update speed by using large leaf nodes. B⁺-trees are a fundamental data structure for implementing in-memory indexes in databases and storage systems. B⁺- trees support both point operations (i.e., inserts and finds) and range operations (i.e., iterators and maps). There is an inherent tradeoff between point and range operations however, since the optimal node size for point operations is much smaller than the optimal node size for range operations. To avoid any slowdown in point operations, this thesis introduces a novel insert-optimized array called the buffered partitioned array (BPA) to efficiently organize data in leaf nodes. Using the buffered partitioned array, the BP-tree overcomes the decades-old tradeoff between point and range operations in B⁺-trees. Experiments show that on 48 hyperthreads, the BP-tree supports slightly faster (by about 1.1×) point operations than the best-case configuration for B+-trees for point operations while supporting between 1.4×–1.7× faster range operations. On workloads generated from the Yahoo! Cloud Serving Benchmark (YCSB), the BP-tree is faster (by about 1.1×) on all point operation workloads compared to the B⁺-tree, and slower (by about 1.15×) on the short range operation workload compared to the B⁺-tree. Furthermore, this work extends the YCSB to include large scan and map workloads, commonly found in database applications, and find that the BP-tree is between 1.2×–1.4× faster than the B⁺-tree on these workloads. This thesis contains my joint work with Helen Xu, Brian Wheatman, Manoj Marneni, and Prashant Pandey."],"dc:description.degree":["M.Eng."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/150198"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"dc:rights.uri":["http://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["BP-Tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B⁺-trees"],"dc:type":["Thesis"],"thesis:degree_name":["Master","Master of Engineering in Electrical Engineering and Computer Science"]},"updated_at":"2026-07-22T22:21:57Z"}