Databases Reference
In-Depth Information
Other types of index
Several third-party storage engines use different types of data structures for their in-
dexes. For example, TokuDB uses fractal tree indexes. This is a newly developed data
structure that has some of the same benefits as B-Tree indexes, without some of the
drawbacks. As you read through this chapter, you'll see many InnoDB topics, including
clustered indexes and covering indexes. In most cases, the discussions of InnoDB apply
equally well to TokuDB.
ScaleDB uses Patricia tries (that's not a typo), and other technologies such as InfiniDB
or Infobright have their own special data structures for optimizing queries.
Benefits of Indexes
Indexes enable the server to navigate quickly to a desired position in the table, but that's
not all they're good for. As you've probably gathered by now, indexes have several
additional benefits, based on the properties of the data structures used to create them.
B-Tree indexes, which are the most common type you'll use, function by storing the
data in sorted order, and MySQL can exploit that for queries with clauses such as
ORDER
BY
and
GROUP BY
. Because the data is presorted, a B-Tree index also stores related values
close together. Finally, the index actually stores a copy of the values, so some queries
can be satisfied from the index alone. Three main benefits proceed from these
properties:
1. Indexes reduce the amount of data the server has to examine.
2. Indexes help the server avoid sorting and temporary tables.
3. Indexes turn random I/O into sequential I/O.
This subject really deserves an entire topic. For those who would like to dig in deeply,
we recommend
Relational Database Index Design and the Optimizers
, by Tapio Lah-
denmaki and Mike Leach (Wiley). It explains topics such as how to calculate the costs
and benefits of indexes, how to estimate query speed, and how to determine whether
indexes will be more expensive to maintain than the benefit they provide.
Lahdenmaki and Leach's topic also introduces a three-star system for grading how
suitable an index is for a query. The index earns one star if it places relevant rows
adjacent to each other, a second star if its rows are sorted in the order the query needs,
and a final star if it contains all the columns needed for the query.
We'll return to these principles throughout this chapter.
