MS-数据结构-B-Tree&B+Tree

B-Tree
读作B树(不是B减树)，是一种自平衡的树，能够保持数据有序，这种数据结构能保证查找数据、顺序访问、插入删除元素，都能在对数时间内完成。

• 定义（引用自算法导论）
  一棵B树T具有以下的性质：

  1. 每个节点x，

     • 有n个关键字
     • 每个关键词按照非降序排列，x.key1<=x.key2<=x.key3<=...<=x.keyn

  2. 每个内部节点(非叶节点)，有n+1个指向孩子节点的指针

  3. 每个内部节点的关键字，对孩子节点的关键字范围加以分割

     k1 <= x.key1 <= k2 <= x.key2 <= ... <= x.keyn <= kn+1
     其中ki为孩子节点的关键字，x.keyi为内部节点的关键字
     

     节点(2,6)将孩子节点划分范围 1<2<(3,5)<6<8

  4. 每个叶子节点有相同的深度，即树的高度

  5. 每个节点包含的关键字的个数：

     • 除了根节点以外的每个内部节点，至少有t-1个关键字，有t个孩子
     • 如果树非空，根节点至少有一个关键字
     • 每个节点至多有2t-1个关键字，因此至多有2t个孩子
     • t为B-树的最小度数，t>=2
       （t=2的B树是最简单的B树，每个内部节点可以有2个、3个、4个孩子，即2-3-4树）

B+Tree
B+树和B-树有一些共同点，也有一些新的特征

• 定义

  1. B+树的中间节点不保存关键字，只用来索引，所有数据（关键字）都保存在叶子节点上。
  2. 叶子节点包含了所有的关键字，且叶子节点上的关键字按照非降序排列。
  3. 所有父节点的元素都同时存在于子节点，且在子节点中是最大（或最小）元素。

  4. 有n个元素（等同于关键字，但不是关键字）的内部节点，有n个孩子节点（B-Tree有n+1个孩子）

     
     B+树，叶子节点按非降序链接
  • 特征
    1. 根节点的最大元素也是整棵B+树的最大元素。
    2. 每个叶子节点都含有指向下一个叶子节点的指针，形成一个有序链表。
    3. B+树只有叶子节点含有卫星数据，B-树中每个节点都含有卫星数据。
       因为内部节点没有卫星数据，相同大小的磁盘页可以容纳更多的节点元素，因此B+树比B-树更加的“矮胖”，因此磁盘IO次数会更少
    4. 在聚簇索引(Clustered Index)中，叶子节点直接含有卫星数据，而非聚簇索引(NonClustered Index)，叶子节点含有指向卫星数据的指针。

• B+树查找过程

  查找3， 第一次磁盘IO
  第二次磁盘IO
  第三次磁盘IO
  • 总结
    1. 因为内部节点含有卫星数据，B-树的查找效率不稳定，最好的情况直接查找更节点就找到了，最坏情况要找到叶子节点才可以。
       B+树每次查找都需要查到叶子节点，是稳定的。
    2. 范围查询，B+树只要遍历叶子节点就可以了，而B-树需要复杂的中序遍历
    3. 因为更“矮胖”，B+树需要更少的磁盘IO次数。

为什么用B+树存储索引

问题引入：使用B+树做索引，查找效率大概是log(n)，而hash做索引，效率是o(1)，为什么不用hash做索引呢？

答：文件系统或者数据库的索引一般存在硬盘上，如果数据量特别大的话，不能够一次性全部加载到内存中。

假设内存每次只能加载2个数，我们把数据组成一个3路B-树，这样每个节点最多含有2个元素，查找的时候，每次只加载1个节点就行了。

之所以用B+树，就像上边介绍B+树的时候说的，在范围查找时非常方便，而B-树需要使用中序遍历，进行跨层访问。