In order to better understand SQL query performance, we must first understand what indexes are and how they are built.
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 implies three steps:
- The tree traversal
- Searching the leaf node chain
- Fetching the data from the table
Thus, an index lookup is great when reading from the b-tree only, as you avoid the linear—O(n)—full table scan, for example. That being said though, you can never avoid the overhead...