B-Tree定義

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

B-Tree的特點

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

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

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

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

5、其他結點為內(nèi)部結點，保存索引，即key和next。

每個節(jié)點占用一個盤塊的磁盤空間，一個節(jié)點上有兩個升序排序的關鍵字和三個指向子樹根節(jié)點的指針，指針存儲的是子節(jié)點所在磁盤塊的地址。兩個關鍵詞劃分成的三個范圍域?qū)齻€指針指向的子樹的數(shù)據(jù)的范圍域。以根節(jié)點為例，關鍵字為17和35，P1指針指向的子樹的數(shù)據(jù)范圍為小于17，P2指針指向的子樹的數(shù)據(jù)范圍為17~35，P3指針指向的子樹的數(shù)據(jù)范圍為大于35。

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

1、根據(jù)根節(jié)點找到磁盤塊1，讀入內(nèi)存。【磁盤I/O操作第1次】

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

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

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

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

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

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

JAVA代碼實現(xiàn)


package tree;
 
 
/**
 * Created by bruce_shan on 2018/7/8 17:08.
 * Description : B-樹 也作 B樹 java 實現(xiàn)
 */
public class BTree<Key extends Comparable<Key>, Value> {
 
 private static final int M = 4; // B樹的階數(shù)
 
 private Node root; // B-tree 的根節(jié)點
 private int height; // B-tree 的高度
 private int N; // B-tree 樹中鍵值對的數(shù)目
 
 // B-tree 節(jié)點類型
 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 節(jié)點中的元素類型
 private static class Entry {
 private Comparable key;
 private Object val;
 private Node next; // 指向節(jié)點中下一元素
 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;
 
 // 節(jié)點內(nèi)數(shù)組操作 內(nèi)部遍歷
 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);
 
 // 節(jié)點內(nèi)部數(shù)組操作
 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);
 }
 
 // 分裂節(jié)點成兩半
 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;
 }
}