Where indexes point

An index maps a key to something. This unit is about what that something is, and about keys made of more than one column.

Secondary indexes

The primary key names exactly one row. A secondary index lets you search by another column, like city. Many rows can share one city, so the index must handle repeats. Either each entry holds a list of matching row IDs, or the row ID is added to the key so every entry is unique.

Clustered index or heap file

A clustered index keeps the whole row inside the index. Otherwise the index points to the row. The pointer can be the row's primary key, or its place in a heap file, where rows sit in no order. If a row in a heap file grows and must move, every index must be updated, or a forwarding pointer is left at the old place.

Covering indexes

A covering index copies a few extra columns into the index. If a query needs only those columns, the database never opens the main row. The price: the copied data takes space, and every write must update it.

Concatenated indexes

A concatenated index joins several columns into one key, in a fixed order, like a phone book sorted by last name, then first name. It helps queries on the first column, or the first and second, but not the second alone.

Multidimensional indexes

"Find cafes inside this map box" filters on a latitude range and a longitude range at once. A (latitude, longitude) index can narrow only one of them; the other must be checked row by row. R-trees keep nearby points together, so both ranges narrow at once. Grids, or a space-filling curve that turns two numbers into one, also work.

Remember

• Secondary keys repeat; store row lists or add the row ID.
• Clustered holds the whole row; covering holds a few extra columns.
• A concatenated index only helps its leading columns.
• Two ranges at once need a multidimensional index.