High Performance MySQL [Electronic resources] نسخه متنی

4.2 Index Structures

Having covered some of the basic
ideas behind indexing, let's turn to the various
types (or structures) of indexes in MySQL. None of the index types
are specific to MySQL. You'll find similar indexes
in PostgreSQL, DB2, Oracle, etc.

Rather than focus too much on the implementation details,^[7]
we'll look at the types of data or applications each
type was designed to handle and find answers to questions like these:
Which index types are the fastest? Most flexible? Use the most or
least space?

^[7] As with many products, the specific implementation details are
subject to change over time. By trying to take advantage of
what's under the hood, you're
inviting future problems when it does change.

If this were a general-purpose textbook for a computer science class,
we might delve deeper into the specific data structures and
algorithms that are employed under the hood. Instead,
we'll try to limit our scope to the practical. If
you're especially curious about the under-the-hood
magic, there are plenty of excellent computer science books available
on the topic.

4.2.1 B-Tree Indexes

The B-tree, or balanced tree, is the most
common types of index. Virtually all database servers and embedded
database libraries offer B-tree indexes, often as the default index
type. They are usually the default because of their unique
combination of flexibility, size, and overall good performance.

As the name implies, a B-tree is a tree structure. The nodes are
arranged in sorted order based on the key values. A B-tree is said to
be balanced because it will never become lopsided as new nodes are
added and removed. The main benefit of this balance is that the
worst-case performance of a B-tree is always quite good. B-trees
offer O(log n) performance for single-record
lookups. Unlike binary trees, in which each node has at most two
children, B-trees have many keys per node and don't
grow "tall" or
"deep" as quickly as a binary tree.

B-tree indexes offer a lot of flexibility when you need to resolve
queries. Range-base queries such as the following can be resolved
very quickly:

SELECT * FROM phone_book WHERE last_name
BETWEEN 'Marten' and 'Mason'

The server simply finds the first
"Marten" record and the last
"Mason" record. It then knows that
everything in between are also matches. The same is true of virtually
any query that involves understanding the range of values, including
MIN( ) and MAX( ) and even an
open-ended range query such as the following:

SELECT COUNT(*) FROM phone_book WHERE last_name > 'Zawodny'

MySQL will simply find the last Zawodny and count all the records
beyond it in the index tree.

4.2.2 Hash Indexes

The second most popular indexes are
hash-based. These hash indexes resemble a hash
table rather than a tree. The structure is very flat compared to a
tree. Rather than ordering index records based on a comparison of the
key value with similar key values, hash indexes are based on the
result of running each key through a hash
function. The hash function's job is to
generate a semiunique hash value (usually numeric) for any given key.
That value is then used to determine which bucket to put the key in.

Consider a common hashing function such as MD5( ).
Given similar strings as input, it produces wildly different results:

mysql> SELECT MD5('Smith');
+----------------------------------+
| MD5('Smith')                     |
+----------------------------------+
| e95f770ac4fb91ac2e4873e4b2dfc0e6 |
+----------------------------------+
1 row in set (0.46 sec)
mysql> SELECT MD5('Smitty');
+----------------------------------+
| MD5('Smitty')                    |
+----------------------------------+
| 6d6f09a116b2eded33b9c871e6797a47 |
+----------------------------------+
1 row in set (0.00 sec)

However, the MD5 algorithm produces 128-bit values (represented as
base-64 by default), which means there are just over 3.4 x
10³⁸ possible values. Because most
computers don't have nearly enough disk space (let
alone memory) to contain that many slots, hash tables are always
governed by the available storage space.

A common technique that reduces the possible key space of the hash
table is to allocate a fixed number of buckets, often a relatively
large prime number such as 35,149. You then divide the result of the
hash function by the prime number and use the remainder to determine
which bucket the value falls into.

That's the theory. The implementation details,
again, can be quite a bit more complex, and knowing them tends not to
help much. The end result is that the hash index provides very fast
lookups, generally O(1) unless you're dealing with a
hash function that doesn't produce a good spread of
values for your particular data.

While hash-based indexes generally provide some of the fastest key
lookups, they are also less flexible and less predictable than other
indexes. They're less flexible because range-based
queries can't use the index. Good hash functions
generate very different values for similar values, so the server
can't make any assumptions about the ordering of the
data within the index structure. Records that are near each other in
the hash table are rarely similar. Hash indexes are less predictable
because the wrong combination of data and hash function can result in
a hash table in which most of the records are clumped into just a few
buckets. When that happens, performance suffers quite a bit. Rather
than sifting through a relatively small list of keys that share the
same hash value, the computer must examine a large list.

Hash indexes work relatively well for most text and numeric data
types. Because hash functions effectively reduce arbitrarily sized
keys to a small hash value, they tend not to use as much space as
many tree-based indexes.

4.2.3 R-Tree Indexes

R-tree indexes are used for
spatial or
N-dimensional data. They are quite popular in mapping and geoscience
applications but work equally well in other situations in which
records are often queried based on two axes or dimensions: length and
width, height and weight, etc.

Having been added for Version 4.1, R-tree indexes are relatively new
to MySQL. MySQL's implementation is based on the
OpenGIS specifications, available
online at http://www.opengis.org/. The spatial data
support in other popular database servers is often based on the
OpenGIS specifications, so the syntax should be familiar if
you've similar products.

Spatial indexes may be unfamiliar to many long-time MySQL users, so
let's look at a simple example.
We'll create a table to contain spatial data, add
several points using X, Y coordinates, and ask MySQL which points
fall within the bounds of some polygons.

First, create the table with a small BLOB field to
contain the spatial data:

mysql> create table map_test
-> (
->   name varchar(100) not null primary key,
->   loc  geometry,
->   spatial index(loc)
-> );
Query OK, 0 rows affected (0.00 sec)

Then add some points:

mysql> insert into map_test values ('One Two', point(1,2));
Query OK, 1 row affected (0.00 sec)
mysql> insert into map_test values ('Two Two', point(2,2));
Query OK, 1 row affected (0.00 sec)
mysql> insert into map_test values ('Two One', point(2,1));
Query OK, 1 row affected (0.00 sec)

Now, ensure that it looks right in the table:

mysql> select name, AsText(loc) from map_test;
+---------+-------------+
| name    | AsText(loc) |
+---------+-------------+
| One Two | POINT(1 2)  |
| Two Two | POINT(2 2)  |
| Two One | POINT(2 1)  |
+---------+-------------+
3 rows in set (0.00 sec)

Finally, ask MySQL which points fall within a polygon:

mysql> SELECT name FROM map_test WHERE
-> Contains(GeomFromText('POLYGON((0 0, 0 3, 3 3, 3 0, 0 0))'), loc);
+---------+
| name    |
+---------+
| One Two |
| Two Two |
| Two One |
+---------+
3 rows in set (0.00 sec)

Figure 4-1 shows the points and polygon on a graph.

Figure 4-1. 2-D points and a polygon that contains them

MySQL indexes the various shapes that can be represented (points,
lines, polygons) using the shape's minimum bounding
rectangle (MBR). To do so, it computes the smallest rectangle you can
draw that completely contains the shape. MySQL stores the coordinates
of that rectangle and uses them when trying to find shapes in a given
area.