B-Tree、B+Tree

---

B-Tree

---

B 树又叫平衡多路查找树。一棵m阶的B树的特性如下：

• 树中每个结点最多含有m个孩子（m>=2）；
• 除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；
• 若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
• 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
• 每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，……，Kn，Pn)。其中：
  
  • Ki (i=1…n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
  • Pi为指向子树根的接点，且指针P(i-1)指向子树中所有结点的关键字均小于Ki，但都大于K(i-1)。
  • 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。

---

B-Tree的度：

• 结点：表示树中的元素。
• 结点的度：拥有子结点的个数。
• 叶子：度为0的结点。
• 树的度：树中结点的最大的度。
• 结点的层次：根结点是第一层，它的孩子结点是第二层，依次类推。
• 树的高度：最大层次数。
• B-Tree中每个节点能包含的关键字的数量有一个上界和下界。下界称为B-Tree的最小度数。

// 上图是一个度数为2的B-Tree，而不是 4,此处 B-Tree 的度指代的是B-Tree的最小度数

// 另一篇博文中对B-Tree的描述如下：
   d为大于1的一个正整数，称为B-Tree的度。
   每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d

// 如果按照二叉树中对度的定义去理解的话，d 是节点的最大孩子数，那么非叶子节点拥有的指针个数 n 就应该等于 d , 又何谈 n <= 2d , 因为随着指针个数的增大，B-Tree 的度也在随之增大，n 的上限永远也达不到 2d 

// 此处个人理解有误，纠结了好久。

---

B-Tree的高度

• 从B-Tree的最小度来计算

  • B树上大部分操作所需的磁盘存取次数与B树的高度成正比。下面分析B树的最坏高度情况。如果n>=1, 则对任意一棵包含n个关键字、高度为h（从0开始）、最小度数t>=2的B树有： h = logt((n+1)/2);

  • 证明：

    • 如果一棵B-Tree的高度为h，最小度数 t （即每个节点中包含的关键字数量的下界）
    • 根节点至少包括一个关键字，而其他节点至少t个关键字。t+1 个孩子
    • 深度为0的节点，即根节点，只有1个节点，至少有t个关键字
    • 深度为1的节点至少有2个，至少有2t个关键字
    • 深度为2的节点至少有2(t+1)个，至少有2t(t+1)个关键字（每个节点中关键字数量的下限t，则该节点至少有t+1个孩子节点）
    • 深度为3的节点至少为2*(t+1)2个，至少有2t*(t+1)2个关键字
    • 深度为h-1的节点至少有2(t+1)h−2个，至少有2t(t+1)h−2个关键字
    • 深度为h 的节点至少为2(t+1)h−1个，深度为h的叶子节点，不保存关键字信息，因此，
    • n = t+2t+2(t+1)t+2t(t+1)2+……+2t*(t+1)h−2
    • t ≥ 1

    • n - 1 ≥ 2( t +t2 +t3+……+th−2)
      （
      此处：类比二叉树，节点总数
      n = 1+2 + 22 + …….+2h−1
      n = 2h - 1
      h = log2(n+1)
      ）
      n - 1 ≥ 2(th−2 - 1)

      所以：h≥logt(n+1)2

---

• 从B-Tree的阶数计算

  • 若B树某一非叶子节点包含N个关键字，则此非叶子节点含有N+1个孩子结点，而所有的叶子结点都在第I层，我们可以得出：
    
    1. 因为根至少有两个孩子，因此第2层至少有两个结点。
    2. 除根和叶子外，其它结点至少有┌m2┐个孩子，
    3. 因此在第3层至少有2*┌m2┐个结点，
    4. 在第4层至少有2*┌(m2)2┐个结点，
    5. 在第 I层至少有2*┌(m2)(I−2)┐个结点，于是有： N+1 ≥ 2*┌(m2)(I−2) )┐；
    6. 考虑第L层的结点个数为N+1，那么2*┌(m2)(I−2) )┐≤N+1，也就是L层的最少结点数刚好达到N+1个，即： I≤logm2(N+1)2+2；所以当B树包含N个关键字时，B树的最大高度为l-1（因为计算B树高度时，叶结点所在层不计算在内），即：l−1=logm2(N+1)2+1。

---

B-Tree 数据检索

检索过程描述

• 首先从根节点进行二分查找
• 如果找到则返回对应节点的data
• 否则对相应区间的指针指向的节点递归进行查找
• 根据根节点的数据与需要查找的数据进行比较，确认走哪个分支
• 直到找到节点或找到null指针，前者查找成功，后者查找失败

伪代码实现

BTree_Search(node, key) {
    if(node == null) return null;
    foreach(node.key)
    {
        if(node.key[i] == key) return node.data[i];
            // 走节点的左侧指针指向的分支
            if(node.key[i] > key) return BTree_Search(point[i]->node);
    }
    // 走节点的右侧指针指向的分支
    return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);

时间复杂度

• 查找次数与高度 h 有关，h≥logt(n+1)2
• 时间复杂度为：O(logdN)

---

B+Tree

B+树是B-树的变体，也是一种多路搜索树，其定义基本与B-树同，区别：

• 1.非叶子结点的子树指针与关键字个数相同；
• 2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i],K[i+1])的子树（B-树是开区间）；
• 3.为所有叶子结点增加一个链指针；在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree；目的：是为了提高区间访问的性能
• 4.所有关键字都在叶子结点出现
• 5.B+Tree中叶节点和内节点一般大小不同；虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间

特性：

• 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
• 不可能在非叶子结点命中查询结果；数据记录存储在叶子节点中
• 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
• 更适合文件索引系统；
• 更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关

---

参考资料

• B-Tree 、B+树、B*树
• 树的术语及性质