Indexing for High Performance - High Performance MySQL - page 153

KEY USING HASH(fname)
) ENGINE=MEMORY;

containing this data:
mysql> SELECT * FROM testhash;
+--------+-----------+
| fname | lname |
+--------+-----------+
| Arjen | Lentz |
| Baron | Schwartz |
| Peter | Zaitsev |
| Vadim | Tkachenko |
+--------+-----------+
Now suppose the index uses an imaginary hash function called f() , which returns the
following values (these are just examples, not real values):
f('Arjen')= 2323
f('Baron')= 7437
f('Peter')= 8784
f('Vadim')= 2458
The index's data structure will look like this:

Slot Value

2323 Pointer to row 1

2458 Pointer to row 4

7437 Pointer to row 2

8784 Pointer to row 3

Notice that the slots are ordered, but the rows are not. Now, when we execute this
query:
mysql> SELECT lname FROM testhash WHERE fname='Peter';

MySQL will calculate the hash of 'Peter' and use that to look up the pointer in the
index. Because f('Peter') = 8784, MySQL will look in the index for 8784 and find the
pointer to row 3. The final step is to compare the value in row 3 to 'Peter' , to make
sure it's the right row.
Because the indexes themselves store only short hash values, hash indexes are very
compact. As a result, lookups are usually lightning fast. However, hash indexes have
some limitations:
• Because the index contains only hash codes and row pointers rather than the values
themselves, MySQL can't use the values in the index to avoid reading the rows.
Fortunately, accessing the in-memory rows is very fast, so this doesn't usually de-
grade performance.