Workshop On Search Data Structures for High-Performance Databases
When: Thu, 14:00-16:00
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++.
- 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.