Workshop On Search Data Structures for High-Performance Databases

Spring 2021

---

Lecturers: Adam Morrison, Moshik Hershcovitch (IBM Research)

When: Thu, 14:00-16:00

Room: Dan David 204

Course Overview

Database management systems (DBMSs) rely on index data structures to locate data in database tables efficiently, without having to search every row in the table. Essentially, an index implements a map interface, which maps from keys (such as Andy) to the table row in which a pre-specified column (such as First name) matches the key. Indexes typically also support ordered iteration, which allows efficiently retrieving a range of rows. One popular index choice, for example, is the B-tree.

In this workshop, we will explore various indexes, both published in the research literature and novel designs developed at the university. We will especially focus on space-efficiency: indexes consume a significant fraction of the memory used by a DBMS engine (up to 60%), and reducing this space consumption is an important problem. Several projects will be offered, all around implementing and evaluating DBMS indexes. Programming will be done in C++.

Important information:

• Programming will be done in C++.
• Projects require significant self-learning, specifically, to understand the open-source into which we want to plug the indexes.