6. B树

B树 ： B-Tree是 平衡的 m 路查找树，"B"表示平衡；
严格意义上 ： B-Tree并非二分查找树（多叉结构）；
逻辑上 ： 依旧是二分查找树（详见后续讲解）

---

设计动机

• 弥合不同的存储级别之间的访问速度上的巨大差异，实现高效的 I/O
• 事实实践中 ： 系统存储容量的增长速度 << 应用问题规模的增长速度

出现的背景：平衡二叉树的查找效率是非常高的，并可以通过降低树的深度来提高查找的效率。但是当数据量非常大，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B树是解决这个问题的很好的结构
采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

典型的数据库规模/存储容量对比：
1. 1980年 ： 10MB / 1MB    10倍
2. 2000年 ： 1TB / 1GB     1000倍

* 这就是相对而言：内存"越来越小"！

---

那么为什么不将内存做大呢？

• 物理上，存储器的容量越大(小)，访问速度就越慢(快)

B.Gate : 640K ought to be enough for anyone.
够用啦！觉得"不够"，设计来凑。

---

上面叙述的问题，引入高速缓存来解决

1. 事实1 ： 不同容量的存储器，访问速度差异悬殊。
   • 磁盘(ms级别) << 内存(ns级别)， 100000倍
     若内存访问需要1s，则一次外存访问需要一天
   • 为了避免1次外存访问，宁愿访问内存100次...
     所以将最常用的数据存储在最快的存储器中
2. 事实2 ： 从磁盘中读 1 B，与读写 1KB 的时间成本几乎一样
   • 所以典型的采用批量式访问 ： 以页（page）或块（block）为单位，使用缓冲区。
     批量式

B-Tree在其中又起到什么作用呢？

---

---

B-Tree 结构：B树是存储关键码的词条结构，比普通的 BST 更宽，更矮 ！也称之为平衡多路搜索树

典型平衡多路搜索树(平衡m路搜索树)构造过程：

• 将 BST 经适当的合并，得到超级结点
  • 每2代合并 ： 4路，3个关键码(最多)
  • 每3代合并 ： 8路，7个关键码(最多)
  • 每d代合并 ： m路（m=2^d），m-1 个关键码(最多)
• 典型平衡4路搜索树示例图(每2代合并)
  平衡4路搜索树结构
  [注] 实线红框称之为超级结点

逻辑上B树与BBST完全等价，既然如此，为什么还要引入B树？

• 多级存储系统中使用 B-Tree ,可针对外部查找，大大减少 I/O次数.
• [分析]：

  1. 若使用 AVL 树，为什么不够？
     例如 ：
     若有 n = 1G(也就是10^9) 个记录，
     每次查找 需要log(2，10^9) = 30 次 I/O操作 {即AVL的高度为30层} ，
     每次只读出一个关键码，得不偿失。

  2. 那么B树的性能呢？
     充分利用外存对批量访问的高效支持的特点，将此特点转化成优点，层次每降一级，都以超级结点为单位，读入一组关键码
     具体多大为一组（超级结点）： 视磁盘的数据块大小而定

m = #key / page
比如，目前的大多数数据库系统采用 m = 200~300
若取 m = 256 = 2^8 ，则1G的记录每次查找只需 log(256,10^9) <= 4 次 I/O

---

---

B-Tree

定义

• 所谓m阶B-Tree，即平衡的 m 路查找树，其中 m>=3

B-Tree示意图

• 如上图所示：
  外部节点的深度统一相等
  所有叶节点的深度统一相等
  树高H = 外部节点的深度

• B-Tree的阶次 m 的含义：给出超级节点规模的上下限

m 阶B-Tree ：以分支数讨论

• 上限：每个节点最多有 m 个分支
• 下限：
  根节点至少2个分支，
  非根节点至少有⌈m/2⌉个分支

所以也称 m 阶B-Tree 为 ( ⌈m/2⌉ , m )树 ，即超级节点（除根节点）的分支数的上下限 ！！！！！！
[注] 超级节点关键码的个数 = 节点分支数 - 1

例：
m = 4 阶，（2，4）树
m = 5 阶，（3，5）树
m = 6 阶，（3，6）树

B-Tree的画法示例

---

---

B-Tree 的实现

1. 超级节点结构 ： BT_Node，若有n个关键码，则有n+1个孩子分支

B-Tree节点
struct BTNode
{
    BTNode * pstParent;   //父节点指针
    vector<T> Key;        //关键码vector数组，T为关键码数据类型
    vector<BTNode *> Child;  //孩子指针数组
    //结构体设计两个构造
    BTNode()
    {
        pstParent = NULL;
        Child.insert(0,NULL);
    }
    BTNode(T e, BTNode & pLc=NULL, BTNode & pRc=NULL)
    {
        pstParent = NULL;
        Key.insert(0, e);       //仅有一个关键码
        Child.insert(o, pLc);
        Child.insert(1, pRc);   //两个孩子
        if (pLc)
            pLc->Parent = this;
        if (pRc)
            pRc->Parent = this;
    }
}

BTNode结构体

2. B-Tree封装类

class BTree
{
    procted:
        int _size;               关键码总数
        int _order;              阶数
        BTNode * _root;          根节点

        BTNode * _hot        记忆热点，作为标记 Search（）最后访问的非空节点的位置
  
/*********************************************************************/
        经过动态操作后（插入或删除），如何恢复合法B树的操作
        void solveOverflow();     因插入而上溢后的分裂处理
        void solveUnderflow();    因删除而下溢后的合并处理
/*********************************************************************/

    public:
        BTNode * Search();                 //查找
        bool insert(const T & e);          //插入
        bool remove(const T & e);          //删除
}

---

算法实现

1. B-Tree 查找算法实现（ Search(key) ）

根据 B-Tree 超级节点的特点，将必需的节点载入内存，尽可能的减少I/O操作；
[注] B-Tree的失败查找必定终止在外部节点

代码实现 : Code
BTNode * Search(T & e)
{
    BTNode * v = _root;                 //从根节点开始
    _hot = NULL;

    while (v)
    {//逐层查找
        int  r = v->Key.search(e);     //在当前节点对应的Key Vector中顺序查找，并记录 
        if ( 0 <= r && e == v->Key[r])
        {
            return v;                  // 找到了，则返回
        }
        _hot = v;                      // _hot记录
        v = v->Child[ r + 1 ]          ！！！//因为节点中的关键码是单调不减的，如果在当前节点中未找到(未必遍历完节点所有关键码)，则通过记录的 r 值，从Child向量的 r+1 指向对应的下层子树
    }//若因 v 空而退出，则意味着抵达外部节点

    return NULL;
}

注： STL中vector的search(e)函数知识补充
vector.search(e) 只支持有序向量查找，返回值是int类型，表示返回不大于e且下标值最大的下标值

比如 vector  v : [ 2, 4, 6, 7, 7, 9, 11 ]
int r1 = v.search(5);         // r1 = 1
int r2 = v.search(7);         // r2 = 4
int r3 = v.search(9);         // r3 = 5

使用vector正好也满足了B-Tree中序序列单调非降的特点，完美搭配！

B-Tree 查找算法的复杂度：受树高h的影响 log(h)

结论：

• 最大树高：数学推导
  含N个关键码数的m阶B-Tree，最大高度 = ？
  分析： 为使B-Tree更高，内部节点应该尽可能的'瘦'，各层节点数依次是：
  n0 = 1，n1 =2，n2 = 2 * ⌈m/2⌉ ，…… ， nk = 2 * ( ⌈m/2⌉^(k-1) )
  外部节点所在层：
  N+1 = nh >= 2 * ( ⌈m/2⌉^(h-1) ) 所以有 h <= 1 + log( ⌈m/2⌉ , ⌊ (N+1)/2 ⌋ ) = O(log(m,N))
• 最小树高：数学推导
  含N个关键码数的m阶B-Tree，最小高度 = ？
  为此，尽可能'胖'
  n0 = 1， n1 = m ，n2 = m^2 ， …… ，nh = m^h
  考察外部节点所在层 ： N+1 = nh <= m^h
  则有： h >= log(m,N+1)

2. B-Tree 插入算法实现（ insert(e) ）

插入算法实现是个动态过程，也就意味着在此过程中，若破坏了B-Tree的结构，则需要相应的恢复处理

Insert
很明显，若是新插入关键码，必定都是在叶子节点处插入(B-Tree的Search函数找不到关键码，最后_hot记录的是最后一个访问的叶子节点)，如上图，若插入后没有造成节点关键码上溢，则OK；若发生上溢，则需要做分裂处理

B-Tree插入算法代码实现：

bool insert(const T & e)
{
    BTNode * v = Search(e);      首先在B-Tree中查找，确认待插入关键码 e 是否存在
    if ( NULL != v)
        return false;
    
    int r = _hot->Key.search(e);    在最后访问的节点_hot中确认插入位置！！！ _hot肯定是叶子节点，通过vector的search()确定待查入点的位置！！！
    
    _hot->Key.insert( r + 1 , e);    将新关键码插至对应的位置
    _hot->Child.insert(r + 2 , NULL);   与此同时，分支数+1，即创建一个空子树指针作为外部节点

    _size ++;
    
/***********************************************************************/
 插入新关键码后，造成对应节点关键码数超过上限（称为上溢），则需要分裂节点操作
    SolveOverflow( _hot );
/***********************************************************************/

    return true;
}

节点上溢处理 (SolveOverflow) ： 分裂操作

处理流程

• 设上溢节点中关键码为 k0，k1，…… ，km-1
• 取中位数 s = ⌊ m / 2 ⌋，以关键码ks为边界划分为：
  k0，…… ，ks-1，ks ，ks+1 ，…… ，km-1
• 关键码ks上升一层
  并分裂（split）：以所得的两个新节点作为其左右孩子
• 上溢缺陷可能向上传播（ks给上一层parent可能导致上溢传播）,若发生，则逐层向上进行分裂处理，最多亦不过根节点！
  [注] 根节点的上溢操作：提升后的中位数关键码上升，作为根节点，同时树高 +1，这也是分裂处理导致树高增加的唯一情况

算法复杂度：O(h)

图示：6阶B-Tree

最坏情况：即每一层节点都会上溢直至到达根节点，但这种情况出现的概率极低；

SolveOverflow代码实现
后补！！！

---

3. B-Tree 删除算法实现（ remove(e) ）

B-Tree删除关键码也是动态操作，若因为删除关键码导致该节点下溢（即节点关键码个数不足下限），需要做对于的调整恢复处理。

remove

删除算法代码实现：
bool remove(T &e)
{
    BTNode * v = Search(e);      // 找到关键码所处的节点
    if (NULL == v)
        return false;

    int r = v->Key.search(e);     // 找到关键码的秩，也就是下标是第一个!!!
   
1. 如果 v 是叶子节点，直接把关键码移除以及其中一个Child外部节点，这个外部节点为空，所以在这直接规定摘除右孩子外部节点（r+1）
    if (NULL == v->child[0])
    {
        v -> Key.remove(r);         //关键码移除
        v.Child.remove(r+1);        //孩子节点移除
    }
2. 如果 v 是非叶子节点，则 
    else
    {
        
        BTNode * u = v->child[ r+1 ];        // 右子树

    在右子树中一直向左，其实就是找待删除关键码e的中序直接后继关键码
        while (NULL != u->Child[0])
        {
            u = u->Child[0];
        }   while循环后，u 一定指向叶子节点

    交换"待删除关键码和其直接后继关键码"
        v -> Key[ r ] = u->Key[ 0 ];         // 交换，直接后继关键码放在原删除位置
        v = u;                      // 待删除关键码的指针指向直接后继的叶子节点
        r = 0;                     // 现在待删除的关键码就是叶子节点指向的第一个key值

    通过上面的转换，变成按删除叶子节点关键码处理了！！！
        v -> Key.remove(r);         //关键码移除
        v.Child.remove(r+1);        //孩子节点移除
    }

/************************************************************************************/
3. 如果删除关键码后，造成节点下溢，则需要对节点调整恢复，主要做两个操作:"旋转/合并"，后面详细分析；
    SolveUnderflow( v );

/**********************************************************************************/
    return true;
}

[注]
B-Tree删除关键码可参考于BST中的删除节点的做法：

1. 关键码不在叶子节点中的处理类似与 BST中的删除节点的做法：
   找到中序直接后继
   交换两者位置（swap）
   使待删除的关键码数据出现在叶子节点中
   然后像在叶子节点中直接删除即可！！！
2. 关键码在叶子节点中
   直接删除Key Vector和Child Vector

删除关键码示意图

待删除关键码在叶子节点
待删除关键码在不在叶子节点

节点下溢处理 (SolveUnderflow) ： 旋转/合并操作

关键：节点因为删除关键码而造成下溢，删除后则此时节点必恰好包含：⌈m/2⌉ －1 个分支，⌈m/2⌉ －2 个关键码！！！

旋转操作：

什么时候是做旋转？
删除关键码的节点记为V，V发生下溢
情况：若下溢节点V的左（右）兄弟节点有足够的关键码借出，则作旋转处理
[注]：何为兄弟节点有足够关键码 ： 即借出去一个不至于导致自己下溢
条件： 关键码个数 N >= ⌈m/2⌉ ！！！牢记

以左兄弟节点L为例，若L有有足够的关键码，则旋转处理操作过程如下图所示：

下溢旋转操作

合并操作：

什么时候做合并？
情况： 若下溢的节点V的左,右兄弟节点或者不存在，或者不足借出关键码，则作合并操作
[注] ： 何为兄弟节点不够借：即借出一个自己都下溢了
条件：关键码个数 N = ⌈m/2⌉-1 ！！！牢记

假设左右兄弟节点L和R存在其一，只含有⌈m/2⌉-1个关键码，不妨以L为例，则合并处理操作过程如下图所示：

下溢合并操作

下溢缺陷可能会向上传播，导致父节点发生下溢，需要再次利用旋转/合并

---

实例演示：5阶B-Tree

ddd

---

说在最后

对B-Tree的 I/O 操作
考虑到外存操作代价与内存操作代价相当
B-Tree的设计就是存的关键码多，一堆关键码节点进行I/O与一个关键码节点进行I/O，时间上，一堆I/O = 一个I/O，但拿出的关键码更多，更省！！！

---

---

关键字：
B-Tree : m阶也可称为 ( ⌈m/2⌉ , m )树，分支
插入 ~ 上溢 ~ 分裂(中位数)
删除 ~ 下溢 ~ 旋转/合并

B-Tree参考

B树产生的原因:

B树是一种查找树，我们知道，这一类树（比如二叉查找树，红黑树等等）最初生成的目的都是为了解决某种系统中，查找效率低的问题。B树也是如此，它最初启发于二叉查找树，二叉查找树的特点是每个非叶节点都只有两个孩子节点。然而这种做法会导致当数据量非常大时，二叉查找树的深度过深，搜索算法自根节点向下搜索时，需要访问的节点也就变的相当多。如果这些节点存储在外存储器中，每访问一个节点，相当于就是进行了一次I/O操作，随着树高度的增加，频繁的I/O操作一定会降低查询的效率。

一个基本的概念：从外存储器中读取信息的步骤，简单来分，大致有两步

1. 找到存储这个数据所对应的磁盘页面，这个过程是机械化的过程，需要依靠磁臂的转动，找到对应磁道，所以耗时长。
2. 读取数据进内存，并实施运算，这是电子化的过程，相当快。

综上，对于外存储器的信息读取最大的时间消耗在于寻找磁盘页面。那么一个基本的想法就是能不能减少这种读取的次数，在一个磁盘页面上，多存储一些索引信息。B树的基本逻辑就是这个思路，它要改二叉为多叉，每个节点存储更多的指针信息，以降低I/O操作数。

B-Tree磁盘查找示意图

文件查找的具体过程(涉及磁盘IO操作)
为了简单，这里用少量数据构造一棵3叉树的形式，实际应用中的B树结点中关键字很多的。上面的图中比如根结点，其中17表示一个磁盘文件的文件名；小红方块表示这个17文件内容在硬盘中的存储位置；p1表示指向17左子树的指针。

其结构可以简单定义为：

typedef struct {
    /*文件数*/
    int  file_num;

    /*文件名(key)*/
    char * file_name[max_file_num];

    /*指向子节点的指针*/
     BTNode * BTptr[max_file_num+1];

     /*文件在硬盘中的存储位置*/
     FILE_HARD_ADDR offset[max_file_num];
}BTNode;

假如每个盘块可以正好存放一个B树的结点（正好存放2个文件名）。那么一个BTNode结点就代表一个盘块，而子树指针就是存放另外一个盘块的地址。

下面，来模拟下查找文件29的过程：

1. 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作 1次】
2. 此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法我们发现：17<29<35，因此我们找到指针p2。
3. 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作 2次】
4. 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现：26<29<30，因此我们找到指针p2。
5. 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作 3次】
6. 此时内存中有两个文件名28，29。根据算法我们查找到文件名29，并定位了该文件内存的磁盘地址。
   分析上面的过程，发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于IO操作是影响整个B树查找效率的决定因素。

当然，如果使用平衡二叉树的磁盘存储结构来进行查找，那么需要至少4次I/O操作，最多5次，而且文件越多，B树比平衡二叉树所用的磁盘IO操作次数将越少，效率也越高。