Indexes are usually implemented as tree structures—mostly
complex trees—to avoid a fast decay of indexes on heavily inserted, updated, and deleted tables. To find
the physical location of a row, the address of which is stored in the
index, one must compare the key value to the value
stored in the current node of the tree to be able to determine which
sub-tree must be recursively searched. Let's now suppose that the value
that drives our search doesn't exactly match an actual column value but
can be compared to the result of a function
) applied to the column value. In that case we may be tempted
to express a condition as follows:
where f(indexed_column) = 'some value'
This kind of condition will typically torpedo the index, making it
useless. The problem is that nothing guarantees that the function
f( ) will keep the same order as the
index data; in fact, in most cases it will not. For instance, let's
suppose that our tree-index looks like Figure 3-6.
Figure 3-6. A simplistic representation of how names might be stored in an index
(If the names look familiar, it is because they are those of some of Napoleon's marshals.) Figure 3-6 is of course an outrageously simplified representation, just for the purpose of explaining a particular point; the actual indexes do not look exactly like the binary tree shown in Figure 3-6. If we look ...