In order to better understand SQL query performance, we must first understand what indexes are and how they are built.
SQL query performance
The structure of indexes
An index is an ordered list of table elements. These elements are first stored in a physically unordered doubly linked list. The list is doubly linked to the table through pointers to the table entries and to a second structure that stores the index values in a logical order, a balanced tree or b-tree. Thus, indexes have an algorithmic complexity that is logarithmic—O(log n)—for read operations on average, which means that the database engine should maintain speed even if there is a significant number of entries in the table. Indeed, an index lookup...
