{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/62662"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/62662","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"A hybrid data structure for dense keys in in-memory database systems","abstract":"This thesis presents a data structure which performs well for in-memory indexing of keys that are unevenly distributed into clusters with a high density of keys. This pattern is prevalent, for example, in systems that use tables with keys where one field is auto-incremented. These types of tables are widely used. The proposed data structure consists of a B+ Tree with intervals as keys, and arrays as values. Each array holds a cluster of values, while the clusters themselves are managed by the B+ Tree for space and cache efficiency. Using the H-Tree as an in-memory indexing structure for an implementation of the TPC-C benchmark sped up the transaction processing time by up to 50% compared to an implementation based on B+Trees, and showed even more dramatic performance gains in the presence of few and large clusters of data.","abstract_html":"This thesis presents a data structure which performs well for in-memory indexing of keys that are unevenly distributed into clusters with a high density of keys. This pattern is prevalent, for example, in systems that use tables with keys where one field is auto-incremented. These types of tables are widely used. The proposed data structure consists of a B+ Tree with intervals as keys, and arrays as values. Each array holds a cluster of values, while the clusters themselves are managed by the B+ Tree for space and cache efficiency. Using the H-Tree as an in-memory indexing structure for an implementation of the TPC-C benchmark sped up the transaction processing time by up to 50% compared to an implementation based on B+Trees, and showed even more dramatic performance gains in the presence of few and large clusters of data.","abstract_has_math":false,"creators":["Muñiz Navarro, José Alberto"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Samuel Madden."],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010","date_published":"2010","updated_at":"2026-07-22T22:21:58Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/62662","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Samuel Madden."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Muñiz Navarro, José Alberto"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2011-05-09T15:16:16Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2011-05-09T15:16:16Z"]},{"key":"dc:date.issued","label":"Date","values":["2010"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/62662"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 71-72)."]},{"key":"dc:description.abstract","label":"Abstract","values":["This thesis presents a data structure which performs well for in-memory indexing of keys that are unevenly distributed into clusters with a high density of keys. This pattern is prevalent, for example, in systems that use tables with keys where one field is auto-incremented. These types of tables are widely used. The proposed data structure consists of a B+ Tree with intervals as keys, and arrays as values. Each array holds a cluster of values, while the clusters themselves are managed by the B+ Tree for space and cache efficiency. Using the H-Tree as an in-memory indexing structure for an implementation of the TPC-C benchmark sped up the transaction processing time by up to 50% compared to an implementation based on B+Trees, and showed even more dramatic performance gains in the presence of few and large clusters of data."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:title","label":"Title","values":["A hybrid data structure for dense keys in in-memory database systems"]}]}],"canonical_facts":{"dc:contributor.advisor":["Samuel Madden."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Muñiz Navarro, José Alberto"],"dc:date.accessioned":["2011-05-09T15:16:16Z"],"dc:date.available":["2011-05-09T15:16:16Z"],"dc:date.issued":["2010"],"dc:description":["Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 71-72)."],"dc:description.abstract":["This thesis presents a data structure which performs well for in-memory indexing of keys that are unevenly distributed into clusters with a high density of keys. This pattern is prevalent, for example, in systems that use tables with keys where one field is auto-incremented. These types of tables are widely used. The proposed data structure consists of a B+ Tree with intervals as keys, and arrays as values. Each array holds a cluster of values, while the clusters themselves are managed by the B+ Tree for space and cache efficiency. Using the H-Tree as an in-memory indexing structure for an implementation of the TPC-C benchmark sped up the transaction processing time by up to 50% compared to an implementation based on B+Trees, and showed even more dramatic performance gains in the presence of few and large clusters of data."],"dc:description.degree":["M.Eng."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/62662"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["A hybrid data structure for dense keys in in-memory database systems"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:58Z"}