B树和B+树

      B树和B+树是一种非常适合用于计算机磁盘存储的数据结构。

      1.B树

     （1）B树的定义(转自 Mysql和B树那些事)

         a.每个节点至多可以拥有m棵子树

         b.根节点，只有至少有2个节点（要么极端情况，就是一棵树就一个根节点，单细胞生物，即是根，也是叶，也是树)。

        c.非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整，图中5阶B树，每个节点至少有3个子树，也就是至少有3个叉)。

         d.非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示该节点中保存的关键字个数，K为关键字且Ki<Ki+1，A为指向子树根节点的指针。

         e.从根到叶子的每一条路径都有相同的长度，也就是说，叶子节在相同的层，并且这些节点不带信息，实际上这些节点就表示找不到指定的值，也就是指向这些节点的指针为空。

     （2）B树长相（转自 从B树、B+树、B*树谈到R 树）：

                   

         由定义可只，B树的节点中包含的关键字个数比孩子节点少1，这么做的原因是因为节点中包含的关键字是取相邻孩子节点关键字的中间值。如图所示，对于磁盘块2来说，8代表索引的关键字，P1是指向第一个孩子节点的指针，第一个孩子节点（磁盘块5）中，关键字升序排列，最大的关键字为5，而P2指向的第二个孩子节点中的关键字的最小值为9.所以磁盘块中第一个关键字为8（5<8<9），这样在查找使通过和关键字的比较，就能得到目标的磁盘块的位置。这里的关键字可以理解为Mysql中的主键即所存储的实际信息。

        2.B+树

         B+树的含义可以看（InnoDB页结构）

         其长相如下（转自 从B树、B+树、B*树谈到R 树）：

                       

        与B树相比有着以下不同：

         a.有n棵子树的节点含有n个关键字而不再是B树中的n-1,（每个关键字对应着其孩子节点的索引故为n）。

         b.所有的叶子节点包含了全部的关键字，及指向含这些关键字记录的指针，且叶子节点本身根据关键字自小而大顺序连接在InnoDB中，叶子节点代表着页，每页之间都有着链表似的结构进行链接。

         c.非叶子节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字，而不像是B树中的存有实际信息。在InnoDB中，同样非叶子节点也是页的一种，使用链表结构链接。