Understanding MySQL Indexes: B‑Tree, B+Tree, Hash and Their Principles

1. MySQL Index Types

MySQL supports four main index types: B‑Tree, Hash, Full‑text (MyISAM) and R‑Tree. The article focuses on B‑Tree and Hash indexes, which are the most commonly used.

Hash Index

Only the Memory storage engine uses Hash indexes by default. Hash indexes provide very fast point lookups but cannot support range queries or sorting because they store data as hash buckets.

B‑Tree Index

B‑Tree is the default index for InnoDB. It stores ordered keys in leaf nodes and includes a sequential pointer for range scans. While slower than Hash for single‑row lookups, B‑Tree excels at ordered and range queries.

B+Tree Index

MySQL actually uses B+Tree for its indexes. B+Tree stores all keys in leaf nodes and uses internal nodes only for navigation, adding a linked list between leaves to improve range‑query performance.

2. Why B+Tree Is Preferred

B+Tree aligns node size with disk page size, minimizing I/O by loading an entire node in one read. Its shallow height reduces the number of disk accesses compared to balanced binary trees.

Because leaf nodes are linked, B+Tree can scan a range by following pointers, which is essential for database workloads that frequently perform range queries.

3. Index Principles

Indexes work like a book's table of contents: they narrow the search space and turn random access into sequential access.

Effective indexing reduces disk I/O, which is orders of magnitude slower than memory access.

Left‑most Prefix Rule

For composite indexes, MySQL can use the index only from the leftmost column onward. If the leftmost column is omitted in a query, the index cannot be used.

Full‑text Index

Full‑text indexes are supported on MyISAM (and InnoDB from newer versions) and are suitable for searching large text fields. Example creation:

ALTER TABLE table_name ADD FULLTEXT(column1, column2)

Querying a full‑text index:

SELECT * FROM table_name WHERE MATCH(column1, column2) AGAINST('word1' 'word2' 'word3')

4. Index Usage Tips

Do not over‑index; each index adds write overhead and consumes disk space.

Indexes do not include columns that contain NULL values.

MySQL uses at most one index per query; ORDER BY columns may not use the same index as the WHERE clause.

LIKE 'prefix%' can use an index, but LIKE '%suffix' cannot.

5. Choosing Index Types

Prefer small, simple data types (e.g., INT over BIGINT) for indexed columns to reduce storage and improve cache efficiency.

Avoid NULLs in indexed columns when possible, and design composite indexes with the most selective columns first.

6. Common Index Statements

Ordinary index:

ALTER TABLE 'table_name' ADD INDEX index_name('col')

Unique index:

ALTER TABLE 'table_name' ADD UNIQUE('col')

Primary key (special unique index):

ALTER TABLE 'table_name' ADD PRIMARY KEY('col')

Composite index (following left‑most prefix rule):

ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3')

These commands illustrate how to create and manage indexes to optimize MySQL query performance.