Most query engines have a query optimizer, which tries to come up with a good plan for executing queries. The query optimizer will run an index scan or index seek, or a table scan, if there are any accessible indexes, which can speed up a query.
Example:
SELECT * FROM tbl WHERE category_id = 5;
If the category id does not have an index, a table scan—in which every entry in the table is checked for the correct category id—will be carried out.
However, things get more complicated if the category id is indexed. It's likely that an index seek will be used if the table is really large. However, if the table is tiny, the optimizer may decide that a table scan is still quicker because accessing an index incurs some overhead. Scanning the table may be quicker even for large tables if the category id is not discriminating enough, such as if there are only two categories.
Typically, tree structures are used to organize indexes. An O(log n) operation is required to locate an item in a tree. It takes O(n) operations to scan a table. The number of disc accesses necessary to complete the query mostly determines the speed. For tiny tables, accessing the index first and the table for the discovered entries second can result in additional disc accesses.
Let us have a look at another query:
SELECT category_id FROM tbl WHERE category_id BETWEEN 10 AND 100;
Another solution is available in this situation. In this case, an index seek (as opposed to an index scan) might not be quicker than a table scan, but since we are only retrieving category ids, it might be. Instead of utilizing the tree structure, an index scan reads each entry of the index table (what the index seek does). However, since the requested data is all contained in the index, there will be no need to access the data table. Similar to a table scan, an index scan also uses an O(n) operation, however, because an index is typically smaller than a table, it uses fewer disc accesses.
