Introduction to Database indexes.

Mani M
Mani M
March 19, 2019


Imagine a users table with first_name, last_name, address as columns and has more than 1 million records and you are trying to search for records with last_name as ‘John’. Without indexes it will iterate through all the records thereby increasing disk accesses as well as the search time. We use indexes in order to decrease the number of disk accesses and query time.

For the above example, search time without indexes is 2070 ms where as with indexes search time is 1 ms which depicts the importance of database indexes.

What is Database index

An Database index is a data structure which is used to increase the retrieval speed of a record from database.

How indexing works

An index on column is nothing but a seperate data structure of table’s records sorted on that specific column usually via B-Tree.

Index data structure.
Index data structure.

Search key is the index column value and data reference is the address of the corresponding record.

For Example, take a users table

records in users table
All records

 If you create a index on first name, the corresponding index table will look like the following table

Indexed table
Indexed table

Advantages of using database index

  • Less retrieval time.
  • Less number of disk accesses.

Disadvantages of using database index

  • More time for inserts and updates.
  • Need more memory as it has to store index records.

When to use database index

  • When cardinality is high. Cardinality is the number of unique values of that specific column.
  • Do index on a unique column.
  • Do indexing on frequently queried column.
  • Do index on a foreign key column.
  • Consider indexing keys that are used frequently to join tables in SQL statements.

When not to use database index

  • A table with lots of inserts and updates.
  • A table with small number of records.
  • When index key is large. As large keys take more memory.

Single index and Composite index

Single Index

Single index is a index on single column. Consider the same users table as above.

If we have a index on first name. The index table will look like the following table.

indexed table for single column index.
Normal indexed table.

Composite Index

Composite index is an index on multiple columns. We can combine upto 16 columns. The composite index will work as index on first column, index on combination of first two columns and so on. It is very effective if used in proper order.

Consider the same users table as above. If we have index on combination of last name and first name. It is considered as composite index as index is on multiple columns. The corresponding index table will look like the following table.

Index table for combination of multiple columns.
Composite index.