为什么要用B+树做索引？底层原理与优势详解

B+树结构示意图：
        [10, 20, 30]
       /   |    |   \
   [1-9] [11-19] [21-29] [31-40]
    |       |       |       |
[1,2,3...][11,12...][21,22...][31,32...]

// 简化版的B+树节点结构
typedef struct bplus_node {
    int page_no;                    // 页号
    int page_level;                 // 节点层级（0表示叶子节点）
    int page_type;                  // 页类型
    int n_slots;                    // 槽数量
    int heap_top;                   // 堆顶部位置
    int n_records;                  // 记录数量
    int free_space;                 // 空闲空间
    int page_directory[PAGE_DIR_SIZE]; // 页目录
    char data[PAGE_SIZE];           // 实际数据
} bplus_node_t;

场景：查找id=123456的记录
 
1. 根节点读取（1次I/O）
   假设根节点有1000个键，通过二分查找定位到子节点
   
2. 中间节点读取（1次I/O）
   继续二分查找，定位到叶子节点
   
3. 叶子节点读取（1次I/O）
   在叶子节点的有序数组中找到目标记录
 
总计：3次I/O操作

-- 范围查询对比
SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31';
 
-- B树：需要中序遍历，随机I/O
-- B+树：沿着叶子节点链表顺序扫描，顺序I/O

哈希表的致命弱点：
1. 不支持范围查询（WHERE age > 18）
2. 不支持前缀匹配（WHERE name LIKE '张%'）
3. 不支持排序操作（ORDER BY）
4. 哈希冲突处理复杂
5. 不支持模糊查询

-- 这些查询哈希索引完全无能为力
SELECT * FROM users WHERE age BETWEEN 20 AND 30;
SELECT * FROM products WHERE name LIKE '手机%';
SELECT * FROM orders ORDER BY create_time DESC;

1000万条记录的不同树结构高度对比：
 
二叉搜索树：~24层
AVL树：~24层（平衡但高度不变）
红黑树：~24层（近似平衡）
B+树（1000扇出）：~3层
 
结论：B+树将24次I/O降到3次，性能提升8倍！

-- 创建表时，InnoDB会自动创建聚簇索引
CREATE TABLE users (
    id INT PRIMARY KEY,    -- 聚簇索引的键
    name VARCHAR(50),
    age INT,
    INDEX idx_name(name)   -- 二级索引也是B+树
);

-- 二级索引的B+树结构
CREATE INDEX idx_name ON users(name);

-- 覆盖索引示例
SELECT name, age FROM users WHERE name = '张三';
 
-- 如果(name, age)是联合索引，这个查询只需要访问二级索引
-- 不需要回表，性能提升50%以上！

节点分裂过程：
1. 当节点满时（16KB），选择中间键
2. 将一半数据移动到新节点
3. 更新父节点的键值
4. 如果父节点也满，递归分裂
 
实战影响：
- 插入性能：分裂操作需要3次I/O
- 空间利用率：通常保持60-70%
- 并发控制：需要锁机制保护

-- 好的B+树索引设计
CREATE INDEX idx_optimal ON orders(user_id, order_date, status);
 
-- 糟糕的B+树索引设计
CREATE INDEX idx_poor ON orders(status, user_id, order_date);

-- 这些操作会让B+树索引失效
SELECT * FROM users WHERE YEAR(create_time) = 2024;  -- 函数操作
SELECT * FROM products WHERE price + 10 > 100;      -- 表达式操作
SELECT * FROM orders WHERE order_no LIKE '%12345%'; -- 前导模糊查询

-- 利用B+树有序性优化分页
SELECT * FROM users 
WHERE id > 10000 
ORDER BY id 
LIMIT 20;
 
-- 比传统的OFFSET效率高10倍以上！

-- 监控B+树索引健康状况
SELECT 
    table_name,
    index_name,
    stat_value 
FROM mysql.innodb_index_stats 
WHERE stat_name = 'size' 
ORDER BY stat_value DESC;
 
-- 重建碎片化严重的索引
ALTER TABLE users DROP INDEX idx_name, ADD INDEX idx_name(name);