What is a database index? [duplicate]

I wrote a complete book about it! It's also available for free on the web: http://use-the-index-luke.com/

I try to answer your questions shortly—which is not exactly what I'm good at. The last time I tried, I ended up writing a book...

Like tables, indexes consist of rows and columns but store the data in a logically sorted manner to improve search performance. Think of it like a telephone book (a printed one). They are usually sorted last_name, first_name and potentially other criteria (e.g. zip code). This sorting makes it possible to find all entries for a specific last name quickly. If you know the first name too, you can even find the entries for the combination last name/first name very quickly.

If you just know the first name, however, the telephone book does not really help you. The very same is true for multi-column database indexes. So yes, an index can potentially improve search performance. If you have the wrong index for your question (e.g. a phonebook when searching by first name) they might be useless.

You can have many indexes on the same table but on different columns. So, an index on last_name,first_name is different from an index on first_name only (which you would need to optimize searches by first name).

Indexes hold redundant data (ex: clustered indexes = telephone book). They have the same information as stored in the table (ex: function based indexes), but in a sorted manner. This redundancy is automatically maintained by the database for each write operation you perform (insert/update/delete). Consequently, indexed decrease write performance.

Besides finding data quickly, indexes can also be used to optimize sort operations (order by) and physically arrange related data closely together (clustering).

To get a better idea, look at the full table of contents of my book: http://use-the-index-luke.com/sql/table-of-contents

Think of it as a table of contents for tables. If it's there, the database knows where to look more specific. If it ain't there, the database has to search through all the data to find it.

A way more detailed explanation can be found here in this Wikipedia article.

A database index is a datastructure aimed at improving the time complexity of lookup operation.

Lookup with no index is in worst case O(N) complexity. Efficient lookup with index enables logarithmic O(log(N)) or even with some architechture O(1) complexity.

A database index also make it possible to enforce DB constraints. Many DB systems set a index on a set of columns referred to as PRIMARY KEY. Some DB systems requires columns in a FOREIGN KEY to be indexed, so as to speed up operations (insert, update).