How does a database index work?
Database Index Tips |
|
From the MySQL Manual - |
Indexes are used to find rows with specific column values fast. Without an index, MySQL has to start with the first record and then read through the whole table to find the relevant rows. The larger the table, the more this costs. If the table has an index for the columns in question, MySQL can quickly determine the position to seek to in the middle of the data file without having to look at all the data. If a table has 1,000 rows, this is at least 100 times faster than reading sequentially. Note that if you need to access almost all 1,000 rows, it is faster to read sequentially, because that minimizes disk seeks. Most MySQL indexes ( , , , and ) are stored in B-trees. Exceptions are that indexes on spatial column types use R-trees, and ( ) tables support hash indexes. Strings are automatically prefix- and end-space compressed. In general, indexes are used as described in the following discussion. Characteristics specific to hash indexes (as used in tables) are described at the end of this section.
statement: If a multiple-column index exists on and , the appropriate rows can be fetched directly. If separate single-column indexes exist on and , the optimizer tries to find the most restrictive index by deciding which index will find fewer rows and using that index to fetch the rows. If the table has a multiple-column index, any leftmost prefix of the index can be used by the optimizer to find rows. For example, if you have a three-column index on , you have indexed search capabilities on , , and . MySQL can't use a partial index if the columns don't form a leftmost prefix of the index. Suppose that you have the statements shown here: If an index exists on , only the first of the preceding queries uses the index. The second and third queries do involve indexed columns, but and are not leftmost prefixes of . An index is used for columns that you compare with the , , , , , or operators. MySQL also uses indexes for comparisons if the argument to is a constant string that doesn't start with a wildcard character. For example, the following statements use indexes: In the first statement, only rows with are considered. In the second statement, only rows with are considered. The following statements will not use indexes: In the first statement, the value begins with a wildcard character. In the second statement, the value is not a constant. MySQL 4.0 and up performs an additional optimization. If you use and string is longer than three characters, MySQL will use the algorithm to initialize the pattern for the string and then use this pattern to perform the search quicker. Searching using will use indexes if col_name is indexed. Any index that doesn't span all levels in the clause is not used to optimize the query. In other words, to be able to use an index, a prefix of the index must be used in every group. The following clauses use indexes: These clauses do not use indexes: Sometimes MySQL will not use an index, even if one is available. One way this occurs is when the optimizer estimates that using the index would require MySQL to access a large percentage of the rows in the table. (In this case, a table scan is probably much faster, because it will require many fewer seeks.) However, if such a query uses to only retrieve part of the rows, MySQL will use an index anyway, because it can much more quickly find the few rows to return in the result. Hash indexes have somewhat different characteristics than those just discussed:
|