Lecture: State-of-the-Art Database Index Maintenance

This talk will explain how B-trees, Log-Structured Merge Trees and
Streaming B-trees operate, and what is their asympotic performance.
The talk is aimed at people who are interested in understanding the
state-of-the-art for maintaining indexes for databases such as MySQL,
MongoDB, or HBase.

We actually have a 3-hour tutorial, the abstract for which follows. We'd be happy to give the full tutorial rather than the 1-hour version described in the abstract above.
Data Structures and Algorithms for Big Databases
Abstract for 3-hour tutorial:

Speakers: Michael A. Bender / SUNY Stony Brook
Bradley C. Kuszmaul / MIT

This tutorial will explore data structures and algorithms for big
databases. The topics include
- Data structures including B-trees, Log Structured Merge Trees, and
Streaming B-trees.
- Approximate Query Membership data structures including Bloom filters and
cascade filters.
- Algorithms for join including hash joins and Graefe's generalized join.
- Index design, including covering indexes.
- Consistency (row locks, multiversion concurrency).
- Getting good performance in memory.
- Cache efficiency including both Cache-aware and Cache-oblivious data
structures and algorithms.

These algorithms and data structures are used both in NoSQL
implementations such as MongoDB, HBase and in SQL-oriented
implementations such as MySQl and TokuDB.

This talk includes explaining and analyzing data structures. So it
might not be aimed at someone who hates seeing O(N \log N). But we'll
keep the content accessible so that anyone who can tolerate some math
will benefit from attending.

Info

Day: 2012-08-26
Start time: 10:00
Duration: 01:00
Room: C120/Databases
Track: Databases
Language: en

Links:

Feedback

Click here to let us know how you liked this event.

Concurrent Events