Databases Reference
In-Depth Information
structure for these indexes, even though they're labeled
BTREE
, and InnoDB uses
B+Trees. The variations in the structures and algorithms are out of scope for this topic,
though.
Storage engines use B-Tree indexes in various ways, which can affect performance. For
instance, MyISAM uses a prefix compression technique that makes indexes smaller,
but InnoDB leaves values uncompressed in its indexes. Also, MyISAM indexes refer to
the indexed rows by their physical storage locations, but InnoDB refers to them by their
primary key values. Each variation has benefits and drawbacks.
The general idea of a B-Tree is that all the values are stored in order, and each leaf page
is the same distance from the root.
Figure 5-1
shows an abstract representation of a B-
Tree index, which corresponds roughly to how InnoDB's indexes work. MyISAM uses
a different structure, but the principles are similar.
A B-Tree index speeds up data access because the storage engine doesn't have to scan
the whole table to find the desired data. Instead, it starts at the root node (not shown
in this figure). The slots in the root node hold pointers to child nodes, and the storage
engine follows these pointers. It finds the right pointer by looking at the values in the
node pages, which define the upper and lower bounds of the values in the child nodes.
Eventually, the storage engine either determines that the desired value doesn't exist or
successfully reaches a leaf page.
Figure 5-1. An index built on a B-Tree (technically, a B+Tree) structure
