Understanding Index Structures: B+ Tree, AVL, and B Tree in MySQL

Indexes are data structures designed to shorten data retrieval time and minimize disk I/O.

Almost every data‑driven scenario uses indexes—phone contacts, file systems (ext4, XFS, NTFS), and database systems (MySQL, Oracle). Most databases and file systems store index information using B+ trees, which provide O(logN) search complexity, where N is the number of nodes.

MySQL supports four index structures: B+ tree, R‑tree, HASH, and FULLTEXT.

This article introduces B+ trees; a subsequent article will discuss the B+‑tree implementations of MySQL’s two common storage engines, MyISAM and InnoDB.

1. What is a binary tree? A binary tree is a data‑storage structure where each node has at most two child nodes.

Basic tree concepts: root node, child (son) node, parent node, leaf node, sibling node, level, height, depth, and balance factor.

Figure 1 shows a typical tree that can degenerate into a linked list, which leads to O(n) search time.

2. Balanced binary tree (AVL) An AVL tree satisfies three properties: (1) left subtree keys are smaller than the parent, (2) right subtree keys are larger than the parent, and (3) the absolute balance‑factor of every node is ≤ 1. Such trees guarantee O(logN) search complexity.

For example, finding node 5 in the illustrated AVL tree requires only two comparisons (7 → 5), while locating leaf node 10 needs at most three (7 → 9 → 10).

With 31 nodes, an AVL tree of height 4 (five levels) still provides efficient lookups, though further optimization can be achieved by using multi‑way trees.

3. B‑Tree A B‑Tree is a multi‑way AVL tree that reduces height by increasing the number of keys per node. Its properties (for order m) include: each node can have up to m children, non‑root/non‑leaf nodes have at least ⌈m/2⌉ children, and all leaf nodes appear on the same level.

Transforming the AVL example into a 4‑order B‑Tree yields a three‑level structure with fewer nodes, where each node corresponds to a disk block (e.g., 4 KB for EXT4, 8 KB for PostgreSQL, 16 KB for MySQL InnoDB).

To read a record with key 31, the system performs three disk I/Os: read the root block, follow pointer P2 to block 3, then follow pointer P4 to block 11 where the key resides.

This demonstrates that B‑Trees reduce both node count and tree depth compared with AVL trees, but storing full data in non‑leaf nodes can waste memory when the data payload is large.

4. B+‑Tree B+‑Tree refines B‑Tree by keeping only keys in non‑leaf nodes, while leaf nodes store both keys and data in an ordered (often linked) list. Searches continue down to the leaf even when a matching key is found in an internal node.

Converting the previous B‑Tree into a 6‑order B+‑Tree results in a structure where non‑leaf nodes contain only keys, and all leaf nodes are linked, combining the range‑search efficiency of B‑Trees with the sequential‑access advantage of linked lists—hence why most database indexes use B+‑Trees.

This article serves as a foundation for the next piece, which will explore MySQL’s MyISAM and InnoDB index implementations.