今天咱们来聊聊MySQL中的索引是怎么实现的，主要围绕InnoDB存储引擎的实现原理。作为一个资深Java开发工程师，我经常看到面试官问：“MySQL的索引底层是怎么实现的？”这个问题看似简单，其实考察的知识点挺深的，搞不明白就容易掉坑里。
首先，MySQL的InnoDB存储引擎使用的是B+树来实现索引结构。为什么是B+树而不是B树或者其他数据结构？这个选择不是拍脑袋决定的，而是数据库领域数十年积累下来的结果。
B+树的结构是怎样的？
B+树是一种多叉平衡树。简单理解，它是一个多层的“楼房”，每层节点存储的索引值是有序的，非叶子节点不存储实际数据，只存储索引和指针，用来指导“去哪一层找”。
在B+树中，所有的数据都存储在叶子节点上，叶子节点之间还通过双向链表相连。这样设计有几个好处：
- 磁盘读取高效： 因为每个节点的容量较大，可以一次性读取更多数据，减少磁盘I/O次数。
- 范围查询友好： 因为叶子节点形成了有序链表，做范围查询时，只需要顺序扫描叶子节点。
- 平衡性： B+树自动维护平衡，插入、删除节点时树高度不会失控。
B+树索引查找是怎么做的？
假设有一个商品表product，有一列id作为主键，我们想通过下面这条SQL查询商品信息：
SELECT * FROM product WHERE id = 5;
查询过程是这样的：
-
从根节点开始比较，假设根节点存储的索引是
(1, 10, 20)。 - 查询
id=5，发现5在1和10之间，于是进入对应的子节点。 - 在第二层节点中，假设存储的是
(1, 4, 7)，发现5又在4和7之间，于是进入下一个子节点。 - 在第三层的叶子节点中，假设存储的是
(4, 5, 6)，这时找到了目标数据id=5，查找成功。
整个查找过程经历了3次磁盘I/O操作。
为什么选择B+树？
B+树的设计主要是为了解决数据库频繁读写磁盘的问题。在磁盘中，磁盘I/O是非常昂贵的操作，数据库的目标就是尽量减少I/O次数。由于B+树是多叉树，树的高度较小，即使存储几百万条数据，通常也只需要3-4次磁盘I/O就能找到目标数据。
此外，B+树的叶子节点之间有链表连接，非常适合区间查询，例如：
SELECT * FROM product WHERE id BETWEEN 5 AND 15;
数据库从id=5的叶子节点开始，顺着链表一直找到id=15，高效完成范围查询。
主键索引和普通索引的区别
主键索引： 主键索引是B+树的一个聚集索引，表中的数据物理存储方式是按照主键的顺序排列的。因此，通过主键查询非常高效。
普通索引： 普通索引是一个辅助索引，叶子节点存储的不是实际数据，而是主键值。查询时需要先查到主键值，然后再通过主键索引定位到实际数据。这叫“回表”操作。
示例代码演示
以下是一个简单的Java代码示例，模拟B+树节点的结构：
import java.util.*;
class BPlusTreeNode {
int[] keys;
BPlusTreeNode[] children;
boolean isLeaf;
BPlusTreeNode(int order) {
keys = new int[order - 1];
children = new BPlusTreeNode[order];
isLeaf = true;
}
}
public class BPlusTree {
private BPlusTreeNode root;
public BPlusTree(int order) {
root = new BPlusTreeNode(order);
}
public void search(int key) {
BPlusTreeNode current = root;
while (!current.isLeaf) {
int i = 0;
while (i current.keys[i]) {
i++;
}
current = current.children[i];
}
System.out.println("Found key " + key + " in leaf node.");
}
public static void main(String[] args) {
BPlusTree tree = new BPlusTree(4);
tree.search(5); // 模拟查询
}
}
这段代码只是简单展示了B+树的查找过程，实际数据库引擎的实现远比这复杂得多。
最后，面试官问你：MySQL中的索引是如何实现的？为什么选择B+树？
你的回答：
MySQL InnoDB存储引擎的索引使用B+树作为数据结构。B+树是一种多叉平衡树，叶子节点存储所有数据，非叶子节点只存储索引和指针。B+树的特点是树的高度较小，即使在存储百万级别的数据时，树的高度通常也只有3-4层，因此磁盘I/O次数很少。
选择B+树的原因有以下几点：
- 磁盘I/O优化： B+树节点存储容量大，减少了磁盘读取次数。
- 范围查询高效： 叶子节点形成双向链表，做范围查询时可以顺序扫描。
- 自动平衡： B+树自动保持平衡，插入、删除操作不会导致树高度失控。
此外，主键索引和普通索引在存储和查找上也有差异。主键索引是聚集索引，存储了实际数据，而普通索引是辅助索引，存储的是主键值，需要回表查询。
