详细讲解MySQL中的默认索引(B+树)

发布于:2024-11-29 ⋅ 阅读:(26) ⋅ 点赞:(0)

好的,我来通俗地解释B+树的原理和代码实现:

  1. 什么是B+树?
    想象一个图书馆的图书分类系统:
  • 一楼大厅有总的分类指示牌(根节点)
  • 各个楼层有具体类别的指示牌(内部节点)
  • 最终的书架上才有实际的书(叶子节点)
  1. B+树的特点:
  • 所有真实数据都存在叶子节点上(就像所有书都在书架上)
  • 非叶子节点只存索引(就像指示牌)
  • 叶子节点通过指针连接(就像书架是连续的)

下面用更简单的代码来实现:

java

public class BPlusTree {
    // 定义节点结构
    class Node {
        boolean isLeaf;         // 是否是叶子节点
        int[] keys;            // 键数组
        Object[] values;       // 值数组(仅叶子节点使用)
        Node[] children;       // 子节点数组
        Node nextLeaf;         // 下一个叶子节点的指针
        int keyCount;          // 当前节点中键的数量

        // 创建新节点
        public Node(boolean leaf, int maxKeys) {
            this.isLeaf = leaf;
            this.keys = new int[maxKeys];
            this.keyCount = 0;
            
            if (leaf) {
                this.values = new Object[maxKeys];
            } else {
                this.children = new Node[maxKeys + 1];
            }
        }
    }

    private Node root;           // 根节点
    private int maxKeys;         // 每个节点最多能存储的键数量
    
    // 初始化B+树
    public BPlusTree(int order) {
        this.maxKeys = order - 1;
        this.root = new Node(true, maxKeys);
    }

    // 插入数据的方法
    public void insert(int key, Object value) {
        Node current = root;
        
        // 1. 如果根节点已满,需要分裂
        if (current.keyCount == maxKeys) {
            Node newRoot = new Node(false, maxKeys);
            newRoot.children[0] = root;
            splitChild(newRoot, 0);
            root = newRoot;
        }
        
        insertNonFull(root, key, value);
    }

    // 在非满节点中插入数据
    private void insertNonFull(Node node, int key, Object value) {
        int i = node.keyCount - 1;

        // 如果是叶子节点,直接插入数据
        if (node.isLeaf) {
            // 找到合适的插入位置
            while (i >= 0 && key < node.keys[i]) {
                node.keys[i + 1] = node.keys[i];
                node.values[i + 1] = node.values[i];
                i--;
            }
            
            // 插入新的键值对
            node.keys[i + 1] = key;
            node.values[i + 1] = value;
            node.keyCount++;
        }
        // 如果不是叶子节点,需要找到合适的子节点继续插入
        else {
            // 找到合适的子节点
            while (i >= 0 && key < node.keys[i]) {
                i--;
            }
            i++;
            
            // 如果子节点已满,需要先分裂
            if (node.children[i].keyCount == maxKeys) {
                splitChild(node, i);
                if (key > node.keys[i]) {
                    i++;
                }
            }
            
            insertNonFull(node.children[i], key, value);
        }
    }

    // 查找数据的方法
    public Object search(int key) {
        return searchInNode(root, key);
    }

    private Object searchInNode(Node node, int key) {
        int i = 0;
        
        // 找到第一个大于等于查找键的位置
        while (i < node.keyCount && key > node.keys[i]) {
            i++;
        }

        // 如果是叶子节点
        if (node.isLeaf) {
            // 找到对应的键,返回值
            if (i < node.keyCount && key == node.keys[i]) {
                return node.values[i];
            }
            return null;
        }
        
        // 如果不是叶子节点,继续在子节点中查找
        return searchInNode(node.children[i], key);
    }
}

让我用实际例子来说明这个B+树是如何工作的:

  1. 插入数据的过程:
    假设我们要插入学生成绩数据,学号作为键,成绩作为值:

java

复制

BPlusTree tree = new BPlusTree(4); // 创建一个4阶B+树
tree.insert(1001, 85);  // 插入学号1001,成绩85
tree.insert(1002, 92);
tree.insert(1003, 78);

插入过程就像在图书馆整理书籍:

  • 先找到合适的位置(书架)
  • 如果书架满了,需要分配新书架(节点分裂)
  • 更新指示牌(索引节点)
  1. 查询数据的过程:

java

Object score = tree.search(1002); // 查找学号1002的成绩
System.out.println("学号1002的成绩是:" + score); // 输出: 92

查询过程就像在图书馆找书:

  • 先看总指示牌(根节点)
  • 按指示牌找到对应区域(内部节点)
  • 最后在书架上找到具体的书(叶子节点)
  1. B+树的优势:
  • 减少磁盘I/O:因为数据是按块存储的,一次可以读取多个数据
  • 范围查询快:叶子节点相连,可以快速遍历
  • 平衡树结构:保证查询效率稳定

比如要查询学号在1001-1003之间的所有成绩,只需要:

  1. 找到1001所在的叶子节点
  2. 通过叶子节点的连接顺序遍历到1003
  3. 一次性获得所有需要的数据

这就是为什么MySQL选择B+树作为索引结构的原因:它既能保证单个查询的效率,又能很好地支持范围查询。