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 ...
