算法详解：B+树 - 数据库索引的基石

B+树是现代数据库系统中最重要的数据结构之一，它是MySQL InnoDB、PostgreSQL、Oracle等主流数据库引擎索引实现的核心。本文将深入解析B+树的原理、实现和应用，带你掌握这个数据库索引的基石。

1. B+树概述

1.1 什么是B+树

B+树（B-Plus Tree）是B树的变种，是一种自平衡的多路搜索树。与B树相比，B+树具有以下特点：

  • 所有数据都存储在叶子节点：内部节点只存储键值，不存储实际数据
  • 叶子节点形成链表：所有叶子节点通过指针连接，支持范围查询
  • 更高的扇出度：由于内部节点不存储数据，可以存储更多键值
  • 更好的缓存局部性：适合磁盘存储和大数据量处理

1.2 B+树的结构特征

一个m阶B+树必须满足以下性质：

  1. 除根节点外，所有内部节点至少有⌈m/2⌉个子节点
  2. 根节点至少有2个子节点（如果不是叶子节点）
  3. 所有叶子节点在同一层
  4. 内部节点的键值数量比子节点数量少1
  5. 叶子节点包含所有键值和数据指针

1.3 B+树可视化结构

1
2
3
4
5
6
7
8
9

                    [20, 40]
                   /    |    \
                  /     |     \
           [10, 15]   [25, 30, 35]   [45, 50]
           /  |  \     /  |  |  \     /  |  \
          /   |   \   /   |  |   \   /   |   \
    [5,8,9] [12,14] [17,18] [22,24] [27,29] [31,33] [37,38] [42,44] [47,49] [52,55]
      ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓
    数据     数据     数据     数据     数据     数据     数据     数据     数据     数据

在上图中：

  • 方括号表示节点中的键值
  • 叶子节点包含实际数据
  • 内部节点只包含用于导航的键值
  • 叶子节点通过链表连接（图中省略了链表指针）

2. 现实世界中的B+树应用

2.1 数据库索引

B+树是关系型数据库中最常用的索引结构：

MySQL InnoDB引擎：

  • 主键索引使用B+树，叶子节点存储完整行数据
  • 辅助索引使用B+树，叶子节点存储主键值
  • 支持范围查询，如 SELECT * FROM table WHERE id BETWEEN 100 AND 200

PostgreSQL：

  • 默认的btree索引基于B+树实现
  • 支持多列索引和部分索引

2.2 文件系统

现代文件系统广泛使用B+树：

NTFS文件系统：

  • 目录结构使用B+树组织
  • 文件名和文件记录通过B+树快速定位

ext4文件系统：

  • 目录索引使用HTree（基于B+树的变种）
  • 提高大目录的访问性能

2.3 内存数据库

Redis Sorted Set： 虽然Redis使用跳表实现有序集合，但B+树在其他内存数据库中广泛使用。

3. B+树的Java实现

3.1 基础数据结构

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233

/**
 * B+树实现
 * @param <K> 键类型
 * @param <V> 值类型
 */
public class BPlusTree<K extends Comparable<K>, V> {

    private static final int DEFAULT_ORDER = 4; // 默认阶数

    private int order; // B+树的阶数
    private Node<K, V> root; // 根节点
    private int size; // 树中键值对的数量

    /**
     * B+树节点抽象类
     */
    abstract static class Node<K extends Comparable<K>, V> {
        protected int keyCount; // 当前节点中键的数量
        protected K[] keys; // 键数组
        protected Node<K, V> parent; // 父节点

        @SuppressWarnings("unchecked")
        public Node(int order) {
            this.keys = (K[]) new Comparable[order - 1];
            this.keyCount = 0;
            this.parent = null;
        }

        /**
         * 判断节点是否已满
         */
        public boolean isFull() {
            return keyCount == keys.length;
        }

        /**
         * 判断节点是否为空
         */
        public boolean isEmpty() {
            return keyCount == 0;
        }

        /**
         * 判断是否为叶子节点
         */
        public abstract boolean isLeaf();

        /**
         * 在节点中查找键的位置
         */
        protected int findKeyIndex(K key) {
            int index = 0;
            while (index < keyCount && keys[index].compareTo(key) < 0) {
                index++;
            }
            return index;
        }
    }

    /**
     * 内部节点类
     */
    static class InternalNode<K extends Comparable<K>, V> extends Node<K, V> {
        private Node<K, V>[] children; // 子节点数组

        @SuppressWarnings("unchecked")
        public InternalNode(int order) {
            super(order);
            this.children = new Node[order];
        }

        @Override
        public boolean isLeaf() {
            return false;
        }

        /**
         * 获取指定索引的子节点
         */
        public Node<K, V> getChild(int index) {
            return children[index];
        }

        /**
         * 设置指定索引的子节点
         */
        public void setChild(int index, Node<K, V> child) {
            children[index] = child;
            if (child != null) {
                child.parent = this;
            }
        }

        /**
         * 在内部节点中插入键和子节点
         */
        public void insertKeyAndChild(K key, Node<K, V> rightChild, int index) {
            // 移动键
            for (int i = keyCount; i > index; i--) {
                keys[i] = keys[i - 1];
            }
            // 移动子节点
            for (int i = keyCount + 1; i > index + 1; i--) {
                children[i] = children[i - 1];
            }

            keys[index] = key;
            children[index + 1] = rightChild;
            rightChild.parent = this;
            keyCount++;
        }

        /**
         * 删除指定索引的键和对应的右子节点
         */
        public void removeKeyAndChild(int index) {
            // 移动键
            for (int i = index; i < keyCount - 1; i++) {
                keys[i] = keys[i + 1];
            }
            // 移动子节点
            for (int i = index + 1; i < keyCount; i++) {
                children[i] = children[i + 1];
            }

            keys[keyCount - 1] = null;
            children[keyCount] = null;
            keyCount--;
        }
    }

    /**
     * 叶子节点类
     */
    static class LeafNode<K extends Comparable<K>, V> extends Node<K, V> {
        private V[] values; // 值数组
        private LeafNode<K, V> next; // 指向下一个叶子节点的指针
        private LeafNode<K, V> prev; // 指向上一个叶子节点的指针

        @SuppressWarnings("unchecked")
        public LeafNode(int order) {
            super(order);
            this.values = (V[]) new Object[order - 1];
            this.next = null;
            this.prev = null;
        }

        @Override
        public boolean isLeaf() {
            return true;
        }

        /**
         * 获取指定索引的值
         */
        public V getValue(int index) {
            return values[index];
        }

        /**
         * 设置指定索引的值
         */
        public void setValue(int index, V value) {
            values[index] = value;
        }

        /**
         * 在叶子节点中插入键值对
         */
        public boolean insertKeyValue(K key, V value) {
            int index = findKeyIndex(key);

            // 如果键已存在，更新值
            if (index < keyCount && keys[index].equals(key)) {
                values[index] = value;
                return false; // 没有增加新的键值对
            }

            // 如果节点已满，无法插入
            if (isFull()) {
                return false;
            }

            // 移动键和值
            for (int i = keyCount; i > index; i--) {
                keys[i] = keys[i - 1];
                values[i] = values[i - 1];
            }

            keys[index] = key;
            values[index] = value;
            keyCount++;
            return true;
        }

        /**
         * 删除指定索引的键值对
         */
        public void removeKeyValue(int index) {
            for (int i = index; i < keyCount - 1; i++) {
                keys[i] = keys[i + 1];
                values[i] = values[i + 1];
            }
            keys[keyCount - 1] = null;
            values[keyCount - 1] = null;
            keyCount--;
        }

        /**
         * 获取下一个叶子节点
         */
        public LeafNode<K, V> getNext() {
            return next;
        }

        /**
         * 设置下一个叶子节点
         */
        public void setNext(LeafNode<K, V> next) {
            this.next = next;
            if (next != null) {
                next.prev = this;
            }
        }

        /**
         * 获取上一个叶子节点
         */
        public LeafNode<K, V> getPrev() {
            return prev;
        }
    }
}

3.2 构造函数和基本方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

/**
 * B+树构造函数
 */
public BPlusTree() {
    this(DEFAULT_ORDER);
}

public BPlusTree(int order) {
    if (order < 3) {
        throw new IllegalArgumentException("B+树的阶数必须大于等于3");
    }
    this.order = order;
    this.root = new LeafNode<>(order);
    this.size = 0;
}

/**
 * 获取树中键值对的数量
 */
public int size() {
    return size;
}

/**
 * 判断树是否为空
 */
public boolean isEmpty() {
    return size == 0;
}

/**
 * 查找最小键对应的叶子节点
 */
private LeafNode<K, V> findFirstLeaf() {
    Node<K, V> current = root;
    while (!current.isLeaf()) {
        InternalNode<K, V> internal = (InternalNode<K, V>) current;
        current = internal.getChild(0);
    }
    return (LeafNode<K, V>) current;
}

/**
 * 根据键查找对应的叶子节点
 */
private LeafNode<K, V> findLeafNode(K key) {
    Node<K, V> current = root;

    while (!current.isLeaf()) {
        InternalNode<K, V> internal = (InternalNode<K, V>) current;
        int index = 0;

        // 找到合适的子节点
        while (index < internal.keyCount &&
               key.compareTo(internal.keys[index]) >= 0) {
            index++;
        }

        current = internal.getChild(index);
    }

    return (LeafNode<K, V>) current;
}

3.3 查找操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

/**
 * 根据键查找值
 */
public V get(K key) {
    if (key == null) {
        throw new IllegalArgumentException("键不能为null");
    }

    LeafNode<K, V> leaf = findLeafNode(key);
    int index = leaf.findKeyIndex(key);

    if (index < leaf.keyCount && leaf.keys[index].equals(key)) {
        return leaf.getValue(index);
    }

    return null; // 未找到
}

/**
 * 判断是否包含指定的键
 */
public boolean containsKey(K key) {
    return get(key) != null;
}

/**
 * 范围查询：查找指定范围内的所有键值对
 */
public List<V> rangeQuery(K startKey, K endKey) {
    if (startKey == null || endKey == null) {
        throw new IllegalArgumentException("范围查询的键不能为null");
    }

    if (startKey.compareTo(endKey) > 0) {
        throw new IllegalArgumentException("起始键必须小于等于结束键");
    }

    List<V> result = new ArrayList<>();
    LeafNode<K, V> current = findLeafNode(startKey);

    while (current != null) {
        for (int i = 0; i < current.keyCount; i++) {
            K key = current.keys[i];

            if (key.compareTo(startKey) >= 0 && key.compareTo(endKey) <= 0) {
                result.add(current.getValue(i));
            } else if (key.compareTo(endKey) > 0) {
                return result; // 超出范围，结束查询
            }
        }
        current = current.getNext();
    }

    return result;
}

3.4 插入操作

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

/**
 * 插入键值对
 */
public V put(K key, V value) {
    if (key == null) {
        throw new IllegalArgumentException("键不能为null");
    }

    LeafNode<K, V> leaf = findLeafNode(key);
    V oldValue = null;

    // 检查键是否已存在
    int index = leaf.findKeyIndex(key);
    if (index < leaf.keyCount && leaf.keys[index].equals(key)) {
        oldValue = leaf.getValue(index);
        leaf.setValue(index, value);
        return oldValue;
    }

    // 尝试在叶子节点中插入
    if (leaf.insertKeyValue(key, value)) {
        size++;
        return null;
    }

    // 叶子节点已满，需要分裂
    splitLeafNode(leaf, key, value);
    size++;
    return null;
}

/**
 * 分裂叶子节点
 */
private void splitLeafNode(LeafNode<K, V> leaf, K key, V value) {
    // 创建新的叶子节点
    LeafNode<K, V> newLeaf = new LeafNode<>(order);

    // 临时数组存储所有键值对
    int totalKeys = leaf.keyCount + 1;
    @SuppressWarnings("unchecked")
    K[] tempKeys = (K[]) new Comparable[totalKeys];
    @SuppressWarnings("unchecked")
    V[] tempValues = (V[]) new Object[totalKeys];

    // 合并原有键值对和新键值对
    int insertIndex = leaf.findKeyIndex(key);
    int tempIndex = 0;

    for (int i = 0; i < leaf.keyCount; i++) {
        if (i == insertIndex) {
            tempKeys[tempIndex] = key;
            tempValues[tempIndex] = value;
            tempIndex++;
        }
        tempKeys[tempIndex] = leaf.keys[i];
        tempValues[tempIndex] = leaf.getValue(i);
        tempIndex++;
    }

    if (insertIndex == leaf.keyCount) {
        tempKeys[tempIndex] = key;
        tempValues[tempIndex] = value;
    }

    // 分割键值对
    int mid = totalKeys / 2;

    // 清空原叶子节点
    leaf.keyCount = 0;
    for (int i = 0; i < mid; i++) {
        leaf.keys[i] = tempKeys[i];
        leaf.setValue(i, tempValues[i]);
        leaf.keyCount++;
    }

    // 填充新叶子节点
    for (int i = mid; i < totalKeys; i++) {
        newLeaf.keys[i - mid] = tempKeys[i];
        newLeaf.setValue(i - mid, tempValues[i]);
        newLeaf.keyCount++;
    }

    // 更新叶子节点链表
    newLeaf.setNext(leaf.getNext());
    leaf.setNext(newLeaf);

    // 获取要上升到父节点的键
    K promotedKey = newLeaf.keys[0];

    // 如果当前叶子节点是根节点，创建新的根节点
    if (leaf.parent == null) {
        InternalNode<K, V> newRoot = new InternalNode<>(order);
        newRoot.keys[0] = promotedKey;
        newRoot.setChild(0, leaf);
        newRoot.setChild(1, newLeaf);
        newRoot.keyCount = 1;

        root = newRoot;
    } else {
        // 在父节点中插入提升的键
        insertIntoParent(leaf.parent, promotedKey, newLeaf);
    }
}

/**
 * 在父节点中插入键和子节点
 */
private void insertIntoParent(InternalNode<K, V> parent, K key, Node<K, V> rightChild) {
    // 如果父节点未满，直接插入
    if (!parent.isFull()) {
        int index = parent.findKeyIndex(key);
        parent.insertKeyAndChild(key, rightChild, index);
        return;
    }

    // 父节点已满，需要分裂
    splitInternalNode(parent, key, rightChild);
}

/**
 * 分裂内部节点
 */
private void splitInternalNode(InternalNode<K, V> internal, K key, Node<K, V> rightChild) {
    // 创建新的内部节点
    InternalNode<K, V> newInternal = new InternalNode<>(order);

    // 临时数组存储所有键和子节点
    int totalKeys = internal.keyCount + 1;
    @SuppressWarnings("unchecked")
    K[] tempKeys = (K[]) new Comparable[totalKeys];
    @SuppressWarnings("unchecked")
    Node<K, V>[] tempChildren = new Node[totalKeys + 1];

    // 找到插入位置
    int insertIndex = internal.findKeyIndex(key);

    // 复制键
    System.arraycopy(internal.keys, 0, tempKeys, 0, insertIndex);
    tempKeys[insertIndex] = key;
    System.arraycopy(internal.keys, insertIndex, tempKeys, insertIndex + 1,
                     internal.keyCount - insertIndex);

    // 复制子节点
    System.arraycopy(internal.children, 0, tempChildren, 0, insertIndex + 1);
    tempChildren[insertIndex + 1] = rightChild;
    System.arraycopy(internal.children, insertIndex + 1, tempChildren, insertIndex + 2,
                     internal.keyCount - insertIndex);

    // 计算分割点
    int mid = totalKeys / 2;
    K promotedKey = tempKeys[mid];

    // 清空原内部节点
    internal.keyCount = 0;

    // 重新分配键和子节点
    for (int i = 0; i < mid; i++) {
        internal.keys[i] = tempKeys[i];
        internal.setChild(i, tempChildren[i]);
        internal.keyCount++;
    }
    internal.setChild(mid, tempChildren[mid]);

    // 填充新内部节点
    for (int i = mid + 1; i < totalKeys; i++) {
        newInternal.keys[i - mid - 1] = tempKeys[i];
        newInternal.setChild(i - mid - 1, tempChildren[i]);
        newInternal.keyCount++;
    }
    newInternal.setChild(newInternal.keyCount, tempChildren[totalKeys]);

    // 如果当前内部节点是根节点，创建新的根节点
    if (internal.parent == null) {
        InternalNode<K, V> newRoot = new InternalNode<>(order);
        newRoot.keys[0] = promotedKey;
        newRoot.setChild(0, internal);
        newRoot.setChild(1, newInternal);
        newRoot.keyCount = 1;

        root = newRoot;
    } else {
        // 在父节点中插入提升的键
        insertIntoParent(internal.parent, promotedKey, newInternal);
    }
}

3.5 删除操作

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

/**
 * 删除指定键的键值对
 */
public V remove(K key) {
    if (key == null) {
        throw new IllegalArgumentException("键不能为null");
    }

    LeafNode<K, V> leaf = findLeafNode(key);
    int index = leaf.findKeyIndex(key);

    // 检查键是否存在
    if (index >= leaf.keyCount || !leaf.keys[index].equals(key)) {
        return null; // 键不存在
    }

    V oldValue = leaf.getValue(index);
    leaf.removeKeyValue(index);
    size--;

    // 检查是否需要重新平衡
    if (leaf.keyCount < (order - 1) / 2 && leaf.parent != null) {
        rebalanceAfterDeletion(leaf);
    }

    return oldValue;
}

/**
 * 删除后重新平衡
 */
private void rebalanceAfterDeletion(Node<K, V> node) {
    if (node.parent == null) {
        // 根节点，无需重新平衡
        return;
    }

    InternalNode<K, V> parent = (InternalNode<K, V>) node.parent;
    int nodeIndex = findChildIndex(parent, node);

    // 尝试从兄弟节点借用
    if (nodeIndex > 0 && canBorrowFromSibling(parent.getChild(nodeIndex - 1))) {
        borrowFromLeftSibling(node, parent, nodeIndex);
    } else if (nodeIndex < parent.keyCount &&
               canBorrowFromSibling(parent.getChild(nodeIndex + 1))) {
        borrowFromRightSibling(node, parent, nodeIndex);
    } else {
        // 无法借用，需要合并
        if (nodeIndex > 0) {
            mergeWithLeftSibling(node, parent, nodeIndex);
        } else {
            mergeWithRightSibling(node, parent, nodeIndex);
        }
    }
}

/**
 * 检查兄弟节点是否可以借用键
 */
private boolean canBorrowFromSibling(Node<K, V> sibling) {
    return sibling.keyCount > (order - 1) / 2;
}

/**
 * 从左兄弟节点借用键
 */
private void borrowFromLeftSibling(Node<K, V> node, InternalNode<K, V> parent, int nodeIndex) {
    Node<K, V> leftSibling = parent.getChild(nodeIndex - 1);

    if (node.isLeaf()) {
        LeafNode<K, V> leaf = (LeafNode<K, V>) node;
        LeafNode<K, V> leftLeaf = (LeafNode<K, V>) leftSibling;

        // 从左兄弟移动最后一个键值对到当前节点的开头
        K borrowedKey = leftLeaf.keys[leftLeaf.keyCount - 1];
        V borrowedValue = leftLeaf.getValue(leftLeaf.keyCount - 1);

        // 在当前节点开头插入
        for (int i = leaf.keyCount; i > 0; i--) {
            leaf.keys[i] = leaf.keys[i - 1];
            leaf.setValue(i, leaf.getValue(i - 1));
        }
        leaf.keys[0] = borrowedKey;
        leaf.setValue(0, borrowedValue);
        leaf.keyCount++;

        // 删除左兄弟的最后一个键值对
        leftLeaf.keys[leftLeaf.keyCount - 1] = null;
        leftLeaf.setValue(leftLeaf.keyCount - 1, null);
        leftLeaf.keyCount--;

        // 更新父节点的键
        parent.keys[nodeIndex - 1] = leaf.keys[0];
    } else {
        InternalNode<K, V> internal = (InternalNode<K, V>) node;
        InternalNode<K, V> leftInternal = (InternalNode<K, V>) leftSibling;

        // 更复杂的内部节点借用逻辑...
        // 这里简化处理，实际实现需要更仔细地处理键和子节点的移动
    }
}

/**
 * 合并节点
 */
private void mergeWithLeftSibling(Node<K, V> node, InternalNode<K, V> parent, int nodeIndex) {
    Node<K, V> leftSibling = parent.getChild(nodeIndex - 1);

    if (node.isLeaf()) {
        LeafNode<K, V> leaf = (LeafNode<K, V>) node;
        LeafNode<K, V> leftLeaf = (LeafNode<K, V>) leftSibling;

        // 将当前节点的所有键值对合并到左兄弟
        for (int i = 0; i < leaf.keyCount; i++) {
            leftLeaf.keys[leftLeaf.keyCount] = leaf.keys[i];
            leftLeaf.setValue(leftLeaf.keyCount, leaf.getValue(i));
            leftLeaf.keyCount++;
        }

        // 更新叶子节点链表
        leftLeaf.setNext(leaf.getNext());

        // 从父节点删除对应的键和子节点引用
        parent.removeKeyAndChild(nodeIndex - 1);

        // 检查父节点是否需要重新平衡
        if (parent.keyCount < (order - 1) / 2 && parent.parent != null) {
            rebalanceAfterDeletion(parent);
        } else if (parent.keyCount == 0 && parent == root) {
            // 根节点为空，更新根节点
            root = leftLeaf;
            leftLeaf.parent = null;
        }
    }
}

/**
 * 找到子节点在父节点中的索引
 */
private int findChildIndex(InternalNode<K, V> parent, Node<K, V> child) {
    for (int i = 0; i <= parent.keyCount; i++) {
        if (parent.getChild(i) == child) {
            return i;
        }
    }
    return -1; // 不应该发生
}

// 其他借用和合并方法的实现...
private void borrowFromRightSibling(Node<K, V> node, InternalNode<K, V> parent, int nodeIndex) {
    // 类似于borrowFromLeftSibling的实现
}

private void mergeWithRightSibling(Node<K, V> node, InternalNode<K, V> parent, int nodeIndex) {
    // 类似于mergeWithLeftSibling的实现
}

4. B+树与其他树结构的比较

4.1 B+树 vs B树

特性B+树B树
数据存储位置仅在叶子节点所有节点
内部节点大小更小，可存储更多键更大，存储键和数据
范围查询优秀（叶子节点链表）需要中序遍历
点查询必须到叶子节点可能在内部节点找到
磁盘I/O更少（更高扇出度）相对较多

4.2 B+树 vs 二叉搜索树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/**
 * 性能对比示例
 */
public class TreePerformanceComparison {

    public static void main(String[] args) {
        // 测试数据量
        int[] dataSizes = {1000, 10000, 100000, 1000000};

        for (int size : dataSizes) {
            System.out.println("数据量: " + size);

            // B+树测试
            BPlusTree<Integer, String> bPlusTree = new BPlusTree<>(100);
            long startTime = System.nanoTime();

            for (int i = 0; i < size; i++) {
                bPlusTree.put(i, "value" + i);
            }

            long bPlusInsertTime = System.nanoTime() - startTime;

            // 查询测试
            startTime = System.nanoTime();
            for (int i = 0; i < 1000; i++) {
                bPlusTree.get(i);
            }
            long bPlusSearchTime = System.nanoTime() - startTime;

            // 范围查询测试
            startTime = System.nanoTime();
            bPlusTree.rangeQuery(100, 199);
            long bPlusRangeTime = System.nanoTime() - startTime;

            System.out.println("B+树插入时间: " + bPlusInsertTime / 1_000_000 + " ms");
            System.out.println("B+树查询时间: " + bPlusSearchTime / 1_000_000 + " ms");
            System.out.println("B+树范围查询时间: " + bPlusRangeTime / 1_000_000 + " ms");
            System.out.println("------------------------");
        }
    }
}

4.3 复杂度分析

操作B+树二叉搜索树(平衡)哈希表
插入O(log_m n)O(log n)O(1)平均
删除O(log_m n)O(log n)O(1)平均
查找O(log_m n)O(log n)O(1)平均
范围查询O(log_m n + k)O(log n + k)O(n)

其中 m 是B+树的阶数，n 是数据总量，k 是范围查询结果数量。

5. 数据库中的B+树优化技术

5.1 批量加载优化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

/**
 * B+树批量加载优化
 */
public class BPlusTreeBulkLoading<K extends Comparable<K>, V> extends BPlusTree<K, V> {

    /**
     * 批量加载有序数据
     */
    public void bulkLoad(List<Map.Entry<K, V>> sortedData) {
        if (sortedData == null || sortedData.isEmpty()) {
            return;
        }

        // 验证数据是否已排序
        for (int i = 1; i < sortedData.size(); i++) {
            if (sortedData.get(i - 1).getKey().compareTo(sortedData.get(i).getKey()) >= 0) {
                throw new IllegalArgumentException("数据必须按键排序");
            }
        }

        // 计算最优的填充因子（通常是70-80%）
        double fillFactor = 0.75;
        int leafCapacity = (int) ((order - 1) * fillFactor);

        List<LeafNode<K, V>> leaves = new ArrayList<>();
        LeafNode<K, V> currentLeaf = new LeafNode<>(order);

        // 构建叶子节点层
        for (Map.Entry<K, V> entry : sortedData) {
            if (currentLeaf.keyCount >= leafCapacity) {
                leaves.add(currentLeaf);

                LeafNode<K, V> newLeaf = new LeafNode<>(order);
                currentLeaf.setNext(newLeaf);
                currentLeaf = newLeaf;
            }

            currentLeaf.keys[currentLeaf.keyCount] = entry.getKey();
            currentLeaf.setValue(currentLeaf.keyCount, entry.getValue());
            currentLeaf.keyCount++;
        }

        if (currentLeaf.keyCount > 0) {
            leaves.add(currentLeaf);
        }

        // 自底向上构建内部节点
        List<Node<K, V>> currentLevel = new ArrayList<>(leaves);

        while (currentLevel.size() > 1) {
            List<Node<K, V>> nextLevel = new ArrayList<>();
            InternalNode<K, V> currentInternal = new InternalNode<>(order);
            int childCount = 0;

            for (int i = 0; i < currentLevel.size(); i++) {
                Node<K, V> child = currentLevel.get(i);

                if (childCount >= order - 1) {
                    nextLevel.add(currentInternal);
                    currentInternal = new InternalNode<>(order);
                    childCount = 0;
                }

                if (childCount > 0) {
                    K separatorKey = getFirstKey(child);
                    currentInternal.keys[currentInternal.keyCount] = separatorKey;
                    currentInternal.keyCount++;
                }

                currentInternal.setChild(childCount, child);
                childCount++;
            }

            if (childCount > 0) {
                nextLevel.add(currentInternal);
            }

            currentLevel = nextLevel;
        }

        root = currentLevel.get(0);
        size = sortedData.size();
    }

    /**
     * 获取节点的第一个键
     */
    private K getFirstKey(Node<K, V> node) {
        if (node.isLeaf()) {
            return node.keys[0];
        } else {
            InternalNode<K, V> internal = (InternalNode<K, V>) node;
            return getFirstKey(internal.getChild(0));
        }
    }
}

5.2 缓存优化策略

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

/**
 * 带缓存的B+树实现
 */
public class CachedBPlusTree<K extends Comparable<K>, V> extends BPlusTree<K, V> {

    private final LRUCache<K, V> cache;
    private final int cacheSize;

    public CachedBPlusTree(int order, int cacheSize) {
        super(order);
        this.cacheSize = cacheSize;
        this.cache = new LRUCache<>(cacheSize);
    }

    @Override
    public V get(K key) {
        // 首先检查缓存
        V cachedValue = cache.get(key);
        if (cachedValue != null) {
            return cachedValue;
        }

        // 缓存未命中，从B+树查找
        V value = super.get(key);
        if (value != null) {
            cache.put(key, value);
        }

        return value;
    }

    @Override
    public V put(K key, V value) {
        // 更新缓存
        cache.put(key, value);

        // 更新B+树
        return super.put(key, value);
    }

    @Override
    public V remove(K key) {
        // 从缓存中移除
        cache.remove(key);

        // 从B+树中移除
        return super.remove(key);
    }

    /**
     * 简单的LRU缓存实现
     */
    private static class LRUCache<K, V> extends LinkedHashMap<K, V> {
        private final int capacity;

        public LRUCache(int capacity) {
            super(capacity + 1, 1.0f, true);
            this.capacity = capacity;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity;
        }
    }

    /**
     * 获取缓存统计信息
     */
    public void printCacheStats() {
        System.out.println("缓存大小: " + cache.size() + "/" + cacheSize);
        System.out.println("缓存使用率: " +
                          String.format("%.2f%%", (double) cache.size() / cacheSize * 100));
    }
}

5.3 并发B+树

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

/**
 * 支持并发的B+树实现
 */
public class ConcurrentBPlusTree<K extends Comparable<K>, V> {

    private volatile Node<K, V> root;
    private final int order;
    private final ReadWriteLock rootLock = new ReentrantReadWriteLock();

    // 节点级别的锁
    private static class LockedNode<K extends Comparable<K>, V> extends Node<K, V> {
        private final ReadWriteLock lock = new ReentrantReadWriteLock();

        public LockedNode(int order) {
            super(order);
        }

        public void readLock() {
            lock.readLock().lock();
        }

        public void readUnlock() {
            lock.readLock().unlock();
        }

        public void writeLock() {
            lock.writeLock().lock();
        }

        public void writeUnlock() {
            lock.writeLock().unlock();
        }

        @Override
        public boolean isLeaf() {
            return false; // 由子类实现
        }
    }

    /**
     * 线程安全的查找操作
     */
    public V get(K key) {
        rootLock.readLock().lock();
        try {
            Node<K, V> current = root;

            while (current != null && !current.isLeaf()) {
                if (current instanceof LockedNode) {
                    ((LockedNode<K, V>) current).readLock();
                }

                try {
                    InternalNode<K, V> internal = (InternalNode<K, V>) current;
                    int index = internal.findKeyIndex(key);
                    current = internal.getChild(index);
                } finally {
                    if (current instanceof LockedNode) {
                        ((LockedNode<K, V>) current).readUnlock();
                    }
                }
            }

            if (current != null && current.isLeaf()) {
                if (current instanceof LockedNode) {
                    ((LockedNode<K, V>) current).readLock();
                }

                try {
                    LeafNode<K, V> leaf = (LeafNode<K, V>) current;
                    int index = leaf.findKeyIndex(key);

                    if (index < leaf.keyCount && leaf.keys[index].equals(key)) {
                        return leaf.getValue(index);
                    }
                } finally {
                    if (current instanceof LockedNode) {
                        ((LockedNode<K, V>) current).readUnlock();
                    }
                }
            }

            return null;
        } finally {
            rootLock.readLock().unlock();
        }
    }

    /**
     * 线程安全的插入操作
     * 使用乐观锁策略：先获取读锁，如果需要修改再升级为写锁
     */
    public V put(K key, V value) {
        // 实现细节较复杂，需要考虑锁的获取顺序、死锁避免等
        // 这里提供基本框架

        rootLock.writeLock().lock();
        try {
            // 执行插入操作
            return putInternal(key, value);
        } finally {
            rootLock.writeLock().unlock();
        }
    }

    private V putInternal(K key, V value) {
        // 实际的插入逻辑
        // 需要仔细处理锁的获取和释放顺序
        return null;
    }
}

6. 磁盘存储优化

6.1 磁盘页面管理

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

/**
 * 磁盘页面管理器
 */
public class DiskPageManager {

    private static final int PAGE_SIZE = 4096; // 4KB页面大小
    private static final int NODE_HEADER_SIZE = 32; // 节点头部大小

    private final RandomAccessFile file;
    private final Map<Long, WeakReference<DiskPage>> pageCache;
    private long nextPageId;

    public DiskPageManager(String filename) throws IOException {
        this.file = new RandomAccessFile(filename, "rw");
        this.pageCache = new ConcurrentHashMap<>();
        this.nextPageId = 0;
    }

    /**
     * 磁盘页面类
     */
    public static class DiskPage {
        private final long pageId;
        private final ByteBuffer buffer;
        private boolean dirty;

        public DiskPage(long pageId) {
            this.pageId = pageId;
            this.buffer = ByteBuffer.allocate(PAGE_SIZE);
            this.dirty = false;
        }

        public void markDirty() {
            this.dirty = true;
        }

        public boolean isDirty() {
            return dirty;
        }

        public ByteBuffer getBuffer() {
            return buffer;
        }

        public long getPageId() {
            return pageId;
        }
    }

    /**
     * 读取页面
     */
    public DiskPage readPage(long pageId) throws IOException {
        // 检查缓存
        WeakReference<DiskPage> pageRef = pageCache.get(pageId);
        if (pageRef != null) {
            DiskPage page = pageRef.get();
            if (page != null) {
                return page;
            }
        }

        // 从磁盘读取
        DiskPage page = new DiskPage(pageId);
        file.seek(pageId * PAGE_SIZE);
        file.read(page.getBuffer().array());

        // 加入缓存
        pageCache.put(pageId, new WeakReference<>(page));

        return page;
    }

    /**
     * 写入页面
     */
    public void writePage(DiskPage page) throws IOException {
        if (!page.isDirty()) {
            return; // 页面未修改，无需写入
        }

        file.seek(page.getPageId() * PAGE_SIZE);
        file.write(page.getBuffer().array());
        page.dirty = false;
    }

    /**
     * 分配新页面
     */
    public DiskPage allocatePage() {
        DiskPage page = new DiskPage(nextPageId++);
        page.markDirty();
        pageCache.put(page.getPageId(), new WeakReference<>(page));
        return page;
    }

    /**
     * 关闭页面管理器
     */
    public void close() throws IOException {
        // 写回所有脏页面
        for (WeakReference<DiskPage> pageRef : pageCache.values()) {
            DiskPage page = pageRef.get();
            if (page != null && page.isDirty()) {
                writePage(page);
            }
        }

        file.close();
    }
}

6.2 持久化B+树

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223

/**
 * 持久化B+树实现
 */
public class PersistentBPlusTree<K extends Comparable<K>, V> {

    private final DiskPageManager pageManager;
    private final Serializer<K> keySerializer;
    private final Serializer<V> valueSerializer;
    private long rootPageId;

    public PersistentBPlusTree(String filename,
                              Serializer<K> keySerializer,
                              Serializer<V> valueSerializer) throws IOException {
        this.pageManager = new DiskPageManager(filename);
        this.keySerializer = keySerializer;
        this.valueSerializer = valueSerializer;
        this.rootPageId = -1;
    }

    /**
     * 序列化接口
     */
    public interface Serializer<T> {
        byte[] serialize(T object);
        T deserialize(byte[] data);
        int getSerializedSize(T object);
    }

    /**
     * 持久化节点接口
     */
    public abstract class PersistentNode {
        protected long pageId;
        protected boolean dirty;

        public PersistentNode(long pageId) {
            this.pageId = pageId;
            this.dirty = false;
        }

        public abstract void serialize(ByteBuffer buffer);
        public abstract void deserialize(ByteBuffer buffer);
        public abstract boolean isLeaf();

        public void markDirty() {
            this.dirty = true;
        }

        public long getPageId() {
            return pageId;
        }
    }

    /**
     * 持久化叶子节点
     */
    public class PersistentLeafNode extends PersistentNode {
        private List<K> keys;
        private List<V> values;
        private long nextLeafPageId;

        public PersistentLeafNode(long pageId) {
            super(pageId);
            this.keys = new ArrayList<>();
            this.values = new ArrayList<>();
            this.nextLeafPageId = -1;
        }

        @Override
        public void serialize(ByteBuffer buffer) {
            buffer.putInt(keys.size()); // 键数量
            buffer.putLong(nextLeafPageId); // 下一个叶子节点页面ID

            // 序列化键
            for (K key : keys) {
                byte[] keyData = keySerializer.serialize(key);
                buffer.putInt(keyData.length);
                buffer.put(keyData);
            }

            // 序列化值
            for (V value : values) {
                byte[] valueData = valueSerializer.serialize(value);
                buffer.putInt(valueData.length);
                buffer.put(valueData);
            }
        }

        @Override
        public void deserialize(ByteBuffer buffer) {
            int keyCount = buffer.getInt();
            nextLeafPageId = buffer.getLong();

            keys.clear();
            values.clear();

            // 反序列化键
            for (int i = 0; i < keyCount; i++) {
                int keyLength = buffer.getInt();
                byte[] keyData = new byte[keyLength];
                buffer.get(keyData);
                keys.add(keySerializer.deserialize(keyData));
            }

            // 反序列化值
            for (int i = 0; i < keyCount; i++) {
                int valueLength = buffer.getInt();
                byte[] valueData = new byte[valueLength];
                buffer.get(valueData);
                values.add(valueSerializer.deserialize(valueData));
            }
        }

        @Override
        public boolean isLeaf() {
            return true;
        }

        /**
         * 查找键值
         */
        public V get(K key) {
            int index = Collections.binarySearch(keys, key);
            if (index >= 0) {
                return values.get(index);
            }
            return null;
        }

        /**
         * 插入键值对
         */
        public boolean put(K key, V value) {
            int index = Collections.binarySearch(keys, key);

            if (index >= 0) {
                // 键已存在，更新值
                values.set(index, value);
                markDirty();
                return false;
            }

            // 插入新键值对
            index = -index - 1;
            keys.add(index, key);
            values.add(index, value);
            markDirty();
            return true;
        }
    }

    /**
     * 从磁盘加载节点
     */
    private PersistentNode loadNode(long pageId) throws IOException {
        DiskPageManager.DiskPage page = pageManager.readPage(pageId);
        ByteBuffer buffer = page.getBuffer();
        buffer.rewind();

        // 读取节点类型
        boolean isLeaf = buffer.get() == 1;

        PersistentNode node;
        if (isLeaf) {
            node = new PersistentLeafNode(pageId);
        } else {
            // 创建内部节点（这里简化处理）
            throw new UnsupportedOperationException("内部节点实现省略");
        }

        node.deserialize(buffer);
        return node;
    }

    /**
     * 保存节点到磁盘
     */
    private void saveNode(PersistentNode node) throws IOException {
        if (!node.dirty) {
            return;
        }

        DiskPageManager.DiskPage page = pageManager.readPage(node.getPageId());
        ByteBuffer buffer = page.getBuffer();
        buffer.clear();

        // 写入节点类型
        buffer.put((byte) (node.isLeaf() ? 1 : 0));

        // 序列化节点数据
        node.serialize(buffer);

        page.markDirty();
        pageManager.writePage(page);
        node.dirty = false;
    }

    /**
     * 查找操作
     */
    public V get(K key) throws IOException {
        if (rootPageId == -1) {
            return null; // 空树
        }

        PersistentNode current = loadNode(rootPageId);

        while (!current.isLeaf()) {
            // 导航到叶子节点（这里需要实现内部节点的导航逻辑）
            // ...
        }

        PersistentLeafNode leaf = (PersistentLeafNode) current;
        return leaf.get(key);
    }

    /**
     * 关闭B+树
     */
    public void close() throws IOException {
        pageManager.close();
    }
}

7. 性能分析与基准测试

7.1 理论性能分析

B+树的性能主要受以下因素影响：

  1. 树的高度：决定了查找操作的I/O次数
  2. 节点大小：影响扇出度和缓存效率
  3. 填充因子：影响空间利用率和分裂频率
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

/**
 * B+树性能分析工具
 */
public class BPlusTreeAnalyzer {

    /**
     * 计算B+树的理论高度
     */
    public static int calculateTreeHeight(long recordCount, int order, double fillFactor) {
        // 叶子节点容量
        int leafCapacity = (int) ((order - 1) * fillFactor);

        // 内部节点容量
        int internalCapacity = (int) (order * fillFactor);

        // 计算叶子节点数量
        long leafNodes = (recordCount + leafCapacity - 1) / leafCapacity;

        // 计算树的高度
        int height = 1; // 叶子节点层
        long currentLevelNodes = leafNodes;

        while (currentLevelNodes > 1) {
            currentLevelNodes = (currentLevelNodes + internalCapacity - 1) / internalCapacity;
            height++;
        }

        return height;
    }

    /**
     * 估算磁盘I/O次数
     */
    public static class IOEstimation {
        public final int searchIOs;
        public final int insertIOs;
        public final int rangeQueryIOs;

        public IOEstimation(int searchIOs, int insertIOs, int rangeQueryIOs) {
            this.searchIOs = searchIOs;
            this.insertIOs = insertIOs;
            this.rangeQueryIOs = rangeQueryIOs;
        }
    }

    public static IOEstimation estimateIOCosts(long recordCount, int order,
                                              double fillFactor, int rangeSize) {
        int height = calculateTreeHeight(recordCount, order, fillFactor);

        // 点查询：从根到叶子
        int searchIOs = height;

        // 插入：查找+可能的分裂
        int insertIOs = height + (int) (height * 0.1); // 假设10%的插入导致分裂

        // 范围查询：定位起始位置+顺序读取叶子节点
        int leafCapacity = (int) ((order - 1) * fillFactor);
        int leafNodesForRange = (rangeSize + leafCapacity - 1) / leafCapacity;
        int rangeQueryIOs = height + leafNodesForRange;

        return new IOEstimation(searchIOs, insertIOs, rangeQueryIOs);
    }

    /**
     * 性能基准测试
     */
    public static void benchmarkBPlusTree() {
        int[] orders = {50, 100, 200, 500};
        int[] dataSizes = {10000, 100000, 1000000};

        System.out.println("B+树性能基准测试");
        System.out.println("================");

        for (int order : orders) {
            System.out.println("\n阶数: " + order);

            for (int dataSize : dataSizes) {
                BPlusTree<Integer, String> tree = new BPlusTree<>(order);

                // 插入测试
                long startTime = System.nanoTime();
                for (int i = 0; i < dataSize; i++) {
                    tree.put(i, "value" + i);
                }
                long insertTime = System.nanoTime() - startTime;

                // 随机查询测试
                Random random = new Random(42);
                startTime = System.nanoTime();
                for (int i = 0; i < 1000; i++) {
                    int key = random.nextInt(dataSize);
                    tree.get(key);
                }
                long searchTime = System.nanoTime() - startTime;

                // 范围查询测试
                startTime = System.nanoTime();
                for (int i = 0; i < 100; i++) {
                    int start = random.nextInt(dataSize - 100);
                    tree.rangeQuery(start, start + 99);
                }
                long rangeTime = System.nanoTime() - startTime;

                System.out.printf("数据量: %7d, 插入: %6.2f ms, 查询: %6.2f ms, 范围查询: %6.2f ms%n",
                                dataSize,
                                insertTime / 1_000_000.0,
                                searchTime / 1_000_000.0,
                                rangeTime / 1_000_000.0);
            }
        }
    }

    public static void main(String[] args) {
        // 理论分析
        System.out.println("B+树理论分析");
        System.out.println("============");

        long[] recordCounts = {1_000_000, 10_000_000, 100_000_000};
        int[] orders = {50, 100, 200};
        double fillFactor = 0.75;

        for (long recordCount : recordCounts) {
            System.out.println("\n记录数量: " + recordCount);

            for (int order : orders) {
                int height = calculateTreeHeight(recordCount, order, fillFactor);
                IOEstimation io = estimateIOCosts(recordCount, order, fillFactor, 100);

                System.out.printf("阶数: %3d, 高度: %2d, 查询I/O: %2d, 插入I/O: %2d, 范围查询I/O: %2d%n",
                                order, height, io.searchIOs, io.insertIOs, io.rangeQueryIOs);
            }
        }

        // 实际基准测试
        System.out.println("\n\n");
        benchmarkBPlusTree();
    }
}

7.2 内存使用分析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
 * B+树内存使用分析
 */
public class MemoryAnalyzer {

    /**
     * 分析B+树的内存使用情况
     */
    public static void analyzeMemoryUsage(BPlusTree<Integer, String> tree, int dataSize) {
        Runtime runtime = Runtime.getRuntime();

        // 强制垃圾回收
        System.gc();
        long memoryBefore = runtime.totalMemory() - runtime.freeMemory();

        // 插入数据
        for (int i = 0; i < dataSize; i++) {
            tree.put(i, "value_" + i);
        }

        // 再次垃圾回收
        System.gc();
        long memoryAfter = runtime.totalMemory() - runtime.freeMemory();

        long memoryUsed = memoryAfter - memoryBefore;
        double memoryPerRecord = (double) memoryUsed / dataSize;

        System.out.println("内存使用分析:");
        System.out.println("数据量: " + dataSize);
        System.out.println("总内存使用: " + formatBytes(memoryUsed));
        System.out.println("每条记录内存: " + String.format("%.2f bytes", memoryPerRecord));

        // 分析内存效率
        int theoreticalSize = dataSize * (4 + 20); // 假设每条记录24字节
        double efficiency = (double) theoreticalSize / memoryUsed * 100;
        System.out.println("内存效率: " + String.format("%.2f%%", efficiency));
    }

    private static String formatBytes(long bytes) {
        if (bytes < 1024) return bytes + " B";
        if (bytes < 1024 * 1024) return String.format("%.2f KB", bytes / 1024.0);
        if (bytes < 1024 * 1024 * 1024) return String.format("%.2f MB", bytes / (1024.0 * 1024));
        return String.format("%.2f GB", bytes / (1024.0 * 1024 * 1024));
    }
}

8. 高级主题

8.1 并发控制策略

B+树的并发控制有多种策略：

  1. 锁耦合（Lock Coupling）：从根节点开始，获取子节点锁后再释放父节点锁
  2. 乐观并发控制：使用版本号检测冲突
  3. 无锁算法：使用CAS操作实现无锁并发
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

/**
 * 基于乐观锁的并发B+树节点
 */
public class OptimisticNode<K extends Comparable<K>, V> {
    private volatile long version;
    private volatile K[] keys;
    private volatile V[] values;
    private volatile int keyCount;

    /**
     * 乐观读操作
     */
    public V optimisticGet(K key) {
        long initialVersion;
        K[] localKeys;
        V[] localValues;
        int localKeyCount;

        do {
            initialVersion = version;
            if ((initialVersion & 1) != 0) {
                // 版本号为奇数，表示正在写入
                Thread.yield();
                continue;
            }

            // 读取数据
            localKeys = keys;
            localValues = values;
            localKeyCount = keyCount;

            // 检查版本号是否变化
        } while (version != initialVersion);

        // 在本地副本中查找
        for (int i = 0; i < localKeyCount; i++) {
            if (localKeys[i].equals(key)) {
                return localValues[i];
            }
        }

        return null;
    }

    /**
     * 写操作需要获取写锁
     */
    public synchronized boolean optimisticPut(K key, V value) {
        // 增加版本号（设为奇数，表示正在写入）
        version++;

        try {
            // 执行写操作
            return putInternal(key, value);
        } finally {
            // 完成写入，版本号设为偶数
            version++;
        }
    }

    private boolean putInternal(K key, V value) {
        // 实际的插入逻辑
        return true;
    }
}

8.2 压缩技术

为了提高空间效率，B+树可以使用多种压缩技术：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

/**
 * 压缩B+树节点
 */
public class CompressedLeafNode<K extends Comparable<K>, V> {

    private byte[] compressedData;
    private int keyCount;
    private CompressionCodec codec;

    public interface CompressionCodec {
        byte[] compress(byte[] data);
        byte[] decompress(byte[] compressedData);
    }

    /**
     * 前缀压缩实现
     */
    public static class PrefixCompressionCodec implements CompressionCodec {

        @Override
        public byte[] compress(byte[] data) {
            // 实现前缀压缩
            // 1. 找到公共前缀
            // 2. 存储前缀长度和唯一后缀
            return compressWithPrefix(data);
        }

        @Override
        public byte[] decompress(byte[] compressedData) {
            // 还原前缀压缩的数据
            return decompressPrefix(compressedData);
        }

        private byte[] compressWithPrefix(byte[] data) {
            // 前缀压缩算法实现
            ByteArrayOutputStream baos = new ByteArrayOutputStream();

            // 这里实现具体的前缀压缩逻辑
            // 1. 分析字符串的公共前缀
            // 2. 将前缀和差异部分分别存储

            return baos.toByteArray();
        }

        private byte[] decompressPrefix(byte[] compressedData) {
            // 前缀解压缩算法实现
            return new byte[0]; // 简化实现
        }
    }

    /**
     * 增量编码压缩
     */
    public static class DeltaCompressionCodec implements CompressionCodec {

        @Override
        public byte[] compress(byte[] data) {
            // 对于整数键，使用增量编码
            return compressWithDelta(data);
        }

        @Override
        public byte[] decompress(byte[] compressedData) {
            return decompressDelta(compressedData);
        }

        private byte[] compressWithDelta(byte[] data) {
            // 增量编码实现
            ByteArrayOutputStream baos = new ByteArrayOutputStream();

            // 假设数据是有序的整数
            // 存储第一个值，然后存储后续值与前一个值的差

            return baos.toByteArray();
        }

        private byte[] decompressDelta(byte[] compressedData) {
            // 增量解码实现
            return new byte[0]; // 简化实现
        }
    }
}

8.3 自适应B+树

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

/**
 * 自适应B+树：根据访问模式动态调整结构
 */
public class AdaptiveBPlusTree<K extends Comparable<K>, V> extends BPlusTree<K, V> {

    private final Map<K, AccessPattern> accessPatterns;
    private final int adaptationThreshold;

    public AdaptiveBPlusTree(int order) {
        super(order);
        this.accessPatterns = new ConcurrentHashMap<>();
        this.adaptationThreshold = 1000;
    }

    /**
     * 访问模式统计
     */
    private static class AccessPattern {
        private int readCount;
        private int writeCount;
        private long lastAccessTime;
        private boolean hotData;

        public void recordRead() {
            readCount++;
            lastAccessTime = System.currentTimeMillis();
            updateHotStatus();
        }

        public void recordWrite() {
            writeCount++;
            lastAccessTime = System.currentTimeMillis();
            updateHotStatus();
        }

        private void updateHotStatus() {
            // 根据访问频率和时间确定是否为热数据
            long timeSinceLastAccess = System.currentTimeMillis() - lastAccessTime;
            int totalAccess = readCount + writeCount;

            hotData = totalAccess > 10 && timeSinceLastAccess < 60000; // 1分钟内
        }

        public boolean isHotData() {
            return hotData;
        }
    }

    @Override
    public V get(K key) {
        // 记录访问模式
        AccessPattern pattern = accessPatterns.computeIfAbsent(key,
            k -> new AccessPattern());
        pattern.recordRead();

        V result = super.get(key);

        // 定期检查是否需要自适应调整
        if (accessPatterns.size() % adaptationThreshold == 0) {
            adaptStructure();
        }

        return result;
    }

    @Override
    public V put(K key, V value) {
        // 记录访问模式
        AccessPattern pattern = accessPatterns.computeIfAbsent(key,
            k -> new AccessPattern());
        pattern.recordWrite();

        return super.put(key, value);
    }

    /**
     * 根据访问模式自适应调整树结构
     */
    private void adaptStructure() {
        // 识别热数据
        Set<K> hotKeys = accessPatterns.entrySet().stream()
            .filter(entry -> entry.getValue().isHotData())
            .map(Map.Entry::getKey)
            .collect(Collectors.toSet());

        if (!hotKeys.isEmpty()) {
            // 对热数据进行特殊处理
            optimizeForHotData(hotKeys);
        }

        // 清理过期的访问模式
        cleanupOldPatterns();
    }

    /**
     * 为热数据优化存储结构
     */
    private void optimizeForHotData(Set<K> hotKeys) {
        // 可能的优化策略：
        // 1. 将热数据移动到更高的缓存层
        // 2. 调整节点分裂策略
        // 3. 预取相关数据

        System.out.println("优化热数据: " + hotKeys.size() + " 个键");
    }

    /**
     * 清理过期的访问模式统计
     */
    private void cleanupOldPatterns() {
        long currentTime = System.currentTimeMillis();
        long expirationTime = 5 * 60 * 1000; // 5分钟

        accessPatterns.entrySet().removeIf(entry ->
            currentTime - entry.getValue().lastAccessTime > expirationTime);
    }
}

9. 实际应用案例

9.1 简化的数据库索引实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

/**
 * 简化的数据库索引实现
 */
public class DatabaseIndex<K extends Comparable<K>> {

    private final BPlusTree<K, RowPointer> index;
    private final String indexName;
    private final String tableName;
    private final String columnName;

    public DatabaseIndex(String indexName, String tableName, String columnName) {
        this.index = new BPlusTree<>(100); // 使用较大的阶数
        this.indexName = indexName;
        this.tableName = tableName;
        this.columnName = columnName;
    }

    /**
     * 行指针：指向实际数据的位置
     */
    public static class RowPointer {
        private final long pageId;
        private final int slotId;

        public RowPointer(long pageId, int slotId) {
            this.pageId = pageId;
            this.slotId = slotId;
        }

        public long getPageId() { return pageId; }
        public int getSlotId() { return slotId; }

        @Override
        public String toString() {
            return String.format("RowPointer(page=%d, slot=%d)", pageId, slotId);
        }
    }

    /**
     * 插入索引项
     */
    public void insert(K key, RowPointer pointer) {
        index.put(key, pointer);
    }

    /**
     * 删除索引项
     */
    public boolean delete(K key) {
        return index.remove(key) != null;
    }

    /**
     * 点查询
     */
    public RowPointer lookup(K key) {
        return index.get(key);
    }

    /**
     * 范围查询
     */
    public List<RowPointer> rangeQuery(K startKey, K endKey) {
        return index.rangeQuery(startKey, endKey);
    }

    /**
     * 获取索引统计信息
     */
    public IndexStats getStats() {
        return new IndexStats(index.size(), calculateHeight(), calculateSpaceUsage());
    }

    private int calculateHeight() {
        // 计算树的高度
        return BPlusTreeAnalyzer.calculateTreeHeight(index.size(), 100, 0.75);
    }

    private long calculateSpaceUsage() {
        // 估算空间使用
        return index.size() * 32; // 假设每个索引项32字节
    }

    public static class IndexStats {
        public final int entryCount;
        public final int height;
        public final long spaceUsage;

        public IndexStats(int entryCount, int height, long spaceUsage) {
            this.entryCount = entryCount;
            this.height = height;
            this.spaceUsage = spaceUsage;
        }

        @Override
        public String toString() {
            return String.format("IndexStats(entries=%d, height=%d, space=%d bytes)",
                               entryCount, height, spaceUsage);
        }
    }
}

/**
 * 数据库索引使用示例
 */
public class DatabaseIndexExample {

    public static void main(String[] args) {
        // 创建索引
        DatabaseIndex<Integer> userIdIndex = new DatabaseIndex<>(
            "idx_user_id", "users", "user_id");

        DatabaseIndex<String> emailIndex = new DatabaseIndex<>(
            "idx_email", "users", "email");

        // 插入索引数据
        System.out.println("插入索引数据...");
        for (int i = 1; i <= 10000; i++) {
            DatabaseIndex.RowPointer pointer =
                new DatabaseIndex.RowPointer(i / 100, i % 100);

            userIdIndex.insert(i, pointer);
            emailIndex.insert("user" + i + "@example.com", pointer);
        }

        // 点查询测试
        System.out.println("\n点查询测试:");
        DatabaseIndex.RowPointer pointer = userIdIndex.lookup(5000);
        System.out.println("用户ID 5000 的行指针: " + pointer);

        // 范围查询测试
        System.out.println("\n范围查询测试:");
        List<DatabaseIndex.RowPointer> rangeResult =
            userIdIndex.rangeQuery(1000, 1010);
        System.out.println("ID 1000-1010 的行指针数量: " + rangeResult.size());

        // 索引统计
        System.out.println("\n索引统计信息:");
        System.out.println("用户ID索引: " + userIdIndex.getStats());
        System.out.println("邮箱索引: " + emailIndex.getStats());

        // 模拟SQL查询
        simulateSQL(userIdIndex, emailIndex);
    }

    private static void simulateSQL(DatabaseIndex<Integer> userIdIndex,
                                   DatabaseIndex<String> emailIndex) {
        System.out.println("\n模拟SQL查询:");

        // SELECT * FROM users WHERE user_id = 1234
        System.out.println("查询: SELECT * FROM users WHERE user_id = 1234");
        DatabaseIndex.RowPointer result1 = userIdIndex.lookup(1234);
        System.out.println("索引查找结果: " + result1);

        // SELECT * FROM users WHERE user_id BETWEEN 1000 AND 2000
        System.out.println("\n查询: SELECT * FROM users WHERE user_id BETWEEN 1000 AND 2000");
        List<DatabaseIndex.RowPointer> result2 = userIdIndex.rangeQuery(1000, 2000);
        System.out.println("范围查询结果数量: " + result2.size());

        // SELECT * FROM users WHERE email = 'user5678@example.com'
        System.out.println("\n查询: SELECT * FROM users WHERE email = 'user5678@example.com'");
        DatabaseIndex.RowPointer result3 = emailIndex.lookup("user5678@example.com");
        System.out.println("邮箱索引查找结果: " + result3);
    }
}

9.2 文件系统目录索引

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226

/**
 * 文件系统目录索引实现
 */
public class FileSystemIndex {

    private final BPlusTree<String, FileEntry> directoryIndex;

    public FileSystemIndex() {
        this.directoryIndex = new BPlusTree<>(64); // 适合文件名的阶数
    }

    /**
     * 文件条目
     */
    public static class FileEntry {
        private final String fileName;
        private final long fileSize;
        private final long createTime;
        private final long modifyTime;
        private final boolean isDirectory;
        private final long inodeNumber;

        public FileEntry(String fileName, long fileSize, boolean isDirectory, long inodeNumber) {
            this.fileName = fileName;
            this.fileSize = fileSize;
            this.isDirectory = isDirectory;
            this.inodeNumber = inodeNumber;
            this.createTime = System.currentTimeMillis();
            this.modifyTime = createTime;
        }

        // Getters
        public String getFileName() { return fileName; }
        public long getFileSize() { return fileSize; }
        public long getCreateTime() { return createTime; }
        public long getModifyTime() { return modifyTime; }
        public boolean isDirectory() { return isDirectory; }
        public long getInodeNumber() { return inodeNumber; }

        @Override
        public String toString() {
            return String.format("FileEntry(name=%s, size=%d, isDir=%s, inode=%d)",
                               fileName, fileSize, isDirectory, inodeNumber);
        }
    }

    /**
     * 添加文件或目录
     */
    public void addFile(String fileName, long fileSize, boolean isDirectory) {
        long inodeNumber = generateInodeNumber();
        FileEntry entry = new FileEntry(fileName, fileSize, isDirectory, inodeNumber);
        directoryIndex.put(fileName, entry);
    }

    /**
     * 查找文件
     */
    public FileEntry findFile(String fileName) {
        return directoryIndex.get(fileName);
    }

    /**
     * 删除文件
     */
    public boolean removeFile(String fileName) {
        return directoryIndex.remove(fileName) != null;
    }

    /**
     * 列出目录内容（按文件名排序）
     */
    public List<FileEntry> listFiles() {
        return listFiles("", "\uFFFF"); // 所有文件
    }

    /**
     * 列出指定前缀的文件
     */
    public List<FileEntry> listFiles(String prefix) {
        String endPrefix = prefix + "\uFFFF";
        return directoryIndex.rangeQuery(prefix, endPrefix);
    }

    /**
     * 列出指定范围的文件
     */
    public List<FileEntry> listFiles(String startName, String endName) {
        return directoryIndex.rangeQuery(startName, endName);
    }

    /**
     * 获取目录统计信息
     */
    public DirectoryStats getStats() {
        List<FileEntry> allFiles = listFiles();

        int fileCount = 0;
        int dirCount = 0;
        long totalSize = 0;

        for (FileEntry entry : allFiles) {
            if (entry.isDirectory()) {
                dirCount++;
            } else {
                fileCount++;
                totalSize += entry.getFileSize();
            }
        }

        return new DirectoryStats(fileCount, dirCount, totalSize);
    }

    private long generateInodeNumber() {
        return System.currentTimeMillis() + (long) (Math.random() * 1000);
    }

    public static class DirectoryStats {
        public final int fileCount;
        public final int directoryCount;
        public final long totalSize;

        public DirectoryStats(int fileCount, int directoryCount, long totalSize) {
            this.fileCount = fileCount;
            this.directoryCount = directoryCount;
            this.totalSize = totalSize;
        }

        @Override
        public String toString() {
            return String.format("DirectoryStats(files=%d, dirs=%d, totalSize=%d bytes)",
                               fileCount, directoryCount, totalSize);
        }
    }
}

/**
 * 文件系统索引使用示例
 */
public class FileSystemExample {

    public static void main(String[] args) {
        FileSystemIndex fsIndex = new FileSystemIndex();

        // 添加文件和目录
        System.out.println("创建文件系统结构...");

        // 添加目录
        fsIndex.addFile("Documents", 0, true);
        fsIndex.addFile("Pictures", 0, true);
        fsIndex.addFile("Music", 0, true);

        // 添加文件
        fsIndex.addFile("readme.txt", 1024, false);
        fsIndex.addFile("config.json", 2048, false);
        fsIndex.addFile("data.csv", 5120, false);
        fsIndex.addFile("photo1.jpg", 1048576, false);
        fsIndex.addFile("photo2.png", 2097152, false);
        fsIndex.addFile("song1.mp3", 4194304, false);
        fsIndex.addFile("song2.mp3", 3145728, false);

        // 查找特定文件
        System.out.println("\n文件查找测试:");
        FileSystemIndex.FileEntry file = fsIndex.findFile("readme.txt");
        System.out.println("找到文件: " + file);

        // 列出所有文件
        System.out.println("\n所有文件列表:");
        List<FileSystemIndex.FileEntry> allFiles = fsIndex.listFiles();
        for (FileSystemIndex.FileEntry entry : allFiles) {
            System.out.println("  " + entry);
        }

        // 按前缀查找
        System.out.println("\n查找以'photo'开头的文件:");
        List<FileSystemIndex.FileEntry> photoFiles = fsIndex.listFiles("photo");
        for (FileSystemIndex.FileEntry entry : photoFiles) {
            System.out.println("  " + entry);
        }

        // 范围查找
        System.out.println("\n查找文件名在'a'到'p'之间的文件:");
        List<FileSystemIndex.FileEntry> rangeFiles = fsIndex.listFiles("a", "p");
        for (FileSystemIndex.FileEntry entry : rangeFiles) {
            System.out.println("  " + entry);
        }

        // 目录统计
        System.out.println("\n目录统计信息:");
        FileSystemIndex.DirectoryStats stats = fsIndex.getStats();
        System.out.println(stats);

        // 模拟ls命令
        simulateLsCommand(fsIndex);
    }

    private static void simulateLsCommand(FileSystemIndex fsIndex) {
        System.out.println("\n模拟ls命令:");

        // ls -la (列出所有文件详细信息)
        System.out.println("$ ls -la");
        List<FileSystemIndex.FileEntry> files = fsIndex.listFiles();
        for (FileSystemIndex.FileEntry entry : files) {
            String type = entry.isDirectory() ? "d" : "-";
            String permissions = "rwxr-xr-x"; // 简化的权限显示

            System.out.printf("%s%s %8d %s %s%n",
                            type, permissions, entry.getFileSize(),
                            formatDate(entry.getCreateTime()), entry.getFileName());
        }

        // ls *.mp3 (查找mp3文件)
        System.out.println("\n$ ls *.mp3");
        List<FileSystemIndex.FileEntry> mp3Files = fsIndex.listFiles("song");
        for (FileSystemIndex.FileEntry entry : mp3Files) {
            if (entry.getFileName().endsWith(".mp3")) {
                System.out.println(entry.getFileName());
            }
        }
    }

    private static String formatDate(long timestamp) {
        return new java.text.SimpleDateFormat("MMM dd HH:mm")
                   .format(new java.util.Date(timestamp));
    }
}

总结

B+树作为现代数据库系统的核心数据结构，其重要性不言而喻。通过本文的深入分析，我们了解了：

核心特性

  • 所有数据存储在叶子节点：保证了一致的查询性能
  • 叶子节点形成链表：支持高效的范围查询
  • 高扇出度：减少了树的高度，降低磁盘I/O次数
  • 自平衡特性：保证了操作的时间复杂度

性能优势

  • 查询性能：O(log_m n)的时间复杂度，其中m是阶数
  • 范围查询：通过叶子节点链表实现O(log_m n + k)的复杂度
  • 磁盘友好：大节点设计减少磁盘I/O次数
  • 缓存效率：良好的局部性原理

实际应用

  • 数据库索引：MySQL InnoDB、PostgreSQL等主流数据库
  • 文件系统：NTFS、ext4等现代文件系统
  • 内存数据库：各种内存数据库和缓存系统

优化技术

  • 批量加载：提高大量数据的加载效率
  • 压缩技术：减少存储空间和I/O开销
  • 并发控制：支持多线程并发访问
  • 自适应调整：根据访问模式动态优化

B+树的设计充分体现了计算机科学中时间和空间权衡的智慧，它不仅在理论上优雅，在实践中也经受了时间的考验。掌握B+树的原理和实现，对于理解现代数据库系统和开发高性能应用具有重要意义。

随着数据量的不断增长和存储技术的发展，B+树也在不断演进，如支持SSD优化的B+树变种、分布式B+树等。但其核心思想和基本原理将继续指导我们设计更好的数据结构和算法。

进一步学习建议

  1. 深入研究数据库内核：了解MySQL InnoDB、PostgreSQL等数据库的B+树实现细节
  2. 性能调优实践：在实际项目中应用B+树优化数据访问性能
  3. 并发编程：学习更复杂的并发控制技术和无锁数据结构
  4. 分布式系统：研究分布式B+树和分布式索引技术

B+树不仅仅是一个数据结构，更是连接理论与实践的桥梁。通过深入理解和实践，我们能够更好地设计和优化现代软件系统。