1
// B+ 树范围查询伪代码
2
func (t *BTree) rangeQuery(min, max int) []Value {
3
    // 1. 找到起始叶子节点
4
    node := t.findLeaf(min)
5

6
    // 2. 顺序遍历叶子节点链表
7
    var results []Value
8
    for node != nil {
9
        for _, entry := range node.entries {
10
            if entry.key > max {
11
                return results
12
            }
13
            if entry.key >= min {
14
                results = append(results, entry.value)
15
            }
16
        }
17
        node = node.next  // 链表跳转
18
    }
19
    return results
20
}

1
每个 Entry = 8 + 8 + 6 = 22 字节
2
每个 Page 可存储 = 16KB / 22 ≈ 726 个 Entry
3

4
若树高为 3：
5
- 根节点：726 个子节点
6
- 第二层：726² ≈ 52 万个 Page
7
- 第三层（叶子）：726³ ≈ 3.8 亿个 Page
8

9
每个叶子 Page 存 726 条记录：
10
总计：3.8 亿 × 726 ≈ 2760 亿条记录
11

12
只需 3 次磁盘 I/O！

1
-- 聚簇索引（主键索引）
2
CREATE TABLE t (
3
    id INT PRIMARY KEY,
4
    name VARCHAR(100)
5
);
6

7
-- 数据直接存储在 B+ 树叶子节点
8

9
-- 辅助索引
10
CREATE INDEX idx_name ON t(name);
11

12
-- 叶子节点存储的是主键值，
13
-- 回表查询主键索引获取完整数据

1
# 测试：B 树 vs B+ 树范围查询
2
# 假设 100 万条记录，每页 16KB
3

4
# B 树范围查询
5
$ time ./btree_range_query 1 100000
6
平均磁盘 I/O: 45 次
7
耗时: 2.3ms
8

9
# B+ 树范围查询
10
$ time ./bplustree_range_query 1 100000
11
平均磁盘 I/O: 12 次
12
耗时: 0.6ms

1
-- 查看自适应哈希索引
2
SHOW ENGINE INNODB STATUS;
3

4
-- 自适应哈希索引信息
5
-- --------------------------------------
6
-- Hash table size 3465773, node heap has 1 page(s)
7
-- hash searches: 1234567
8
-- non-hash searches: 234567

1
-- 查询
2
SELECT * FROM orders
3
WHERE customer_id = 100
4
  AND order_date LIKE '2024%';
5

6
-- 无 ICP：先根据 customer_id 找到所有记录，再过滤 order_date
7
-- 有 ICP：在索引树筛选阶段就过滤 order_date