关于B树与B+树

其实这是一个老生常谈的问题。

这两个数据结构广泛用于外存中，并且相对于其他的树（比如红黑树，AVL树）来说，内存中的性能并不是十分的优秀。

为什么这么说呢？如果是一个AVL树，那么由于它的高度平衡性，我想查找一个数据（键值对），那么一般需要logn的次数。对于一个主存数据结构来说，可以说是得到了几乎二分查找一样的次数了。那么由于数据的分散性，每一次访问，注意：我们这是在访问外存而不是内存。将会时间变得想象不到的多。

这里提一下为什么会差那么多。

我们的操作系统帮我们管理最为复杂的任务，那就是存储空间。一般来说一个进程维护一个页表，内存中（虚拟内存）维护着页框。每一个页都是一个内存块，一般是512字节。这样分配或者换入换出就比较方便。为了达到虚拟内存的目的（简单来说就是让程序员认为存储空间是一个特别大的连续数据空间），就会在访问时不断地换页,内存总是很小的，外存却很大，因此换出的页就会存储在外存中。

’外存就是一般常说的磁盘。

磁盘为了访问一个数据，需要，寻道，等待旋转，传送。（这是一个类似于播放唱片的过程，想一想在老式留声机需要拨动柱头，旋转一会，放出音乐。原理大致相似）。由于机械的速度远远赶不上电的速度，所以延迟很大，即使已经有了很多的调度算法（调度算法目的是减少寻道时间），也无法和内存相比。

那么说完为什么访问外存那么慢，就想一下如何降低这个时间。

B树对于这种情况是一种十分良好的数据结构。

首先B树是一个多叉树，由于树的平衡性，搜索过程中访问的节点次数就越少（我可没说总时间就少了）。

而且对于磁盘中的数据组织这种情况。每一次读取树节点到内存中。同普通的二叉树先比，访问外存次数大大减少。（减少多少呢？大概是log以2为底降到log以t为底，t是分叉数）。

为了有个大概认识，这里给出“构造”的代码。

public class BTree{
    private final int minDegree;
    private Node root=null;
    public BTree(int minDegree){
        this.minDegree=minDegree;
    }
    private class Node{
        int lastKey=-1;
        int[] keys=new int[minDegree*2-1];
        Node[] children=new Node[minDegree*2];
        boolean isLeaf=true;

        @Override
        public String toString() {
            return "node keys:"+ Arrays.toString(keys);
        }
    }
    private void splitNode(Node x,int i){
        System.out.println("split node...");
        Node z=new Node(),y=x.children[i];
        z.isLeaf=y.isLeaf;
        z.lastKey=minDegree-2;
        for(int j=0;j<=z.lastKey;j++){
            z.keys[j]=y.keys[j+minDegree];

        }
        if(y.isLeaf==false){
            for(int j=0;j<minDegree-1;j++){
                z.children[j]=y.children[j+minDegree];
            }
        }
        y.lastKey=minDegree-2;
        for(int j=x.lastKey+1;j>=i+1;j--){
            x.children[j+1]=x.children[j];
        }
        x.children[i+1]=z;
        for(int j=x.lastKey;j>=i;j--){
            x.keys[j+1]=x.keys[j];
        }
        x.keys[i]=y.keys[minDegree];
        x.lastKey++;

    }
    private void insertToNotFullNode(Node x,int key){
        System.out.println("insert ..."+key);
        if(x.isLeaf){
            int j=x.lastKey;
            for(;j>=0&&x.keys[j]>key;j--){
                x.keys[j+1]=x.keys[j];
            }
            x.keys[j+1]=key;
            x.lastKey++;
        }
        else{
            int j=x.lastKey;
            while (j>=0&&x.keys[j]>key){
                j--;
            }
            j++;
            if(x.children[j].lastKey+1==minDegree*2-1){
                splitNode(x,j);
                if(key>x.keys[j]){
                    j++;
                }
            }
            insertToNotFullNode(x.children[j],key);
        }
    }
    public void insertKey(int key){
        System.out.println("inserting :"+key);
        if(root==null)
            root=new Node();
        Node r=root;
        if(r.lastKey+1==2*minDegree-1){
            Node s=new Node();
            root=s;
            s.isLeaf=false;
            s.children[0]=r;
            splitNode(s,0);
            insertToNotFullNode(s,key);
        }
        else{
            insertToNotFullNode(r,key);
        }
    }
    private void visit(Node t){
        if(t!=null){
            int j=0;
            while (j<=t.lastKey){
                visit(t.children[j]);
                System.out.println(t.keys[j]);
                j++;
            }
            visit(t.children[j]);
        }
    }

    public void printAll(){
        visit(root);
    }

}

因为有很多优秀的博客都详细的介绍了二叉树的实现，所以我就不班门弄树了。

概括来说，B树的构造需要一个度 t，除了根节点，一般要求节点数在t-1~2*t-1之间，而且可以看到JAVA代码中有一个划分节点的步骤，这样就能维持平衡性。也就是说B树是从下往上增长的，而且在一个节点内部，都是有序的。

所以可以用二分搜索来加速内部查找。

借用别人的一张图，这显然就是数据库里面的键值对存储法呢。当然我们可以认为内存有限，所以大部分仍然保存到外存中去。当然了，对于这个图，还是要改进成多叉树才能进一步降低访问次数。

对于B树的改进型，B+树，

就是内部结点不再存储数据，只存键，叶子节点才存储值。

页节点含有下一节点的指针，只要找到头，就可以遍历。

这里涉及到一个操作系统的知识，就是，文件是怎么分配的。

利用索引（刚才的树）是完美解决连续分配和连接分配的许多问题。

一般的形式是：

外存中含有n+1个块，其中一个块带有其他n个块的连接。仔细想想和B树是多么的相似啊？

所以一般来说，外存的组织是应用了这两种树的结构的。

数据库（比如MySQL）也应用了这种结构，方便的有序存储。

当运行了上面的示例代码，插入一系列数字之后，printAll（中序）就产生了一个有序列。