Indexes allow us to find quickly the addresses (references to some particular storage in persistent memory, typically file identifiers and offsets within the files) of the rows that contain a key we are looking for. Once we have an address, then it can be translated into a low-level, operating system reference which, if we are lucky, will direct us to the true memory address where the data is located. Alternatively, the index search will result in some input/output operation taking place before we have the data at our disposal in memory.
As discussed previously in Chapter
3, when the value of a key we are looking for refers to a very
large number of rows, it is often more efficient simply to scan the
table from the beginning to the end and ignore the indexes. This is why,
at least in a transactional database, it is useless to index columns
with a low number of distinct values (i.e., a low
cardinality) unless one value is highly selective
and appears frequently in
clauses. Other indexes that we can dispose of are single-column indexes
on columns that already participate in composite indexes as the leading
column: there is no need whatsoever to index the same column twice in
these circumstances. The very common tree-structured, or hierarchical,
index can be efficiently searched even if we do not have the full key
value, just as long as we have a sufficient number of leading bytes to
The use of leading ...