MySQL 底层存储 B-Tree 和 B+Tree 原理分析

1class BTreeNode:
2    def __init__(self, m: int, is_leaf: bool = False):
3        self.num_keys: int = 0              # 当前键值数量
4        self.is_leaf: bool = is_leaf        # 是否为叶子节点
5        self.keys: List[int] = [0] * (2 * m - 1)      # 键值数组
6        self.children: List['BTreeNode'] = [None] * (2 * m)  # 子节点指针数组

 1# 内部节点（非叶子节点）
 2class BPlusTreeInternalNode:
 3    def __init__(self, m: int):
 4        self.num_keys: int = 0              # 键值数量
 5        self.keys: List[int] = [0] * m     # 键值数组
 6        self.children: List[BPlusTreeNode] = [None] * (m + 1)  # 子节点指针
 7
 8# 叶子节点
 9class BPlusTreeLeafNode:
10    def __init__(self, m: int):
11        self.num_keys: int = 0              # 键值数量
12        self.keys: List[int] = [0] * m     # 键值数组
13        self.data: List[Any] = [None] * m  # 数据指针（指向实际数据）
14        self.prev: BPlusTreeLeafNode = None  # 前驱节点指针
15        self.next: BPlusTreeLeafNode = None  # 后继节点指针

1-- 使用聚簇索引查询
2SELECT * FROM user WHERE id = 100;
3
4-- 查询路径：根节点 → 内部节点 → 叶子节点（找到完整数据）

1-- 假设 name 有二级索引
2SELECT * FROM user WHERE name = 'Tom';
3
4-- 查询路径：
5-- 1. 在 name 的二级索引 B+Tree 中找到 'Tom'
6-- 2. 获取对应的主键 id = 100
7-- 3. 通过 id 在聚簇索引中查询完整数据（回表）

1-- 假设有联合索引 (name, age)
2SELECT name, age FROM user WHERE name = 'Tom';
3
4-- 无需回表，直接从二级索引获取数据

1-- 查看页面大小
2SHOW VARIABLES LIKE 'innodb_page_size';

1-- 创建测试表
2CREATE TABLE user (
3    id INT PRIMARY KEY,
4    name VARCHAR(50),
5    age INT,
6    email VARCHAR(100)
7);

 1-- 最常见的应用
 2CREATE TABLE orders (
 3    id BIGINT PRIMARY KEY,
 4    order_no VARCHAR(32),
 5    user_id BIGINT,
 6    amount DECIMAL(10,2),
 7    created_at TIMESTAMP
 8);
 9
10-- 查询利用聚簇索引
11SELECT * FROM orders WHERE id = 123456;

1-- 为常用查询条件创建索引
2CREATE INDEX idx_user_id ON orders(user_id);
3CREATE INDEX idx_created_at ON orders(created_at);
4
5-- 联合索引（最左前缀原则）
6CREATE INDEX idx_user_created ON orders(user_id, created_at);

1-- 联合索引 (user_id, created_at)
2CREATE INDEX idx_user_created ON orders(user_id, created_at);
3
4-- ✅ 可以使用索引
5SELECT * FROM orders WHERE user_id = 100;
6SELECT * FROM orders WHERE user_id = 100 AND created_at > '2024-01-01';
7
8-- ❌ 不能使用索引（违反最左前缀）
9SELECT * FROM orders WHERE created_at > '2024-01-01';

1-- 对 email 创建前缀索引
2CREATE INDEX idx_email_prefix ON orders(email(20));
3
4-- 对备注字段创建前缀索引
5CREATE INDEX idx_comment_prefix ON article(comment(100));

1-- ✅ 好的索引：高频查询条件
2CREATE INDEX idx_user_status ON user(user_id, status);
3
4-- ❌ 不好的索引：低区分度的字段
5CREATE INDEX idx_gender ON user(gender);  -- gender 只有男/女，区分度低
6
7-- ❌ 冗余索引
8CREATE INDEX idx_a ON table(a);
9CREATE INDEX idx_a_b ON table(a, b);  -- idx_a 可以被 idx_a_b 覆盖

1-- 假设有联合索引 (user_id, status, created_at)
2
3-- ✅ 覆盖索引，无需回表
4SELECT user_id, status, created_at
5FROM orders
6WHERE user_id = 100;
7
8-- ❌ 需要回表
9SELECT * FROM orders WHERE user_id = 100;

 1-- ✅ 可以使用索引
 2SELECT * FROM orders WHERE user_id = 100;
 3SELECT * FROM orders WHERE user_id > 100;
 4
 5-- ❌ 索引失效：对字段进行函数运算
 6SELECT * FROM orders WHERE UPPER(user_name) = 'TOM';
 7
 8-- ❌ 索引失效：类型转换
 9SELECT * FROM orders WHERE user_id = '100';  -- 字符串转数字
10
11-- ✅ 解决方案：使用函数索引或正确类型
12SELECT * FROM orders WHERE user_id = 100;

1-- ❌ 索引失效
2SELECT * FROM orders WHERE user_id + 1 = 101;
3
4-- ✅ 优化后
5SELECT * FROM orders WHERE user_id = 100;

1-- ✅ 使用索引
2WHERE user_id IN (1, 2, 3)
3
4-- ❌ 可能不使用索引（取决于优化器）
5WHERE user_id NOT IN (1, 2, 3)

1-- ✅ Hash 索引支持
2SELECT * FROM user WHERE id = 100;
3
4-- ❌ Hash 索引不支持
5SELECT * FROM user WHERE id BETWEEN 100 AND 200;
6SELECT * FROM user WHERE id > 100;
7SELECT * FROM user ORDER BY id;

 1-- ❌ 不好的主键：长字符串
 2CREATE TABLE order_log (
 3    order_no VARCHAR(32) PRIMARY KEY,  -- 主键太长，B+Tree 深度高
 4    content TEXT
 5);
 6
 7-- ✅ 好的主键：自增整数
 8CREATE TABLE order_log (
 9    id BIGINT AUTO_INCREMENT PRIMARY KEY,
10    order_no VARCHAR(32),
11    content TEXT
12);

1-- 查看表的索引
2SHOW INDEX FROM user;
3
4-- 使用 EXPLAIN 分析查询执行计划
5EXPLAIN SELECT * FROM user WHERE id = 100;
6
7-- 查看索引使用统计（MySQL 8.0+）
8SELECT * FROM performance_schema.table_io_waits_summary_by_index_usage
9WHERE OBJECT_SCHEMA = 'your_database';