A hybrid data structure for dense keys in in-memory database systems

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).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.by José Alberto Muñiz Navarro.M.Eng