This might sound like a naive question but when are database table indexes in mysql required? How do such indexes affect performance and why?

  • 2
    I suggest you look around on DBA.SE – ratchet freak Dec 22 '12 at 23:45
  • Here are two questions in one. It is not up to the rules. – Gangnus Dec 23 '12 at 15:25

The purpose of database indexes is to increase the performance of searches in data tables.

As you might already know, for unsorted data structures, the asymptotic notation O(f(n)) for searches is O(n). Meaning that, in the worst case, all rows of the table are going to be looked in order to rows matching the WHERE clause (and the same goes for JOIN columns). It might not be that bad in a small table, but it can become really slow on a bigger table.

Since a data table cannot physically contain sorted data for multiple columns (generally speaking, it may only be physically sorted by a single column), indexes become handy. In summary, indexes are usually a B-tree (or a variant) sorted map containing a specific column data as key and the row information as the entry value. This way, the O(f(n)) can be reduced to O(log(n)).

Are indexes required? No. But your queries will show a huge performance boost, if you use indexes in the right way.

Yet the performance gain has its drawbacks: in order to increase the search performance, the insert and delete operations become slower (as the indexes must be updated). Here are some asymptotic amortized worst-case analysis for different data structures. Remember this is just an introduction on the matter. You should definitely take a deeper look on database indexes.


Basically, an index on a column allows you to very quickly find all rows of a table that have a specific value (or range of values) in that column, without having to look at every single row, and no matter how large the table is.

Thus, the index can drastically speed up queries which have a WHERE clause referring to that column, as well as JOINs and nested SELECTs. Especially for very large tables, indexes are absolutely essential to get good performance. But of course, they only help if you have them on the columns your queries actually use.

Not the answer you're looking for? Browse other questions tagged or ask your own question.