Mastering MySQL Indexes: From Hash Tables to B+ Trees and Optimization Tips

1. Basic Concepts

Indexes are data structures that allow fast lookup, similar to a directory, reducing I/O by avoiding full‑table scans.

2. Index Structures

Hash table : key‑value mapping with O(1) lookup, supporting only equality queries.

Ordered array : supports equality and range queries with O(log N) lookup, but inserts require moving many records.

Binary tree : classic tree; balanced trees give O(log N) lookup, while unbalanced trees degrade to O(N).

B‑tree : multi‑way tree reduces height compared to binary trees, suitable for disk‑based storage.

B+‑tree : leaf nodes store all keys and data, internal nodes store only keys, enabling efficient range scans and serving as covering indexes.

3. InnoDB Index Types

Primary (clustered) index : leaf nodes contain the whole row.

Secondary index : leaf nodes store the primary‑key value.

Covering index : all columns needed by the query are present in the index, eliminating the need to read the table.

Composite (joint) index : combines multiple columns and follows the left‑most prefix rule.

Prefix index : indexes only the first N characters of a string to save space, but may increase the number of row lookups.

4. Query Optimization Tips

Avoid creating too many indexes; each index adds write overhead.

Place columns used for ORDER BY in an index to avoid filesort.

Use EXPLAIN to verify which index MySQL chooses.

Refresh statistics with ANALYZE TABLE or force a specific index when the optimizer picks a sub‑optimal one.

5. Practical Advice

Do not use indexes on low‑cardinality columns, on very small tables, or without selective WHERE clauses. Prefer composite indexes that cover query predicates and ordering, and consider the trade‑off between space and query speed when using prefix indexes.

SELECT id, park_code, park_name, biz_type, biz_id, approve_type, approve_status, assignee, assignee_name, creator_name, data_before, data_after, data_update, attachment, reason, opinion, process_order, assignee_code_list, assignee_code_user_list, deleted, creator, operator, extra, gmt_create, gmt_modified FROM approval_list WHERE (park_code IN ('P_1','P_2','P_3','P_4','P_5','P_6','P_7','P_8','P_9','P_10','P_11','P_12','P_13','P_14','P_15','P_16','P_17','P_18','P_19','P_20','P_21','P_22','P_23','P_24','P_25','P_26','P_27','P_28','P_29','P_30','P_31','P_32','P_33','P_34','P_35','P_36','P_37','P_38','P_39','P_40') AND deleted = 0) ORDER BY approve_status ASC, id DESC LIMIT 10