Interview Questions: Database Indexes

Database Indexes

hash index
Most databases support them but they're generally not the default type. ashes can deal with equality but not inequality. 
B-tree Indexes

The data structure most commonly used for database indexes are B-trees, a specific kind of self-balancing tree. 

It allows logarithmic selections, insertions, and deletions in the worst case scenario. And unlike hash indexes it stores the data in an ordered way, allowing for faster row retrieval when the selection conditions include things like inequalities or prefixes.

Other Index Types
MySQL supports R-tree indexes, which are used to query spatial data.
There are also bitmap indexes, which allow for almost instantaneous read operations but are expensive to change and take up a lot of space. They are best for columns which have only a few possible values.

What you gain for in retrieval speed you lose in insertion and deletion speed because every time you alter a table the indexes must be updated accordingly. If your table is updating frequently it's possible that having indexes will cause overall performance of your database to suffer.

There is also a space penalty, as the indexes take up space in memory or on disk. A single index is smaller than the table because it doesn't contain all the data, only pointers to the data, but in general the larger the table the larger the index

For database indexes the "value" is really a pair of values: the indexed field and a pointer to a database row. That is, rather than storing the row data right in the index, you store a pointer to the row on disk.

B-tree indexes are typically designed so that each node takes up one disk block. This allows each node to be read in with a single disk operation.

Also, for the pedants among us, many databases use B+ trees rather than classic B-trees for generic database indexes. InnoDB's BTREE index type is closer to a B+ tree than a B-tree.

R-trees, for example, allow for quicker retrieval of spatial data. For fields with only a few possible values bitmap indexes might be appropriate.
Read full article from Interview Questions: Database Indexes