定義
在計(jì)算機(jī)科學(xué)中，B樹（英語(yǔ)：B-tree）是一種自平衡的樹，能夠保持?jǐn)?shù)據(jù)有序。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)、順序訪問、插入數(shù)據(jù)及刪除的動(dòng)作，都在對(duì)數(shù)時(shí)間內(nèi)完成。
為什么要引入B樹?
首先，包括前面我們介紹的紅黑樹是將輸入存入內(nèi)存的一種內(nèi)部查找樹。
而B樹是前面平衡樹算法的擴(kuò)展，它支持保存在磁盤或者網(wǎng)絡(luò)上的符號(hào)表進(jìn)行外部查找，這些文件可能比我們以前考慮的輸入要大的多（難以存入內(nèi)存）。
既然內(nèi)容保存在磁盤中，那么自然會(huì)因?yàn)闃涞纳疃冗^大而造成磁盤I/O讀寫過于頻繁（磁盤讀寫速率是有限制的），進(jìn)而導(dǎo)致查詢效率低下。
那么降低樹的深度自然很重要了。因此，我們引入了B樹，多路查找樹。
特點(diǎn)
樹中每個(gè)結(jié)點(diǎn)最多含有m個(gè)孩子（m>=2）；
除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有[ceil(m / 2)]個(gè)孩子（其中ceil(x)是一個(gè)取上限的函數(shù)）；
若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有2個(gè)孩子（特殊情況：沒有孩子的根結(jié)點(diǎn)，即根結(jié)點(diǎn)為葉子結(jié)點(diǎn)，整棵樹只有一個(gè)根節(jié)點(diǎn)）；
所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層(最底層)，葉子結(jié)點(diǎn)為外部結(jié)點(diǎn)，保存內(nèi)容，即key和value。
其他結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)，保存索引，即key和next。
內(nèi)部結(jié)點(diǎn)的關(guān)鍵字key：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
內(nèi)容結(jié)點(diǎn)的指針next：P[1], P[2], …, P[M]；其中P[1]指向關(guān)鍵字小于K[1]的子樹，P[M]指向關(guān)鍵字大于K[M-1]的子樹，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹；
例如：（M=3）
查找和插入
為了方便這里用了一個(gè)特殊的哨兵鍵，它小于其他所有鍵，用*表示。
一開始B樹只含有一個(gè)根結(jié)點(diǎn)，而根結(jié)點(diǎn)在初始化時(shí)僅含有該哨兵鍵。
內(nèi)部結(jié)點(diǎn)中的每個(gè)鍵都與一個(gè)結(jié)點(diǎn)相關(guān)聯(lián)，以此結(jié)點(diǎn)為根的子樹種，所有的鍵都大于等于與此結(jié)點(diǎn)關(guān)聯(lián)的鍵，但小于其他所有鍵。
這些約定在很大程度上能夠簡(jiǎn)化代碼。
代碼
點(diǎn)擊下載。
該代碼實(shí)現(xiàn)引入了哨兵鍵，代碼輸出則剔除了它。
代碼里含有哨兵鍵的B樹（將圖片保存到本地查看，字會(huì)清晰些）：
代碼輸出的B樹（將圖片保存到本地查看，字會(huì)清晰些）：
|
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
|
public class BTree<Key extends Comparable<Key>, Value> { // max children per B-tree node = M-1 // (must be even and greater than 2) private static final int M = 4; private Node root; // root of the B-tree private int height; // height of the B-tree private int n; // number of key-value pairs in the B-tree // helper B-tree node data type private static final class Node { private int m; // number of children private Entry[] children = new Entry[M]; // the array of children // create a node with k children private Node(int k) { m = k; } } // internal nodes: only use key and next // external nodes: only use key and value private static class Entry { private Comparable key; private Object val; private Node next; // helper field to iterate over array entries public Entry(Comparable key, Object val, Node next) { this.key = key; this.val = val; this.next = next; } } /** * Initializes an empty B-tree. */ public BTree() { root = new Node(0); } /** * Returns true if this symbol table is empty. * @return {@code true} if this symbol table is empty; {@code false} otherwise */ public boolean isEmpty() { return size() == 0; } /** * Returns the number of key-value pairs in this symbol table. * @return the number of key-value pairs in this symbol table */ public int size() { return n; } /** * Returns the height of this B-tree (for debugging). * * @return the height of this B-tree */ public int height() { return height; } /** * Returns the value associated with the given key. * * @param key the key * @return the value associated with the given key if the key is in the symbol table * and {@code null} if the key is not in the symbol table * @throws NullPointerException if {@code key} is {@code null} */ public Value get(Key key) { if (key == null) { throw new NullPointerException("key must not be null"); } return search(root, key, height); } @SuppressWarnings("unchecked") private Value search(Node x, Key key, int ht) { Entry[] children = x.children; // external node到最底層葉子結(jié)點(diǎn)，遍歷 if (ht == 0) { for (int j = 0; j < x.m; j++) { if (eq(key, children[j].key)) { return (Value) children[j].val; } } } // internal node遞歸查找next地址 else { for (int j = 0; j < x.m; j++) { if (j+1 == x.m || less(key, children[j+1].key)) { return search(children[j].next, key, ht-1); } } } return null; } /** * Inserts the key-value pair into the symbol table, overwriting the old value * with the new value if the key is already in the symbol table. * If the value is {@code null}, this effectively deletes the key from the symbol table. * * @param key the key * @param val the value * @throws NullPointerException if {@code key} is {@code null} */ public void put(Key key, Value val) { if (key == null) { throw new NullPointerException("key must not be null"); } Node u = insert(root, key, val, height); //分裂后生成的右結(jié)點(diǎn) n++; if (u == null) { return; } // need to split root重組root Node t = new Node(2); t.children[0] = new Entry(root.children[0].key, null, root); t.children[1] = new Entry(u.children[0].key, null, u); root = t; height++; } private Node insert(Node h, Key key, Value val, int ht) { int j; Entry t = new Entry(key, val, null); // external node外部結(jié)點(diǎn)，也是葉子結(jié)點(diǎn)，在樹的最底層，存的是內(nèi)容value if (ht == 0) { for (j = 0; j < h.m; j++) { if (less(key, h.children[j].key)) { break; } } } // internal node內(nèi)部結(jié)點(diǎn)，存的是next地址 else { for (j = 0; j < h.m; j++) { if ((j+1 == h.m) || less(key, h.children[j+1].key)) { Node u = insert(h.children[j++].next, key, val, ht-1); if (u == null) { return null; } t.key = u.children[0].key; t.next = u; break; } } } for (int i = h.m; i > j; i--) { h.children[i] = h.children[i-1]; } h.children[j] = t; h.m++; if (h.m < M) { return null; } else { //分裂結(jié)點(diǎn) return split(h); } } // split node in half private Node split(Node h) { Node t = new Node(M/2); h.m = M/2; for (int j = 0; j < M/2; j++) { t.children[j] = h.children[M/2+j]; } return t; } /** * Returns a string representation of this B-tree (for debugging). * * @return a string representation of this B-tree. */ public String toString() { return toString(root, height, "") + "\n"; } private String toString(Node h, int ht, String indent) { StringBuilder s = new StringBuilder(); Entry[] children = h.children; if (ht == 0) { for (int j = 0; j < h.m; j++) { s.append(indent + children[j].key + " " + children[j].val + "\n"); } } else { for (int j = 0; j < h.m; j++) { if (j > 0) { s.append(indent + "(" + children[j].key + ")\n"); } s.append(toString(children[j].next, ht-1, indent + " ")); } } return s.toString(); } // comparison functions - make Comparable instead of Key to avoid casts private boolean less(Comparable k1, Comparable k2) { return k1.compareTo(k2) < 0; } private boolean eq(Comparable k1, Comparable k2) { return k1.compareTo(k2) == 0; } /** * Unit tests the {@code BTree} data type. * * @param args the command-line arguments */ public static void main(String[] args) { BTree<String, String> st = new BTree<String, String>(); st.put("www.cs.princeton.edu", "128.112.136.12"); st.put("www.cs.princeton.edu", "128.112.136.11"); st.put("www.princeton.edu", "128.112.128.15"); st.put("www.yale.edu", "130.132.143.21"); st.put("www.simpsons.com", "209.052.165.60"); st.put("www.apple.com", "17.112.152.32"); st.put("www.amazon.com", "207.171.182.16"); st.put("www.ebay.com", "66.135.192.87"); st.put("www.cnn.com", "64.236.16.20"); st.put("www.google.com", "216.239.41.99"); st.put("www.nytimes.com", "199.239.136.200"); st.put("www.microsoft.com", "207.126.99.140"); st.put("www.dell.com", "143.166.224.230"); st.put("www.slashdot.org", "66.35.250.151"); st.put("www.espn.com", "199.181.135.201"); st.put("www.weather.com", "63.111.66.11"); st.put("www.yahoo.com", "216.109.118.65"); System.out.println("cs.princeton.edu: " + st.get("www.cs.princeton.edu")); System.out.println("hardvardsucks.com: " + st.get("www.harvardsucks.com")); System.out.println("simpsons.com: " + st.get("www.simpsons.com")); System.out.println("apple.com: " + st.get("www.apple.com")); System.out.println("ebay.com: " + st.get("www.ebay.com")); System.out.println("dell.com: " + st.get("www.dell.com")); System.out.println(); System.out.println("size: " + st.size()); System.out.println("height: " + st.height()); System.out.println(st); System.out.println(); }} |
輸出：
cs.princeton.edu: 128.112.136.12
hardvardsucks.com: null
simpsons.com: 209.052.165.60
apple.com: 17.112.152.32
ebay.com: 66.135.192.87
dell.com: 143.166.224.230
size: 17
height: 2
www.amazon.com 207.171.182.16
www.apple.com 17.112.152.32
www.cnn.com 64.236.16.20
(www.cs.princeton.edu)
www.cs.princeton.edu 128.112.136.12
www.cs.princeton.edu 128.112.136.11
www.dell.com 143.166.224.230
(www.ebay.com)
www.ebay.com 66.135.192.87
www.espn.com 199.181.135.201
www.google.com 216.239.41.99
(www.microsoft.com)
www.microsoft.com 207.126.99.140
www.nytimes.com 199.239.136.200
(www.princeton.edu)
www.princeton.edu 128.112.128.15
www.simpsons.com 209.052.165.60
(www.slashdot.org)
www.slashdot.org 66.35.250.151
www.weather.com 63.111.66.11
(www.yahoo.com)
www.yahoo.com 216.109.118.65
www.yale.edu 130.132.143.21
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
