注意：首先需要说明的一点是：B-树就是B树，没有所谓的B减树

引言

我们都知道二叉查找树的查找的时间复杂度是Ｏ(log N)，其查找效率已经足够高了，那为什么还有Ｂ树和Ｂ＋树的出现呢？难道它两的时间复杂度比二叉查找树还小吗？

答案当然不是，Ｂ树和Ｂ＋树的出现是因为另外一个问题，那就是磁盘ＩＯ，众所周知ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的节点。造成大量磁盘ＩＯ操作（最坏情况下为树的高度）。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。
　　所以，我们为了减少磁盘ＩＯ的次数，就你必须降低树的深度，将“瘦高”的树变得“矮胖”。一个基本的想法就是：

• (1)、每个节点存储多个元素
• (2)、摒弃二叉树结构，采用多叉树

这样就引出来了一个新的查找树结构 ——多路查找树。 根据AVL给我们的启发，一颗平衡多路查找树(B~树)自然可以使得数据的查找效率保证在O(logN)这样的对数级别上。即多路平衡查找树

下面来具体介绍一下B树（Balance Tree），

Ｂ树

B树的定义

一个m阶的B树具有如下几个特征：B树中所有结点的孩子结点最大值称为B树的阶，通常用m表示。一个结点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分为k个子集。
这里 k 表示为度，而m 表示为阶数

1. 根结点至少有两个子女。
2. 每个中间节点都包含k-1个元素和k个孩子，其中 ceil（m/2） ≤ k ≤ m
3. 每一个叶子节点都包含k-1个元素，其中 ceil（m/2） ≤ k ≤ m
4. 所有的叶子结点都位于同一层。
5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分
6. 每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An）其中，Ki(1≤i≤n)为关键字，且Ki<Ki+1(1≤i≤n-1)。
   Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。n为结点中关键字的个数，满足ceil(m/2)-1≤n≤m-1。

示例：三阶B树

B树的两种定义

B树的两种定义，一种是算法导论中的度数说；另一种是维基百科的阶数说。

度数：在树中，每个节点的子节点（子树）的个数就称为该节点的度（degree）。
阶数：（Order）阶定义为一个节点的子节点数目的最大值。（自带最大值属性）
然后再结合B树来理解具体含义：

度数与阶数的区别

每个节点（结点）所包含的关键字个数有上界和下界。用一个被称为B树的最小度数（minmum degree）的固定整数t>=2来表示这些界。

a . 除根节点外每个节点至少包含 t-1 个关键字；至少有t个孩子。
b . 每个节点至多可包含 2t-1 个关键字，至多 2t 个孩子节点。

比如当t=2时，每个内部节点可以有2，3，4个孩子。此时该B树的阶为4。

至于这两种定义的差别请参考知乎为什么 B-tree 在不同著作中度的定义有一定差别？

我这里只做简单的介绍，度的定义用来优化阶的定义，主要却别在于，阶数只能定义一个节点满和不满的情况，而度则是在基础上对应了 不满，半满，和全满的情况。 半满对应阶数的满情况，当节点达到全满的情况下才去分裂节点，这样既能满足b树的平衡，用能减少分裂带来的需要找到父节点所带来的开销，毕竟b树的应用场景还是数据库的索引。

查询

以上图为例：若查询的数值为５：

• 第一次磁盘ＩＯ：在内存中定位（与17、35比较），比17小，左子树；
• 第二次磁盘ＩＯ：在内存中定位（与８、12比较），比８小，左子树；
• 第三次磁盘ＩＯ：在内存中定位（与3、5比较），找到5，终止。

整个过程中，我们可以看出：比较的次数并不比二叉查找树少，尤其适当某一节点中的数据很多时，但是磁盘IO的次数却是大大减少。比较是在内存中进行的，相比于磁盘IO的速度，比较的耗时几乎可以忽略。所以当树的高度足够低的话，就可以极大的提高效率。相比之下，节点中的元素多点也没关系，仅仅是多了几次内存交互而已，只要不超过磁盘页的大小即可。

插入

插入逻辑

对度数为ｋ的m阶B树，新结点一般是插在叶子层。通过检索可以确定关键码应插入的结点位置。然后分两种情况讨论：

1. 如果根节点的关键字 等于 2k - 1 则根节点分裂（）
2. 循环找到B树要插入的叶节点（因为插入总发生在叶子节点）
   在插入过程中会遇到节点数 满足 2k - 1的节点，遇到这样的节点就要分裂（以度数k为中心点分裂）。当分裂完成之后，必然会产生t 和 t - 1 关键字的两个节点，而分裂的节点又会上升到父节点当中去，所以，父节点的关键字数不能等于 2k - 1否则将不匹配B数的定义
3. 当经过第二步完成的时候，必然会找到一个叶子节点，其关键字 小于等于 2k - 1，然后插入改节点。注意这里面的关键字可以是 小于，也可以是等于。

注意： 为什么没有用阶数m用于区分原因就是，当m 数是一个固定的数字，没有缓冲边界。所以，一定m 满足了某种特定的条件，则必须要要分裂，分裂导致的父节点关键字+1 可能会引起父节点的分裂。一次类推，导致这种分裂将会一直想上直到根节点，在索引中目的就是要减少内存页的置换次数，如果一直分裂到父节点，意味着内存页面的置换需要一直进行到父节点。因此，为了减少这次的置换调用，算法导论中用了度数来替代阶数的定义，这样就是的每个非叶子节点的关键字个数从放宽了一个限制，在每次插入的时候，在进行分裂，这样就避免了上述多余一次的调用。

插入举例

例如：
我们以[13, 3, 17, 10, 4, 12, 19, 9, 15, 18, 8, 2, 0, 6, 1, 16, 7, 11, 5, 14] 序列来插入

例如：

插入

插入逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def insert(self,key):
    if len(self.root) == self.degree * 2 - 1:
        ## 分裂根节点
        self.root = self.root.split(node(isLeaf=False),self.degree)
        self.nodeNum +=2
    nd = self.root
    while True:
        idx = nd.findKey(key) # 找到key 的位置
        if idx < len(nd) and nd[idx] == key:return
        # 插入操作总在叶子节点发生
        if nd.isLeafNode():
            nd.insert(idx,key)
            self.keyNum+=1
            return
        else:
            chd = nd.getChd(idx)
            # 当节点分裂只会，chd 就已经在树中被阻断了，因此这边要记下来，应为chd的child 毕竟
            if len(chd) == self.degree*2-1: 
                # split 返回的其实是chd 的parent_node 很为在split 就已经处理过了parent
                # 所以下次插入的key的寻找节点还要在这里开始
                nd = chd.split(nd,self.degree)
                self.nodeNum +=1
            else:
                nd = chd

分裂

我们来看分裂的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def split(self,prt,t):
    # 度数 可以用来分割节点   prt 为parent_node
    k = self[t-1]
    nd1 = node()
    nd2 = node()
    nd1.keys,nd2.keys = self[:t-1], self[t:] # note that t is 1 bigger than  key index
    nd1.isLeaf = nd2.isLeaf = self.isLeaf
    # 非叶子节点的分裂
    if not self.isLeaf: 
        # note that  children index is one bigger than key index, and all children included
        nd1.children, nd2.children = self.children[0:t], self.children[t:] 
    # connect them to parent
    idx = prt.findKey(k)
    if prt.children !=[]: prt.children.remove(self) # remove the original node
    prt.insert(idx,k,nd2)
    prt.insert(idx,nd = nd1)
    return prt

最后结果

最后的树结构如下

删除

Ｂ树中关键字的删除比插入更复杂，在这里，只介绍其中的一种方法：

在B树上删除关键字k的过程分两步完成： 找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。

第一步 找出删除节点

• 若该结点为非叶结点，
  1. 找到被删除的key所在的节点。
  2. 在key节点所在的子树找到叶节点,并找出改叶节点的最大的关键字Y,并记录下查找的节点的路径。
  3. 替换这个Y,当前key
  4. 然后依次从后往前遍历节点路径中不满足定义的节点，然后根据情况左选右选或者合并，用来保持b树的平衡。

第一步 由小到大自平衡

• 如果被删关键字所在结点的原关键字个数小于k - 1，说明删去该关键字后该结点不满足B树的定义。

• 自平衡的过程就是想兄弟或者父母借节点，使得父兄组成的树中是自平衡的，这个时候会有如下几种情况

  • 兄弟关键字个数大于 k
  • 左边和右边关键字个数都小于等于 k

• 兄弟关键字个数大于 k
  则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。然后将上升的左右节点根据情况连接到改节点的左右孩子上

例如： 删除3 这个节点

• 左边和右边关键字个数都小于等于 k

  1、 将兄弟节点合并成一个节点
  2、 将父节点拿下一个来放到这个新节点当中
  3、 删除父节点拿下来的这个key
  4、 然后父节点在自平衡一下

例子： 我们来看一下 删除3后在接近这删除2

• 第一步：删除节点 这个时候我们路保存了路径
  
• 第二部，兄弟节点过少，无法满足平衡，合并兄弟节点，将父节点拿下来
• 第三部（左旋转），这个父节点（1,2的父节点） 再次自平衡，将root 的4 拿下来，root节点的下一个孩子的最小值拿上来8，然后，然后8的左孩子给到 1，2 父节点的右孩子
  

总之，设所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删除。

我们来看一下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

def rebalance(self,fathers):
    # fatners 表示 这个节点，key 节点位置 父节点的指针
    nd,keyIdx,chdIdx = fathers.pop()
    while len(nd)<self.degree - 1:
        # 当节点已经不平衡的时候 找到他的父节点
        prt,keyIdx,chdIdx = fathers[-1]
        # 左边兄弟
        lbro = [] if chdIdx==0 else prt.getChd(chdIdx-1)
        # 右边的兄弟
        rbro = [] if chdIdx==len(prt) else prt.getChd(chdIdx+1)
        # 如果左右兄弟都没有到 degree 则两个兄弟合并
        if len(lbro) < self.degree and len(rbro) < self.degree:  # merge two deficient nodes 
            beforeNode,afterNode = None,None
            # 把父亲的 keyindex 拿下来，然后在想左边兄弟借一个key
            if lbro ==[]:
                keyIdx = chdIdx
                beforeNode,afterNode = nd,rbro
            else:
            # 如果左边的兄弟为空 则把这个节点和右边的节点合并
                beforeNode,afterNode = lbro,nd
                keyIdx = chdIdx-1      # important, when choosing 
            keys = beforeNode[:]+[prt[keyIdx]]+afterNode[:]
            # 合并节点的孩子
            children = beforeNode.getChildren() + afterNode.getChildren()
            isLeaf = beforeNode.isLeafNode()
            prt.delChd(keyIdx+1)
            del prt[keyIdx]
            nd.update(keys,isLeaf,children)
            prt.children[keyIdx]=nd
            self.nodeNum -=1
        elif len(lbro)>=self.degree:  # rotate  when only one sibling is deficient
            # 右旋转
            keyIdx = chdIdx-1
            nd.insert(0,prt[keyIdx])    # rotate keys
            prt[keyIdx] =  lbro[-1]
            del lbro[-1]
            if not nd.isLeafNode():     # if not leaf, move children
                nd.insert(0,nd=lbro.getChd(-1))
                lbro.delChd(-1)
        else:
            # 左旋转 父节点拿下一个key 父节点右边第一个子树的根节点上升一个节点
            # 上升的一个节点左孩子链接到当前孩子的右子树当中去
            keyIdx = chdIdx
            nd.insert(len(nd),prt[keyIdx])    # rotate keys
            prt[keyIdx] =  rbro[0]
            del rbro[0]
            if not nd.isLeafNode():     # if not leaf, move children
                #note that insert(-1,ele) will make the ele be the last second one
                nd.insert(len(nd),nd=rbro.getChd(0))
                rbro.delChd(0)
        if len(fathers)==1:
            if len(self.root)==0: 
                self.root = nd
                self.nodeNum -=1
            break
        nd,i,j = fathers.pop()

总结

①、B树主要用于文件系统以及部分数据库索引，例如： MongoDB。而大部分关系数据库则使用B+树做索引，例如：mysql数据库；
　　②、从查找效率考虑一般要求B树的阶数m >= 3;
　　③、B-树上算法的执行时间主要由读、写磁盘的次数来决定，故一次I/O操作应读写尽可能多的信息。因此B-树的结点规模一般以一个磁盘页为单位。一个结点包含的关键字及其孩子个数取决于磁盘页的大小。

• ← Previous Post
• Next Post →

赏 支付宝打赏 微信打赏

赞赏一下