Database index is similar to the book index that helps you quickly locate the information you want. Without index, you need to do table scan to find out a set of records that match - O(n). However, to maintain a separate list of indexes’ values and keep them updated as your data change (insert/ update/ delete), you introduce overhead as well. So, we don’t index every column in a table.Multicolumn indexes
Some of the indexes have more than 1 columns (multi-column). Such indexes can improve the query speed if you often query all columns together in the WHERE clause or if a single column doesn’t have sufficient variety (not selective as >25% of the rows have the same value in this column - table scan is better for that). For example, you create multicolumn index for last_name & first_name that gives you fewer rows than just look at last name. If you create 2 indexes instead of multicolumn index, it will not be helpful as MySQL won’t use them at the same time. In fact, MySQL will ever use one index per table per query except for UNION. To choose the index, MySQL will pick the one that gives fewer rows back based on some statistics. If you create a composite (multi-column) index, the order of the columns in the key are very important. Try to order the columns in the key as to enhance selectivity, with the most selective columns to the leftmost of the key.

ALTER TABLE phone_book INDEX (last_name, first_name)

If a multiple-column index exists on col1 and col2, the appropriate rows can be fetched directly. If separate single-column indexes exist on col1 and col2, the optimizer tries to find the most restrictive index by deciding which index finds fewer rows and using that index to fetch the rows. If the table has a multiple-column index, any leftmost prefix of the index can be used by the optimizer to find rows. For example, if you have a three-column index on (col1, col2, col3), you have indexed search capabilities on (col1), (col1, col2), and (col1, col2, col3).

MySQL can’t use a partial index if the columns don’t form a leftmost prefix of the index. Suppose that you have the SELECT statements shown here:

SELECT * FROM tbl_name WHERE col1=val1;
SELECT * FROM tbl_name WHERE col2=val2;
SELECT * FROM tbl_name WHERE col2=val2 AND col3=val3;

If an index exists on (col1, col2, col3), only the first of the preceding queries uses the index. The second and third queries do involve indexed columns, but (col2) and (col2, col3) are not leftmost prefixes of (col1, col2, col3).

Clustered Index
Indexes are normally kept in a completely separate file that contains a list of primary (and possibly secondary) keys and a value that represents the byte offset of the record. These ensure MySQL can find and then quickly skip ot that point within database to locate record. MySQL has to store the indexes this way because the records are stored in essentially random order.

With clustered indexes, primary key and the record itself are “clusterd” together, and the records are all stored in primary-key order. InnoDB uses clustered indexes. In Oracle, clustered indexes are known as “index-organized tables”. When your data is almost always searched on via its primary key, clustered indexes can make lookups incredibly fast. For a standard MyISAM index, there are 2 lookups,  one to the index, and a second to the table itself via the location specified in the index. With clustered indexes, there is single lookup only.

Index Structure

B-Tree Indexes

Balanced tree is a most common type of index. It is the default index structure because of its unique combination of flexibility, size, and overall performance. As indicated in its name, B-tree is a tree and nodes are arranged in sorted order based on the key values. A B-tree is said to be balanced because it will never become lopsided as new nodes are added and removed. The main benefit of this balance is that the worst-case performance of a B-tree is always quite good. It offers O(log n) performance for single-record lookups. Unlike binary tree, B-tree has many keys per node and don’t grow tall or deep as quick as a binary tree. B-tree indexes offer a lot of flexibility when you need to resolve queries esp range-base query. For example:

SELECT * FROM phone_book WHERE last_name BETWEEN 'Marten' and 'Mason';

The server simply finds the first ‘Marten’ record and the last ‘Mason’ record. It then knows that everything in between are also matches.

A B-tree index can be used for column comparisons in expressions that use the =, >, >=, <, <=, or BETWEEN operators. The index also can be used for LIKE comparisons if the argument to LIKE is a constant string that doesn’t start with a wildcard character. For example, the following SELECT statements use indexes:

SELECT * FROM tbl_name WHERE key_col LIKE 'Patrick%';
SELECT * FROM tbl_name WHERE key_col LIKE 'Pat%_ck%';

Hash Indexes

Hash indexes resemble to a hashtable rather than a tree. The structure is very flat compared to a tree. Rather than ordering index records based on a comparison of the key value with similar key values, hash indexes are based on the result of running each key through a hash function. The end result is that the hash index provides very fast lookup O(1).

Given a key k, store it in an array T with position h(k) where h is the hash function.