How do indexes speed up searches?

Question

How do indexes help in speeding up searching for data based on specific criteria?

If there's a table with 6 columns and none of them are indexed, the program has to check all table rows.

Indexing involves creating another separate table with just two columns, the id and the column you want indexed.

What I don't understand, is how does that help the application do faster searches? It doesn't read the entire 6 column table, but it still has to read the entire 2 column table, right? Which has the same number of rows...

You should take a look at [this answer](http://stackoverflow.com/a/1130/27439) as it gives a good explanation of database indexes. — Vincent Ramdhanie, Dec 26 '13 at 19:10

score 6 · Accepted Answer · answered Dec 26 '13 at 19:10

It functions a lot like an index in a book. We don't read the entire index to find the entry we want, and once we find the entry, we don't keep reading the index for other instances of that same entry. Once we find the entry, we don't have to read the entire book, just jump to the entry we want. These operations are in normal table lookups and indexing saves us time much in the same way a book index would.

score 4 · Answer 2 · edited Feb 17 '17 at 19:21

4

Creating an index basically creates either an on-disk hash table or an on-disk search tree (usually some sort of B Tree).

Searching a hash table for an exact match is O(1) while searching either an exact match or closest matches in an ordered search tree is O(log(n)).

This is in contrast to scanning the entire table, which is O(n).

edited Feb 17 '17 at 19:21

catch23

17,519
42
144
217

answered Dec 26 '13 at 19:06

Lie Ryan

62,238
13
100
144

How do indexes speed up searches?

2 Answers2