Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines

Data structures are the means by which software programs store and retrieve data. This monograph focuses on key-value data structures, which are widely used for data-intensive applications thanks to the versatility of the key-value data model. Key-value data structures constitute the core of any data-driven system. They provide the means to store, search, and modify data residing at various levels of the storage and memory hierarchy. Designing efficient data structures for given workloads has long been a focus of research and practice in both academia and industry. Data Structures for Data-Intensive Applications explains the space of data structure design choices, how to select the appropriate data structure depending on the goals and workload of an application at hand, and how the ever-evolving hardware and data properties require innovations in data structure design. The overarching goal is to help the reader both select the best existing data structures and design and build new ones.