B-Tree定義

在計算機科學中，B樹（英語：B-tree）是一種自平衡的樹，能夠保持數據有序。這種數據結構能夠讓查找數據、順序訪問、插入數據及刪除的動作，都在對數時間內完成。

B-Tree的特點

1、樹中每個結點最多含有m個孩子（m>=2）；

2、除根結點和葉子結點外，其它每個結點至少有[ceil(m / 2)]個孩子（其中ceil(x)是一個取上限的函數）；

3、若根結點不是葉子結點，則至少有2個孩子（特殊情況：沒有孩子的根結點，即根結點為葉子結點，整棵樹只有一個根節點）；

4、所有葉子結點都出現在同一層(最底層)，葉子結點為外部結點，保存內容，即key和value。

5、其他結點為內部結點，保存索引，即key和next。

每個節點占用一個盤塊的磁盤空間，一個節點上有兩個升序排序的關鍵字和三個指向子樹根節點的指針，指針存儲的是子節點所在磁盤塊的地址。兩個關鍵詞劃分成的三個范圍域對應三個指針指向的子樹的數據的范圍域。以根節點為例，關鍵字為17和35，P1指針指向的子樹的數據范圍為小于17，P2指針指向的子樹的數據范圍為17~35，P3指針指向的子樹的數據范圍為大于35。

模擬查找關鍵字29的過程：

1、根據根節點找到磁盤塊1，讀入內存。【磁盤I/O操作第1次】

2、比較關鍵字29在區間（17,35），找到磁盤塊1的指針P2。

3、根據P2指針找到磁盤塊3，讀入內存。【磁盤I/O操作第2次】

4、比較關鍵字29在區間（26,30），找到磁盤塊3的指針P2。

5、根據P2指針找到磁盤塊8，讀入內存。【磁盤I/O操作第3次】

6、在磁盤塊8中的關鍵字列表中找到關鍵字29。

分析上面過程，發現需要3次磁盤I/O操作，和3次內存查找操作。由于內存中的關鍵字是一個有序表結構，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素。B-Tree相對于AVLTree縮減了節點個數，使每次磁盤I/O取到內存的數據都發揮了作用，從而提高了查詢效率。

JAVA代碼實現


package tree;
 
 
/**
 * Created by bruce_shan on 2018/7/8 17:08.
 * Description : B-樹 也作 B樹 java 實現
 */
public class BTree<Key extends Comparable<Key>, Value> {
 
 private static final int M = 4; // B樹的階數
 
 private Node root; // B-tree 的根節點
 private int height; // B-tree 的高度
 private int N; // B-tree 樹中鍵值對的數目
 
 // B-tree 節點類型
 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;
 }
 }
 // B-tree 節點中的元素類型
 private static class Entry {
 private Comparable key;
 private Object val;
 private Node next; // 指向節點中下一元素
 public Entry(Comparable key, Object val, Node next) {
 this.key = key;
 this.val = val;
 this.next = next;
 }
 }
 
 
 /**
 * 初始化空 B-tree樹
 */
 public BTree() {
 root = new Node(0);
 }
 
 /**
 * 判斷 B-tree 是否是空樹
 */
 public boolean isEmpty() {
 return size() == 0;
 }
 
 public int size() {
 return N;
 }
 
 public int height() {
 return height;
 }
 
 /**
 * get操作
 */
 public Value get(Key key) {
 if (key == null) throw new NullPointerException("key must not be null");
 return search(root, key, height);
 }
 
 /**
 * put 操作
 */
 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);
 N++;
 if (u == null) return;
 
 // need to split 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 Value search(Node x, Key key, int ht) {
 Entry[] children = x.children;
 
 // 節點內數組操作 內部遍歷
 if (ht == 0) {
 for (int j = 0; j < x.m; j++) {
 if (equals(key, children[j].key)) return (Value) children[j].val;
 }
 }
 
 // 外部定位
 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;
 }
 // 插入操作
 private Node insert(Node h, Key key, Value val, int ht) {
 int j;
 Entry t = new Entry(key, val, null);
 
 // 節點內部數組操作
 if (ht == 0) {
 for (j = 0; j < h.m; j++) {
 if (less(key, h.children[j].key)) break;
 }
 }
 // 外部遍歷
 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 return split(h);
 }
 
 // 分裂節點成兩半
 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;
 }
 // 判斷兩個元素是否相等
 private boolean equals(Comparable k1, Comparable k2) {
 return k1.compareTo(k2) == 0;
 }
 
 // 判斷兩個元素的大小
 private boolean less(Comparable k1, Comparable k2) {
 return k1.compareTo(k2) < 0;
 }
}