These are notes that I took about SQL Indexing from http://use-the-index-luke.com

Introduction

An index makes a SQL query fast.
An index is a distinct structure in the DB that requires its own space.
A DB index is similar to index of a book - key concept is all entries are arranged in a well-defined order. Finding data in an ordered set is fast and easy because the sort order determines each entries position.
A DB index however undergoes constant change. Whenever INSERT, UPDATE, DELETE's are executed, the index must also be updated without moving around large amounts of data.
The DB combines two data structures for providing indexing - doubly linked lists and search trees.

SQL Indexing