Databases Reference
In-Depth Information
Leaf pages are special, because they have pointers to the indexed data instead of
pointers to other pages. (Different storage engines have different types of “pointers” to
the data.) Our illustration shows only one node page and its leaf pages, but there might
be many levels of node pages between the root and the leaves. The tree's depth depends
on how big the table is.
Because B-Trees store the indexed columns in order, they're useful for searching for
ranges of data. For instance, descending the tree for an index on a text field passes
through values in alphabetical order, so looking for “everyone whose name begins with
I through K” is efficient.
Suppose you have the following table:
CREATE TABLE People (
last_name varchar(50) not null,
first_name varchar(50) not null,
dob date not null,
gender enum('m', 'f')not null,
key(last_name, first_name, dob)
);
The index will contain the values from the
last_name
,
first_name
, and
dob
columns for
every row in the table.
Figure 5-2
illustrates how the index arranges the data it stores.
Figure 5-2. Sample entries from a B-Tree (technically, a B+Tree) index
