package com.laozhang.btree;

import java.util.*;

/**
 * B+树核心特性演示（非完整实现，重点演示理解关键特性）
 *
 * B+树的四个关键特性（对应MySQL索引的设计决策）：
 * 1. 非叶节点只存key，不存data（一个节点能放更多key，树更矮）
 * 2. 叶节点存key+data，且所有叶节点通过双向链表相连（范围查询高效）
 * 3. 每个节点存储多个key（利用磁盘页大小，减少IO次数）
 * 4. 查询都要走到叶节点（查询时间稳定，所有key查找路径等长）
 *
 * 对应MySQL的实现：
 * - 主键索引（聚簇索引）：叶节点存整行数据
 * - 二级索引（非聚簇索引）：叶节点存主键值，需要回表
 */
public class BPlusTreeConcepts {

    /**
     * 模拟B+树节点（简化版，用于理解概念）
     */
    static class BPlusNode {
        boolean isLeaf;
        List<Integer> keys = new ArrayList<>();  // 节点中的key
        List<Object> values = new ArrayList<>(); // 叶节点：data；内部节点：子节点指针
        BPlusNode next; // 叶节点链表（只有叶节点有）

        BPlusNode(boolean isLeaf) { this.isLeaf = isLeaf; }
    }

    /**
     * 演示1：B+树叶节点链表支持高效范围查询
     * 对应：BETWEEN, >, <, ORDER BY 操作
     *
     * MySQL的EXPLAIN看到"Using index"时，通常是B+树叶节点链表的功劳
     */
    public static void demonstrateRangeQuery() {
        // 模拟叶节点链表（已排序）
        // 在真实MySQL中，每个叶节点是16KB的页，存数百条记录
        BPlusNode leaf1 = new BPlusNode(true);
        leaf1.keys.addAll(Arrays.asList(1, 3, 5));

        BPlusNode leaf2 = new BPlusNode(true);
        leaf2.keys.addAll(Arrays.asList(7, 9, 11));

        BPlusNode leaf3 = new BPlusNode(true);
        leaf3.keys.addAll(Arrays.asList(13, 15, 17));

        leaf1.next = leaf2;
        leaf2.next = leaf3; // 叶节点双向链表

        // 范围查询 [5, 13]：
        // 1. 通过B+树根节点，O(log n)定位到包含5的叶节点
        // 2. 从叶节点开始，沿着next指针顺序遍历，直到超出范围
        System.out.println("范围查询 [5, 13]：");
        BPlusNode curr = leaf1; // 假设已定位到leaf1
        while (curr != null) {
            for (int key : curr.keys) {
                if (key >= 5 && key <= 13) {
                    System.out.print(key + " ");
                }
            }
            if (!curr.keys.isEmpty() && curr.keys.get(curr.keys.size()-1) > 13) break;
            curr = curr.next;
        }
        System.out.println();
        // 输出：5 7 9 11 13
    }

    /**
     * 演示2：聚簇索引 vs 非聚簇索引（回表问题）
     *
     * 聚簇索引（主键索引）：叶节点存整行数据
     * - SELECT * FROM t WHERE id = 1；一次B+树查找，直接得到整行数据
     *
     * 非聚簇索引（二级索引）：叶节点存主键值
     * - SELECT * FROM t WHERE name = 'alice'；
     *   1. 走name的B+树，找到对应的主键值
     *   2. 再走主键B+树找到整行数据（回表！）
     *   两次B+树查找！
     *
     * 覆盖索引：SELECT id, name FROM t WHERE name = 'alice'
     * 只需要name索引叶节点里的数据（已包含id），不需要回表
     * MySQL EXPLAIN里看到"Using index"表示走了覆盖索引
     */
    public static void demonstrateIndexTypes() {
        System.out.println("聚簇索引查询 'SELECT * WHERE id=1':");
        System.out.println("  步骤1: 走主键B+树，找到id=1的叶节点");
        System.out.println("  步骤2: 叶节点直接包含整行数据，返回");
        System.out.println("  总IO: 约3次（树高3层）");

        System.out.println("\n非聚簇索引查询 'SELECT * WHERE name=alice':");
        System.out.println("  步骤1: 走name的B+树，找到叶节点，取出主键id=1");
        System.out.println("  步骤2: 用id=1走主键B+树，找到整行数据（回表）");
        System.out.println("  总IO: 约6次（两次树查找）");

        System.out.println("\n覆盖索引查询 'SELECT id,name WHERE name=alice'（name,id复合索引）:");
        System.out.println("  步骤1: 走(name,id)复合索引B+树，叶节点已包含id和name");
        System.out.println("  步骤2: 无需回表，直接返回");
        System.out.println("  总IO: 约3次（一次树查找）");
        System.out.println("  EXPLAIN显示: Using index（这就是覆盖索引）");
    }
}

2.2 红黑树为什么适合内存，不适合磁盘

package com.laozhang.btree;

import java.util.TreeMap;

/**
 * 红黑树（TreeMap）在内存场景的高效性演示
 * 对比：为什么内存用红黑树，磁盘用B+树
 *
 * 内存场景：每次访问是纳秒级，树高20层也只有20*5ns=100ns（L2 cache）
 * 磁盘场景：每次访问是毫秒级，树高20层=200ms（HDD），不可接受
 */
public class RedBlackTreeVsBPlusTree {

    /**
     * 性能对比的数字化表达
     * 理解这组数字，你就理解了"为什么内存用红黑树，磁盘用B+树"
     */
    public static void compareAccessPatterns() {
        System.out.println("=== 100万数据的查找时间估算 ===");

        // 红黑树（内存）
        double rbTreeHeight = Math.log(1_000_000) / Math.log(2); // ~20
        double memAccessNs = 5; // L2 cache hit ~5ns
        double rbTime = rbTreeHeight * memAccessNs;
        System.out.printf("红黑树（内存）: 树高=%.0f层, 约%.0fns = %.3fms%n",
            rbTreeHeight, rbTime, rbTime / 1_000_000);

        // B+树（SSD）
        int keysPerPage = 1000; // 16KB页，每个key+pointer约16字节，能放约1000个
        double bplusHeight = Math.ceil(Math.log(1_000_000) / Math.log(keysPerPage)); // 2层
        double ssdAccessUs = 100; // SSD ~100μs
        double bplusTime = bplusHeight * ssdAccessUs;
        System.out.printf("B+树（SSD）: 树高=%.0f层, 约%.0fμs = %.1fms%n",
            bplusHeight, bplusTime, bplusTime / 1000);

        // B+树（HDD）
        double hddAccessMs = 10; // HDD ~10ms
        double bplusHddTime = bplusHeight * hddAccessMs;
        System.out.printf("B+树（HDD）: 树高=%.0f层, 约%.0fms%n",
            bplusHeight, bplusHddTime);

        // 如果用红黑树放磁盘
        double rbDiskTimeMs = rbTreeHeight * hddAccessMs;
        System.out.printf("红黑树（HDD，假设）: 树高=%.0f层, 约%.0fms（不可接受！）%n",
            rbTreeHeight, rbDiskTimeMs);
    }

    /**
     * 索引选型的实际决策框架
     *
     * MySQL InnoDB B+树：磁盘存储，减少IO，范围查询
     * Java TreeMap（红黑树）：内存中的有序Map，O(log n)
     * Java HashMap：内存中的无序Map，O(1)
     * Redis ZSet（跳表）：内存中的有序集合，O(log n)，优化范围查询
     */
    public static void indexSelectionGuidance() {
        // 内存场景：不需要持久化，选HashMap（O(1)）或TreeMap（O(log n)，需要有序）
        TreeMap<String, Integer> memoryIndex = new TreeMap<>();
        memoryIndex.put("alice", 1);
        memoryIndex.put("bob", 2);
        System.out.println("内存有序索引（红黑树）: " + memoryIndex.firstKey()); // alice

        // 磁盘场景：用B+树（MySQL InnoDB）
        System.out.println("\nMySQL索引建议：");
        System.out.println("1. 主键：自增整数（B+树最高效，顺序插入不分裂页）");
        System.out.println("2. 范围查询字段：加索引（利用B+树叶节点链表）");
        System.out.println("3. 频繁的SELECT col1,col2 WHERE col3：考虑(col3,col1,col2)复合索引");
        System.out.println("   → 覆盖索引，避免回表");
        System.out.println("4. 低基数字段（如性别）：索引意义不大，全表扫描反而更快");
    }

    public static void main(String[] args) {
        compareAccessPatterns();
        demonstrateRangeQuery();
        demonstrateIndexTypes();
        indexSelectionGuidance();
    }

    static void demonstrateRangeQuery() { BPlusTreeConcepts.demonstrateRangeQuery(); }
    static void demonstrateIndexTypes() { BPlusTreeConcepts.demonstrateIndexTypes(); }
}

四、踩坑实录

坑1：在字符串前缀上建索引，但最左前缀原则没理解透

报错现象：建了复合索引(a, b, c)，查询WHERE b=1 AND c=2却没走索引，全表扫描。

根本原因：B+树的复合索引按照(a, b, c)的顺序排列，不包含a的条件无法利用这个索引（无法定位起始位置）。

具体解法：

-- 建了(a,b,c)复合索引，以下查询能否使用索引：

-- 能用索引
WHERE a=1             -- 只用a，可以
WHERE a=1 AND b=2     -- 用a,b，可以
WHERE a=1 AND b=2 AND c=3  -- 用a,b,c，可以
WHERE a=1 AND c=3     -- 只能用a部分，b跳过了

-- 不能用这个索引（最左前缀不满足）
WHERE b=2             -- 没有a，不能用
WHERE b=2 AND c=3     -- 没有a，不能用
WHERE c=3             -- 没有a，不能用

-- 如果经常查WHERE b=2，需要单独建(b)索引或(b,c)索引

坑2：大量随机主键（UUID）导致B+树页分裂严重

报错现象：使用UUID作为主键，插入性能随数据量增大而急剧下降，磁盘碎片很高。

根本原因：UUID是随机的，插入新记录时，落到哪个叶节点是随机的。如果那个叶节点满了，需要页分裂（把一个页拆成两个），这个操作非常耗时，而且产生大量磁盘碎片（约50%空间浪费）。

自增主键则是顺序插入，总是插到最后一个叶节点，不需要页分裂。

具体解法：

-- 不推荐：UUID主键（随机插入，页分裂严重）
CREATE TABLE t (id VARCHAR(36) PRIMARY KEY, ...); -- UUID

-- 推荐：自增主键（顺序插入，页不分裂）
CREATE TABLE t (id BIGINT AUTO_INCREMENT PRIMARY KEY, ...);

-- 如果业务必须用UUID（分布式ID），可以用有序UUID（如UUID v7）
-- 或者用Snowflake ID（有序的64位整数）
-- 这样既有全局唯一性，又有顺序性，不会触发页分裂

坑3：SELECT * 阻止了覆盖索引优化

报错现象：明明建了合适的索引，EXPLAIN里还是显示"Using index condition"而不是"Using index"，有回表。

根本原因：SELECT *查询所有字段，而二级索引叶节点只存了索引字段+主键，不包含其他字段，所以必须回表。

具体解法：

-- 表结构：user(id, name, age, email, address, ...)
-- 索引：(name) 或 (name, age)

-- 有回表（SELECT * 需要所有字段，二级索引不够，回表取整行）
SELECT * FROM user WHERE name = 'alice';

-- 无回表（SELECT id,name,age，覆盖索引(name,age)已包含这三个字段）
SELECT id, name, age FROM user WHERE name = 'alice';
-- EXPLAIN显示 Using index

-- 优化建议：只查需要的字段，不写SELECT *
-- 对高频查询，考虑建覆盖索引（index covering query）
-- 覆盖索引 = 索引字段 包含 查询字段 + 条件字段

五、总结与延伸

B+树选择磁盘的根本原因是减少IO次数：多叉宽节点充分利用磁盘页，树高从O(log₂ n)降到O(log_m n)，m通常是几百到几千。 理解了这个，MySQL的很多索引设计决策（自增主键、覆盖索引、最左前缀）都有了理论依据。
红黑树在内存里是优秀的有序结构，但放到磁盘上树高太大，IO代价太高。 两者都是O(log n)，但底数不同，磁盘访问延迟数千倍于内存，这个底数的差异就变成了数量级的性能差距。
索引优化的核心思路：减少回表（覆盖索引）+ 减少扫描范围（最左前缀）+ 顺序插入（自增主键/有序分布式ID）。 这三点背后，都是对B+树磁盘特性的深度理解。