理解mysql索引背后的数据结构B~Tree(B-Tree/B+Tree)

B-Tree在不同的文献中的定义略显不同,所以在我初学B-Tree的时候非常困惑,知乎的一篇回答解答了我的困惑为什么 B-tree 在不同著作中度的定义有一定差别? - oldsharp的回答 - 知乎 ,本文将以算法导论中的定义来对B-Tree展开讨论。

正文

在《算法导论》和《计算机程序设计艺术》一书中中对B-Tree的度的定义有略微的不同,在《算法导论》中定义了一个「最小度数t」表示「半满」状态,即最小孩子数,而2t则表示「全满」状态,即最大孩子数。

在《计算机程序设计艺术》一书中定义了一个「度m」表示「全满」状态,即最大孩子节点数,而ceil(m/2)则表示「半满」状态,即最小孩子数(ceil表示向上取整),相比于算法导论中定义的「度t」,《计算机程序设计艺术》一书中定义的「度m」更像是b树的阶,m代表m叉树。从定义可以看出,此种定义的「半满」状态(最小孩子节点数)是不稳定的,这取决于m的奇偶性。

关于这两种不同的定义,实现的最简的b树也是不同的,对于《算法导论》中的定义,一颗最简b树是一颗2-3-4树,而对于《计算机程序设计艺术》一书中的定义,一颗最简的b树是一颗2-3树。

推荐文章

在我学习B~Tree的时候,在网络上看到了一些不错的文章,接下来一一分享之,首先要理解mysql索引的本质是一种数据结构,而mysql的索引包括BTree索引、hash索引、全文索引等,本文主要讨论BTree索引,BTree索引是通过B+树实现的,所以要学习BTree索引第一步首先是要学习B~Tree,B-tree/B+tree/B*tree这篇文章非常简洁、明了、易懂的描述了B~Tree的结构及原理,在学习了B~Tree之后,MySQL索引背后的数据结构及算法原理这篇文章很好的分析了mysql的BTree索引实现以及一些mysql索引优化思路,mysql索引的实现是基于存储引擎的,这就意味着,对于不同的存储引擎,mysql的索引实现方式不同,在《MySQL索引背后的数据结构及算法原理》这篇文章中也分析了MyISAM 存储引擎中索引的实现以及InnoDB 存储引擎中索引实现的不同,有关mysql各类存储引擎的分析与比较,可以参看这篇文章Mysql 存储引擎

使用java实现B-Tree

上面推荐的文章已经很好的解释了mysql索引及b~tree,在下也就不重复造轮子,本文主要分享一下我通过java语言实现的B-Tree,该实现是参照算法导论中的定义,但是在分裂时我选择在「全满」时就开始分裂,而不是等到溢出时再分裂,所以我虽然是参考算法导论中的定义,但是我实现的B-Tree的最简树是一颗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
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
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
/**
* Created by 落叶刻痕 on 2017/11/29.
* 本实现是基于算法导论中的定义:
* d是B-Tree的度,表示半满状态下孩子节点的个数,即非根内节点的最少孩子数量,所以d-1表示最少的key个数
* 2d表示 全满状态下孩子节点的个数,即非根内节点的最多孩子数量,所以2d-1表示最多的key个数
* put操作时,在全满时就开始分裂而不是等到溢出时再分裂
*/
public class BTree<K extends Comparable<K>, V> implements Map<K, V> {


private static final int DEFAULT_D = 2;

//d为大于1的一个正整数,称为B-Tree的度,d表示半满状态,d必须大于等于2
private final int d;

private final int minKeys;

private final int maxKeys;
//h为一个正整数,称为B-Tree的高度。
private int h;
//B-Tree的根节点
private Node<K, V> root;
//B-Tree中元素个数
private int size;

public BTree(int d) {
assert d < 2 : "the d need to greater than 2";
if (d<2) throw new IllegalArgumentException("Illegal Capacity: "+
d);
this.d = d;
this.size = 0;
this.h = 1;
this.minKeys = d - 1;
this.maxKeys = 2 * d - 1;
this.root = new Node<>(maxKeys, null);
}

public BTree() {
this(DEFAULT_D);
}

@Override
public int size() {
return this.size;
}

@Override
public boolean isEmpty() {
return size() == 0;
}

@Override
public boolean containsKey(Object key) {
boolean hasKey = false;
Iterator<Map.Entry<K, V>> iterator = entrySet().iterator();
while (iterator.hasNext()){
Map.Entry<K,V> entry = iterator.next();
if (entry.getKey().equals(key)) {
hasKey = true;
break;
}
}
return hasKey;
}

@Override
public boolean containsValue(Object value) {
boolean hasValue = false;
Iterator<Map.Entry<K, V>> iterator = entrySet().iterator();
while (iterator.hasNext()){
Map.Entry<K,V> entry = iterator.next();
if (entry.getValue().equals(value)) {
hasValue = true;
break;
}
}
return hasValue;
}

@Override
public V get(Object key) {
assert key!=null;
if (!(key instanceof Comparable)){
throw new ClassCastException("key need to implements Comparable");
}
return find(key, root);
}

public V find(Object key, Node<K, V> node) {
Entry<K, V>[] entry = node.data;
for (int i = 0; i < node.getCount(); i++) {
if (((Comparable) key).compareTo(entry[i].getKey()) == 0){
return entry[i].getValue();
} else if (i == 0 && ((Comparable) key).compareTo(entry[0].getKey()) < 0 && node.children[0]!=null) {
return find(key, node.children[0]);
} else if (i < node.getCount() - 1 &&
((Comparable) key).compareTo(entry[i].getKey()) > 0 &&
((Comparable) key).compareTo(entry[i+1].getKey()) < 0) {
if (node.children[0]==null)
return null;
else
return find(key, node.children[i+1]);
} else if (i == node.getCount() - 1 &&
((Comparable) key).compareTo(entry[i].getKey()) > 0 &&
node.children[0]!=null) {
return find(key, node.children[i+1]);
}else {
System.out.println("---");
continue;
}
}
return null;
}

public V put(K key, V value) {
if (key == null) throw new NullPointerException("key can not be null!");

//插入元素
Node<K, V> node = insert(this.root, key, value, 1);
//判断插入的节点是否需要分裂,当插入之后节点达到全满状态,立即分裂节点而不是等到溢出时再分裂
trySplit(node);
return value;
}

@Override
public V remove(Object key) {
//TODO remove(Object key)
return null;
}

@Override
public void putAll(Map<? extends K, ? extends V> m) {
//TODO putAll(Map<? extends K, ? extends V> m)
}

@Override
public void clear() {
//TODO clear()
}

@Override
public Set<K> keySet() {
Set<K> keySet = new TreeSet<>();
entrySet().forEach(entry -> keySet.add(entry.getKey()));
return keySet;
}

@Override
public Collection<V> values() {
//TODO values()
return null;
}

@Override
public Set<Map.Entry<K, V>> entrySet() {
Set<Map.Entry<K, V>> es = new TreeSet<>();
Node<K, V> node = this.root;
addToSet(node, es);
return es;
}

public void addToSet(Node<K, V> node, Set<Map.Entry<K, V>> es){
if (node.isLeaf()){
for (int i = 0; i < node.count; i++) {
es.add(node.data[i]);
}
}else {
//先添加最左边子节点的元素到set
addToSet(node.children[0], es);
for (int i = 0; i < node.count; i++) {
//然后依次交替添加根节点、根节点右边子节点。
es.add(node.data[i]);
addToSet(node.children[i+1], es);
}
}
}


private void trySplit(Node<K, V> node) {
if (node.count < node.data.length) {
return;
}
Node<K, V> root = null;
if (node.parent == null) {
//由于没有父节点,所以重新生成一个父节点
root = new Node<>(maxKeys, null);
root.setLeaf(false);
//根节点变为新增的父节点
this.root = root;
//树的高度加一
this.h++;
} else {
root = node.parent;
}
//将node的parent指向父节点。
node.parent = root;
//取node节点的中间值
int index = (int) Math.ceil(node.count / 2.0) - 1;
//取出要放入父节点的值
Entry<K, V> entry = node.data[index];
//清空node节点中的该值
node.data[index] = null;
node.count--;
//分裂之后的兄弟节点
Node<K, V> brother = new Node<>(maxKeys, root);
//将node节点中index后面的元素放入兄弟节点brother中
for (int i = index + 1; i <= node.data.length; i++) {
if (i < node.data.length) {
brother.data[i - index - 1] = node.data[i];
brother.count++;
node.data[i] = null;
node.count--;
}
//将node节点index后的元素的孩子节点放入兄弟节点中
brother.children[i - index - 1] = node.children[i];
node.children[i] = null;
}
if (brother.children[0] != null) {
brother.setLeaf(false);
}
//将node节点中index位置的元素entry放入父节点root中
int parentIndex = addToParent(root, entry);
root.children[parentIndex] = node;
root.children[parentIndex + 1] = brother;
//如果分分裂后父节点也达到了分裂条件,则让父节点也分裂
trySplit(root);
}

int addToParent(Node<K, V> node, Entry<K, V> entry) {
//当为根节点时
if (node.count == 0) {
node.data[0] = entry;
node.count++;
return 0;
}
int index = -1;
for (int i = 0; i < node.count; i++) {
if (entry.getKey().compareTo(node.data[i].getKey()) <= 0) {
index = i;
break;
}
}
index = index == -1 ? node.count : index;
//将插入点后面的元素都后移一位
for (int i = node.count; i > index; i--) {
node.data[i] = node.data[i - 1];
node.children[i + 1] = node.children[i];
}
node.children[index + 1] = null;
//插入数据
node.data[index] = entry;
node.count++;
return index;
}


public Node<K, V> insert(Node<K, V> node, K key, V value, int ht) {
//当插入第一个值到根节点时
if (node.count == 0) {
Entry<K, V> entry = new Entry<>(key, value);
node.data[0] = entry;
node.count++;
this.size++;
return node;
}
//在节点中寻找key应该放在哪个位置
int index = -1;
for (int i = 0; i < node.count; i++) {
if (key.compareTo(node.data[i].getKey()) <= 0) {
index = i;
break;
}
}
index = index == -1 ? node.count : index;
//找到了应该插入的位置,先判断是否到达最后一层,如果没有到达最后一层,即当前不是叶子节点,则递归到下一层
if (ht < this.h) {
Node<K, V> child = node.children[index];
return insert(child, key, value, ht + 1);
} else if (ht == this.h) { //到达最底层即到达了叶子节点,将数据插入叶子节点
Entry<K, V> entry = new Entry<>(key, value);
//将插入点后面的元素都后移一位
for (int i = node.count; i > index; i--) {
node.data[i] = node.data[i - 1];
// node.children[i+1] = node.children[i];
}
//插入数据
node.data[index] = entry;
node.count++;
this.size++;
return node;
}
return node;
}


static class Node<K extends Comparable<K>, V> {
Entry<K, V>[] data;
Node<K, V>[] children;
Node<K, V> parent;
//该节点key的个数
int count;
//是否为叶子节点,默认为true
boolean leaf = true;

public int getCount() {
return count;
}

public boolean isLeaf() {
return leaf;
}

public void setLeaf(boolean leaf) {
this.leaf = leaf;
}

Node(int maxKeys, Node<K, V> parent) {
this.data = (Entry<K, V>[]) new Entry[maxKeys];
this.children = (Node<K, V>[]) new Node[maxKeys + 1];
this.parent = parent;
count = 0;
}
}

static class Entry<K extends Comparable<K>, V> implements Map.Entry, Comparable<Entry<K, V>> {
K key;
V value;

Entry(K key, V value) {
this.key = key;
this.value = value;
}

public K getKey() {
return key;
}

public void setKey(K key) {
this.key = key;
}

public V getValue() {
return value;
}

@Override
public Object setValue(Object value) {
this.value = (V) value;
return value;
}

/**
* 方便在遍历的时候将元素加入TreeSet集合中,其实根据中序遍历,
* 得到的元素已经根据key按照从小到大的顺序排好序了,所以完全可以用一个list或者数组来装
* @param o
* @return
*/
@Override
public int compareTo(Entry o) {
return o.getKey().compareTo(key)*(-1);
}
}

public int getHeight() {
return h;
}
}