Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines
By Manos Athanassoulis, Boston University, USA, mathan@bu.edu | Stratos Idreos, Harvard University, USA, stratos@seas.harvard.edu | Dennis Shasha, New York University, USA, shasha@cs.nyu.edu
Abstract
Key-value data structures constitute the core of any datadriven system. They provide the means to store, search, and modify data residing at various levels of the storage and memory hierarchy, from durable storage (spinning disks, solid state disks, and other non-volatile memories) to random access memory, caches, and registers. Designing efficient data structures for given workloads has long been a focus of research and practice in both academia and industry.
This book outlines the underlying design dimensions of data structures and shows how they can be combined to support (or fail to support) various workloads. The book further shows how these design dimensions can lead to an understanding of the behavior of individual state-of-the-art data structures and their hybrids. Finally, this systematization of the design space and the accompanying guidelines will enable you to select the most fitting data structure or even to invent an entirely new data structure for a given workload.
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.
