如果上面的B+树看的还不是很直观，那么我们再来看一颗更直观一点的；这里我们就不谈什么页分裂问题，这个问题待索引的时候再来探讨，我们来说下B+树和B树在查找方面的比较，首先2者与二叉树比较，提升了磁盘I/O效率，但是B树没有解决遍历元素时效率低的问题，如同上面提出的那个问题，这里我们可以通过B+树来解决，B+树只需要通过叶子节点遍历就可以实现对整棵树的遍历。B+更大的优势在于范围查找，这一点是B树无法比较的，进行范围查找是只需要在叶子结点上遍历即可。B+树的插入和删除都与B树类似，但是插入和删除都是在叶子结点上进行。
上面介绍树的几种不同的数据结构，主要是为了引出B+树，明白这种结构的好处才能为我们后面数据库索引打下基础，另外这里没有介绍红黑树，这个等HashMap源码解读的时候再来看，Java代码实现主要提供平衡二叉树的实现，B树的实现还是给大家提供一个参考https://github.com/int32bit/algorithms/blob/master/B-Tree/src/BTree.java；
二、Java代码实现
public class AVLNode<T extends Comparable<T>> { public T key;//关键字 public int height;//高度 public AVLNode<T> lchild;//左孩子 public AVLNode<T> rchilid;//右孩子 public AVLNode(T key){ this(key,null,null); } public AVLNode(T key,AVLNode<T> lchild,AVLNode<T> rchilid){ this.key=key; this.lchild=lchild; this.rchilid=rchilid; this.height=0; } } public class AVLTree<T extends Comparable<T>> { private AVLNode<T> root; public AVLNode<T> getRoot() { return root; } public AVLTree(){ this.root=null; } public AVLTree(T key){ this.root=new AVLNode<T>(key); } //获取树的高度 private int height(AVLNode<T> node){ if (node!=null){ return node.height; } return 0; } public int height(){ return height(root); } //比较两个值的大小 private int max(int a,int b){ return a>b?a:b; } //递归前序遍历 private void preOrder(AVLNode<T> node){ if (node!=null){ System.out.print(node.key+" "); preOrder(node.lchild); preOrder(node.rchilid); } } public void preOrder(){ preOrder(root); } //中序遍历 private void midOrder(AVLNode<T> node){ if (node!=null){ midOrder(node.lchild); System.out.print(node.key+" "); midOrder(node.rchilid); } } public void midOrder(){ midOrder(root); } //后序遍历 private void postOrder(AVLNode<T> node){ if (node!=null){ postOrder(node.lchild); postOrder(node.rchilid); System.out.print(node.key+" "); } } public void postOrder(){ postOrder(root); } //递归查找key元素 private AVLNode<T> search(AVLNode<T> node,T key){ if (node==null) return node; int compare=key.compareTo(node.key); if (compare<0) return search(node.lchild,key); else if (compare>0) return search(node.rchilid,key); else return node; } public AVLNode<T> search(T key){ return search(root,key); } //LL旋转 private AVLNode<T> llRotation(AVLNode<T> node){ AVLNode<T> newNode; newNode=node.lchild; node.lchild=newNode.rchilid; newNode.rchilid=node; node.height=max(height(node.lchild),height(node.rchilid))+1; newNode.height=max(height(node.lchild),node.height)+1; return newNode; } //RR旋转 private AVLNode<T> rrRotation(AVLNode<T> node){ AVLNode<T> newNode; //根结点右旋 newNode=node.rchilid; node.rchilid=newNode.lchild; newNode.lchild=node; node.height=max(height(node.lchild),height(node.rchilid))+1; newNode.height=max(height(newNode.rchilid),node.height)+1; return newNode; } //LR旋转 private AVLNode<T> lrRotation(AVLNode<T> node){ node.lchild=rrRotation(node.lchild); return llRotation(node); } //RL旋转 private AVLNode<T> rlRotation(AVLNode<T> node){ node.rchilid=llRotation(node.rchilid); return rrRotation(node); } //插入结点 private AVLNode<T> insert(AVLNode<T> node,T key){ if (node==null){ node=new AVLNode<T>(key); }else { int cmp=key.compareTo(node.key);//比较节点的值 if (cmp<0){//小于插入左子树 node.lchild=insert(node.lchild,key); //判断是否失衡 //向左侧插入结点只能照成ll或者lr情况 if (height(node.lchild)-height(node.rchilid)==2){ //插入的结点和当前结点的左子树比较 //大于说明是LR情况否者LL if (key.compareTo(node.lchild.key)>0) node=lrRotation(node); else node=llRotation(node); } }else if (cmp>0){ //同上下面不做介绍 node.rchilid=insert(node.rchilid,key); if (height(node.rchilid)-height(node.lchild)==2){ if (key.compareTo(node.rchilid.key)>0) node=rrRotation(node); else node=rlRotation(node); } }else { System.out.println("添加失败：不允许添加相同的节点！"); } } node.height=max(height(node.lchild),height(node.rchilid))+1; return node; } public void insert(T key){ root=insert(root,key); } //查找最大值 private AVLNode<T> findMax(AVLNode<T> node){ if (node==null) return null; while (node.rchilid!=null){ node=node.rchilid; } return node; } public T finMax(){ AVLNode<T> p=findMax(root); if (p!=null){ return p.key; } return null; } //查找最小值 private AVLNode<T> finMin(AVLNode<T> node){ if (node==null) return null; while (node.lchild!=null){ node=node.lchild; } return node; } public T finMin(){ AVLNode<T> p=finMin(root); if (p!=null){ return p.key; } return null; } //删除结点 private AVLNode<T> remove(AVLNode<T> node,AVLNode<T> del){ if (node==null||del==null) return null; //删除的结点和当前结点比较 int cmp=del.key.compareTo(node.key); if (cmp<0){ //递归向左查找结点 node.lchild=remove(node.lchild,del); //在左子树中删除后该节点失衡，若失衡，则可以肯定的是该节点的右子树比左子树高 if (height(node.rchilid)-height(node.lchild)==2){ AVLNode<T> rTree=node.rchilid;//右子树失衡2种情况 右右和右左 if (height(rTree.lchild)>height(rTree.rchilid)) node=rlRotation(node); else node=rrRotation(node); } }else if (cmp>0){ node.rchilid=remove(node.rchilid,del);//同上相反左边失衡 if (height(node.lchild)-height(node.rchilid)==2){ AVLNode<T> lTree=node.lchild; if (height(lTree.rchilid)>height(lTree.lchild)) node=lrRotation(node); else node=llRotation(node); } }else { //找到了要删除的节点，该节点左右子树都不为空 if ((node.lchild!=null)&&(node.rchilid!=null)){ //判断左右孩子的高度 if (height(node.lchild)>height(node.rchilid)){ //如果左子树高度大于右子树 //则找到左子树最大的结点替换当前结点 //这样操作会避免失衡 AVLNode<T> maxNode=findMax(node.lchild); node.key=maxNode.key; node.lchild=remove(node.lchild,maxNode); }else { //同上 AVLNode<T> minNode=finMin(node.rchilid); node.key=minNode.key; node.rchilid=remove(node.rchilid,minNode); } }else {//单一结点则删除 node=(node.lchild!=null)?node.lchild:node.rchilid; } } return node; } public void remove(T key){ AVLNode<T> removeNode=search(key); if (removeNode!=null) root=remove(root,removeNode); } } public class AVLTest { private static int arr[]= {1,2,3,4,5,6,7,8,9,10,12,11,13,14,15 }; public static void main(String[] args) { AVLTree<Integer> tree = new AVLTree<Integer>(); for (int i=0;i<arr.length;i++){ System.out.printf("%d ", arr[i]); tree.insert(arr[i]); } System.out.printf("\n前序遍历: "); tree.preOrder(); System.out.printf("\n中序遍历: "); tree.midOrder(); System.out.printf("\n后序遍历: "); tree.postOrder(); System.out.printf("\n"); System.out.printf("高度: %d\n", tree.height()); System.out.printf("最小值: %d\n", tree.finMin()); System.out.printf("最大值: %d\n", tree.finMax()); tree.remove(7); System.out.printf("\n高度: %d", tree.height()); System.out.printf("\n中序遍历: "); tree.midOrder(); } }