B树和B+树的理解

B树：

  所谓B树就是B-tree

  一个m阶的B数，结构具有以下特点：

    1.树中每个节点的子树的数量：

      1.节点为根节点：

        1.至少有2个子树

        2.至多有m个子树

      2.节点为非根节点的非终端节点：

        1.至少有m/2的上界个子树（[m/2]）,假设m=3，那么其子树最少为2个

        2.至多有m个子树

  节点内容的特点：

    1.每个非叶子节点的关键字数量

      最多为m-1个，最少为[m/2]-1个(m=3，则最少为1个)

    2.每个节点中包含头指针、尾指针

      1.头指针指向的子树中的所有关键字都小于等于该结点中最小的关键字

      2.尾指针指向的子树中的所有关键字都大于等于该节点中最大的关键字

    3.当结点中的关键字数量大于等于2的时候，在a,b关键字中间会有一个指针

      他指向的子树中的关键字大小都介于a,b之间。(包括a，b)

  B树的简图：

    

B+树

  B+树是B树的一种改进数据结构

  其物理结构类似于B树

  结点内容上稍有不同：

    1.B+树的所有叶子节点包含着所有关键字的信息，他们有一个sqt指针从小到大连接起来。

    2.只有叶子结点上才有关键字对应的data数据信息。

    3.非叶子节点上的关键字都是其子树中的最大值(最小值).

    4.结点中的关键字数量等于该结点的子树的数量。

  B+树简图：

   

  

     注意：

       1.在B树上查找有两种方式：

         1.根据B+树，从根节点往下查找，直到查找到叶子节点，才会返回查找结果

            前面的非叶子结点中的关键字只用作查找的引导。

         2.根据sqt指针，遍历所有的叶子节点。

-----------------------------------------------------

B+树和B树的主要区别在于：

  1.B+树的非叶子结点只包含关键字，不包含实际的值

  2.B+所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

B+ 树的优点在于：
  1. 由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的关键字。

   数据存放的更加紧密，具有更好的空间局部性。

   因此访问叶子节点上关联的数据也具有更好的缓存命中率。
  2.B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。

   而且由于数据顺序排列并且相连，所以便于区间查找和搜索。

B树的缺点：

  B树访问所有的关键字，需要进行每一层的递归遍历。

  相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

B树的优点：

  其优点在于，由于B树的每一个节点都包含key和value，因此如果关键字离根节点更近，访问也更迅速。

--------------------------------------------------------

参考：http://blog.sina.com.cn/s/blog_4e0c21cc01010itp.html