实现a B

/**
来 自 时 代      J a v a   公   众 号 - nowjava.com
**/

import java.util.LinkedList;

import java.util.Queue;


class BTree<Key extends Comparable<Key>, Value> {


  public static int M = 4;


  private Node root;

  // height of BTree

  private int HT;

  // number of key-value pairs in BTree

  private int N;


  // linked list

  


  public BTree() {

    root = new Node(0);
    /**
     * N o w  J a v a  .   c o m 提 供 
    **/

  }


  public int size() {

    return N;

  }


  public boolean isEmpty() {

    return N == 0;

  }


  public int height() {

    return HT;

  }


  public Value get(Key k) {

    return search(root, k, HT);

  }


  private Value search(Node x, Key k, int ht) {

    Entry[] children = x.children;


    if (ht == 0) {

      for (int j = 0; j < x.m; j++) {

        if (eq(k, children[j].key))

          return (Value) children[j].value;

      }

    } else {

      for (int j = 0; j < x.m; j++) {

        if (j + 1 == x.m || less(k, children[j + 1].key))

          return search(children[j].next, k, ht - 1);

      }

    }

    return null;

  }


  public void put(Key k, Value v) {

    Node u = insert(root, k, v, HT);

    N++;


    if (u == null)

      return;


    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;

    HT++;

  }


  private Node insert(Node h, Key k, Value v, int ht) {

    int j;

    Entry t = new Entry(k, v, null);


    if (ht == 0) {

      for (j = 0; j < h.m; j++) {

        if (less(k, h.children[j].key))

          break;

      }

    } else {

      for (j = 0; j < h.m; j++) {

        if ((j + 1 == h.m) || less(k, h.children[j + 1].key)) {

          Node u = insert(h.children[j++].next, k, v, 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);

  }


  public Iterable<Key> keys() {

    Queue<Key> queue = new LinkedList<Key>();

    return keys(root, HT, queue);

  }


  private Iterable<Key> keys(Node h, int ht, Queue<Key> queue) {

    Entry[] children = h.children;


    if (ht == 0) {

      for (int j = 0; j < h.m; j++)

        queue.add((Key) children[j].key);

    } else {

      for (int j = 0; j < h.m; j++)

        queue = (Queue<Key>) keys(children[j].next, ht - 1, queue);

    }


    return queue;

  }


  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 less(Comparable k1, Comparable k2) {

    return k1.compareTo(k2) < 0;

  }


  private boolean eq(Comparable k1, Comparable k2) {

    return k1.compareTo(k2) == 0;

  }


  public static void main(String[] args) {

    BTree<String, Integer> btree = new BTree<String, Integer>();

    btree.put("q", 1);

    btree.put("w", 1);

    btree.put("e", 1);

    btree.put("r", 1);

    btree.put("t", 1);

    btree.put("y", 1);

    btree.put(