I finally watched Baron Schwartz’s webinar on “Optimizing Mysql Queries With Indexes”. I really wanted to watch this webinar because Baron really knows this topic well and explains things concisely. As a MySQL DBA, DBRE whatever I am these days I’m supposed to have a basic understanding of this.

The Video is available at: https://www.youtube.com/watch?v=1hAp8tNcZLA

A good supplement to this video is the “use-the-index-luke” posts

My Notes:

What is an index?

• An index is designed under the same principle as the index in a book.
• The key difference is that indexes in mysql have an entry for every page.
• Indexes may be part of or separate from the table.

Types of indexes

• B-Tree
• Hash
• Log-Structured Merge
• Other

A Table And Index

An index has as many rows as a table.

Table

a b c d
1 2 3 4 0 7 5 6 0 7 5 8 4 3 2 1

index of (b, d)

b d 2 4 3 1 7 6 7 8

Index Trees

Indexes are typically built with a tree data structure such as a (B-Tree)[https://en.wikipedia.org/wiki/B-tree]

The purpose of an index is to be able to very quickly traverse the data.

B-Tree Characteristics

• Multi-purpose, most popular index data structure
• Leaf nodes are sorted
• Supports single-row lookups
• Supports range lookups
• Supports range scanning in order (sorted access)

Most indexes are doublely linked so you can scan and sort in both directions.

Hash Index Characteristics

• Relatively Special-Purpose
• Supports single-row lookup
• Doesn’t support ordered access, bulk access, scanning

Pretty much the same thing has a hash index in a map, dict in your programming language of choice.

“Take the key you hash it that gives you a location and then you go see if the row is there”

Since the hash of the key is “random” there is no ordering

Log Structured Merge Trees

…