汤科资源网

数据结构 --- B树

在我前面几篇文章中介绍了一系列自平衡二叉树，今天我们来学习一个特殊类型的自平衡搜索树，但它不是二叉树，它的每个节点可以存储超过一个key值，你可以认为它是一颗二叉搜索树的广义形式。这就是B树。

下图所示的就是一颗B树。

前面我们学习的自平衡二叉树，如AVL树，红黑树性能都不错，为什么还要B树呢？

假设你要开发一个操作系统，对磁盘的管理是操作系统的必要功能之一，而磁盘上的文件往往很大，但是我们之前学习的二叉树都是假定整个数据常驻内存的，我们可以把磁盘的所有数据都搬入内存进行管理吗？实际上这是有困难的甚至是不可能的。因为自平衡二叉树由于树高h=log2(n), n为节点数，所以诸如查找，插入，删除操作的访问磁盘的I/O平均次数为log2(n)。这个时候使用我们使用诸如红黑树等二叉树操作文件数据效率就会很低，因为I/O操作十分耗时。

那么如何改进呢?

我们看上面对于n个节点的自平衡二叉树来说I/O次数为log2(n)。无论数据结构怎么选择节点数n是不随人的意愿改变的。那么只有一个地方可以优化了就是log2(n)中底数2，如果我们在每个节点存储的数据多余2两个，并且每个节点的子树也多于两个，比如m个(m>2), 那么log2(n)中的2就可以改为m，I/O次数就可以改为logm(n)。在m > 2的情况下logm(n) < log2(n) 对吧(不明白的同学，看一下初中或者高中数学) 。也就是我们把树高压低了，所以我们I/O次数就减少了，也就提升了效率。B树正是基于这样的思想提出的。

首先我们来定义B树的阶，B树的阶表示一个节点最多有多少个孩子节点，通常我们用m表示，m=2时B树就变为一颗二叉树。下面我们看看B树的特性：

1. 所有的叶子节点都有相同的深度(处于同一level)
2. 每一个节点存储的key值按照升序排列
3. 对于每一个节点增加一个布尔值, x.leaf，x.leaf = true,表明其是叶子节点
4. 如果B树的阶数m，那么每一个内部节点最多有m-1个key，除根节点外的其它节点最少应有m/2 - 1个key。
5. 除了根节点以外，其余节点最多可以有m个子节点，最少有m/2个子节点
6. 根节点至少有1个key和 至少有两个孩子节点(如果有孩子节点的话)
7. 一颗拥有n个节点的B树，那么该B树的最小高度h(min) = logm(n+1) - 1
8. 一颗拥有n个节点的B树，t是一个非根节点所拥有的最少子节点,那么该B树的最大高度h(max) = logt((n+1)/2). 其中t = m/2
9. 节点最左边的子树的所有节点的key值小于该节点最小的key值，最右边的子树所有节点的key值大于节点最大的key值，位于(keyi-1 , keyi)之间的子树的所有节点的key值大于keyi-1小于keyi。

B树的操作：

1. 查找

查找B树上的一个节点跟BST查找类似，不过是BST查找的一种广义形式。这里我们采用递归的方式来查找，具体步骤如下:

1. 首先从根节点开始查找。
2. 依次比较当前搜索节点x节点存储的key与待搜索的k值，尝试找到一个key值大于等于k，并记下最后比较的key值的index。
3. 如果#2中找到了这样的key等于k，那么返回该节点和key的index即可。
4. 判断x的leaf是否为true，如果是那么表示已经搜索到叶子节点，并且没有找到，返回NULL即可。
5. 根据#2中记录的index值递归搜索其对应的子树。

下面图示展示整个查找过程, 假设我们要在下图中搜索120。

1. 插入

B树在插入新节点时总是插入到叶子节点，这点跟BST一样。但是B树的每个节点都有指定的最大存储数据量，因此插入操作时，我们需要确认被插入的节点是否还有空间。如果被插入的节点空间已满，那么需要对这个节点进行split操作。所以在进行具体插入操作介绍之前，我们先来介绍split操作。

Split: 如下图所示，我们将左侧所示的y节点分拆为右侧所示的y，z两个节点，这个就可以腾出空间来给新插入的key值。Split的同时也伴随着key值的上移，如下图中将子节点的key值上移到了其父节点。

插入操作的步骤:

所以插入操作的流程就是，我们从根节点开发遍历这颗B树，一直到合适的叶子节点，如果叶子节点空间已经满了，那么就split叶子节点，这样我们就有了插入的空间。

具体步骤：

1. 用x来指示要插入的节点
2. 初始时将x设为根节点
3. 如果x不是叶子节点：

1. 根据待插入的key值找到x的对应孩子节点，这里用y表示
2. 如果y空间还未满，将x设为x
3. 如果y的空间已满，那么对y执行split操作，如果key的值小于y的所有空间的中间值，那么将x设为split之后的第一个节点，否则设为第二个节点

1. 直到x变为叶子节点，那么#3所示的循环就结束了，此时x一定是有存储空间的，因为如果没有在#2已经split过了，所以直接插入key即可。

下面简单展示一下一个简单的插入过程：将100插入一颗B树。

1. 删除

从B树上删除一个节点要比插入一个节点复杂的多。因为我们可以删除任何节点的key，而插入操作只会插入在叶子节点，一旦我们删除了一个非叶子的key那么就意味着我们需要对该节点的所有子树进行重新调整，以使其仍然满足B树的性质。

还记得吗，在插入操作中我们不能向一个存储的key达到其允许的最大值的节点插入数据，此时我们需要split操作。在进行删除操作的时候，我们也要保证删除后，节点(根节点除外)所持有的key不能低于其允许的最小值, 参加上面叙述的B树的性质#4。

对于B树的删除操作，我们分为三种情况：

Case1：

待删除的key是叶子节点中的key。

1. 删除key后不违反B树中关于每个节点都应该包含的最少key的属性限制。如下图中所示的删除32的情况：

1. 删除key后违反了节点应该包含最少key的数量的属性。在这种情况下，我们可以按照从左到右顺序从它的临近节点可以借用一个key。具体描述如下：

首先，访问它临近的左侧兄弟节点，如果左侧兄弟节点拥有的key的数量有超过其最少数量要求，那么我们就从该节点借一个key过来。

否则，访问它的右侧兄弟节点，看看能否借用一个key。

如下图所示，删除31就是这种情况。

如果两边的兄弟节点都不满足借到key的条件，也就是说他们都只拥有最小数量的key。那么我们需要做merge操作，将当前要删除key的节点要么和左边的兄弟节点合并，要么和右边的兄弟节点合并。这个merge操作是通过其父节点完成的。如下图所示删除30的情况：

Case2：

待删除的key节点是B树的内部节点拥有的key。

1. 找到待删除key的拥有者节点的对应于该key的前驱节点，如果该节点拥有的key的数量超过最少数量要求，那么用其前驱节点的最大key替换当前待删除的key即可。如下图所示删除33的情况。

1. 如果#1前驱节点无法满足要求，可以找其后继节点，进行key替换操作。对于后继节点替换时应该取其最小的key值。
2. 如果前驱节点和后继节点都只拥有最少的key的数量，那么将该节点的删除key的左右两个孩子节点合并。如下图所示删除30的情况。

合并完成后，如果合并后的节点的父节点拥有的key的数量少于最小要求，这种情况属于Case1 中#2项，按照其方法操作即可。

Case3：

这是一种会导致树的高度会减小的情况，如果待删除的key存在于一个内部节点当中，并且删除该key后会导致该节点拥有的key的数量少于最低要求，此时寻找该key对应的前驱和后继节点对应的key，如果这两个节点也都仅仅拥有最少数量的key，那么就无法借用，这种情况就是Case2 #3描述的情况，所以要对其子节点进行merge操作。

再尝试向兄弟节点借一个key来满足删除后key数量不足的情况，但是此时如果兄弟节点也只有最低数量的key，那么此时将其兄弟节点与其父节点合并也就是做merge操作。同时调整其子节点的父节点为合并后的节点，字节点的顺序依然安装从左到右增序的方向。如下图所示删除10的情况。

下面是C++的代码实现，仅供参考:

#include <iostream>
using namespace std;

class BTreeNode {
  int *keys;
  int t;
  BTreeNode **C;
  int n;
  bool leaf;

   public:
  BTreeNode(int _t, bool _leaf);

  void traverse();

  int findKey(int k);
  void insertNonFull(int k);
  void splitChild(int i, BTreeNode *y);
  void deletion(int k);
  void removeFromLeaf(int idx);
  void removeFromNonLeaf(int idx);
  int getPredecessor(int idx);
  int getSuccessor(int idx);
  void fill(int idx);
  void borrowFromPrev(int idx);
  void borrowFromNext(int idx);
  void merge(int idx);
  friend class BTree;
};

class BTree {
  BTreeNode *root;
  int t;

   public:
  BTree(int _t) {
    root = NULL;
    t = _t;
  }

  void traverse() {
    if (root != NULL)
      root->traverse();
  }

  void insertion(int k);

  void deletion(int k);
};

// B tree node
BTreeNode::BTreeNode(int t1, bool leaf1) {
  t = t1;
  leaf = leaf1;

  keys = new int[2 * t - 1];
  C = new BTreeNode *[2 * t];

  n = 0;
}

// Find the key
int BTreeNode::findKey(int k) {
  int idx = 0;
  while (idx < n && keys[idx] < k)
    ++idx;
  return idx;
}

// Deletion
void BTreeNode::deletion(int k) {
  int idx = findKey(k);

  if (idx < n && keys[idx] == k) {
    if (leaf)
      removeFromLeaf(idx);
    else
      removeFromNonLeaf(idx);
  } else {
    if (leaf) {
      cout << "The key " << k << " is does not exist in the tree\n";
      return;
    }

    bool flag = ((idx == n) ? true : false);

    if (C[idx]->n < t)
      fill(idx);

    if (flag && idx > n)
      C[idx - 1]->deletion(k);
    else
      C[idx]->deletion(k);
  }
  return;
}

// Remove from the leaf
void BTreeNode::removeFromLeaf(int idx) {
  for (int i = idx + 1; i < n; ++i)
    keys[i - 1] = keys[i];

  n--;

  return;
}

// Delete from non leaf node
void BTreeNode::removeFromNonLeaf(int idx) {
  int k = keys[idx];

  if (C[idx]->n >= t) {
    int pred = getPredecessor(idx);
    keys[idx] = pred;
    C[idx]->deletion(pred);
  }

  else if (C[idx + 1]->n >= t) {
    int succ = getSuccessor(idx);
    keys[idx] = succ;
    C[idx + 1]->deletion(succ);
  }

  else {
    merge(idx);
    C[idx]->deletion(k);
  }
  return;
}

int BTreeNode::getPredecessor(int idx) {
  BTreeNode *cur = C[idx];
  while (!cur->leaf)
    cur = cur->C[cur->n];

  return cur->keys[cur->n - 1];
}

int BTreeNode::getSuccessor(int idx) {
  BTreeNode *cur = C[idx + 1];
  while (!cur->leaf)
    cur = cur->C[0];

  return cur->keys[0];
}

void BTreeNode::fill(int idx) {
  if (idx != 0 && C[idx - 1]->n >= t)
    borrowFromPrev(idx);

  else if (idx != n && C[idx + 1]->n >= t)
    borrowFromNext(idx);

  else {
    if (idx != n)
      merge(idx);
    else
      merge(idx - 1);
  }
  return;
}

// Borrow from previous
void BTreeNode::borrowFromPrev(int idx) {
  BTreeNode *child = C[idx];
  BTreeNode *sibling = C[idx - 1];

  for (int i = child->n - 1; i >= 0; --i)
    child->keys[i + 1] = child->keys[i];

  if (!child->leaf) {
    for (int i = child->n; i >= 0; --i)
      child->C[i + 1] = child->C[i];
  }

  child->keys[0] = keys[idx - 1];

  if (!child->leaf)
    child->C[0] = sibling->C[sibling->n];

  keys[idx - 1] = sibling->keys[sibling->n - 1];

  child->n += 1;
  sibling->n -= 1;

  return;
}

// Borrow from the next
void BTreeNode::borrowFromNext(int idx) {
  BTreeNode *child = C[idx];
  BTreeNode *sibling = C[idx + 1];

  child->keys[(child->n)] = keys[idx];

  if (!(child->leaf))
    child->C[(child->n) + 1] = sibling->C[0];

  keys[idx] = sibling->keys[0];

  for (int i = 1; i < sibling->n; ++i)
    sibling->keys[i - 1] = sibling->keys[i];

  if (!sibling->leaf) {
    for (int i = 1; i <= sibling->n; ++i)
      sibling->C[i - 1] = sibling->C[i];
  }

  child->n += 1;
  sibling->n -= 1;

  return;
}

// Merge
void BTreeNode::merge(int idx) {
  BTreeNode *child = C[idx];
  BTreeNode *sibling = C[idx + 1];

  child->keys[t - 1] = keys[idx];

  for (int i = 0; i < sibling->n; ++i)
    child->keys[i + t] = sibling->keys[i];

  if (!child->leaf) {
    for (int i = 0; i <= sibling->n; ++i)
      child->C[i + t] = sibling->C[i];
  }

  for (int i = idx + 1; i < n; ++i)
    keys[i - 1] = keys[i];

  for (int i = idx + 2; i <= n; ++i)
    C[i - 1] = C[i];

  child->n += sibling->n + 1;
  n--;

  delete (sibling);
  return;
}

// Insertion
void BTree::insertion(int k) {
  if (root == NULL) {
    root = new BTreeNode(t, true);
    root->keys[0] = k;
    root->n = 1;
  } else {
    if (root->n == 2 * t - 1) {
      BTreeNode *s = new BTreeNode(t, false);

      s->C[0] = root;

      s->splitChild(0, root);

      int i = 0;
      if (s->keys[0] < k)
        i++;
      s->C[i]->insertNonFull(k);

      root = s;
    } else
      root->insertNonFull(k);
  }
}

// Insertion non full
void BTreeNode::insertNonFull(int k) {
  int i = n - 1;

  if (leaf == true) {
    while (i >= 0 && keys[i] > k) {
      keys[i + 1] = keys[i];
      i--;
    }

    keys[i + 1] = k;
    n = n + 1;
  } else {
    while (i >= 0 && keys[i] > k)
      i--;

    if (C[i + 1]->n == 2 * t - 1) {
      splitChild(i + 1, C[i + 1]);

      if (keys[i + 1] < k)
        i++;
    }
    C[i + 1]->insertNonFull(k);
  }
}

// Split child
void BTreeNode::splitChild(int i, BTreeNode *y) {
  BTreeNode *z = new BTreeNode(y->t, y->leaf);
  z->n = t - 1;

  for (int j = 0; j < t - 1; j++)
    z->keys[j] = y->keys[j + t];

  if (y->leaf == false) {
    for (int j = 0; j < t; j++)
      z->C[j] = y->C[j + t];
  }

  y->n = t - 1;

  for (int j = n; j >= i + 1; j--)
    C[j + 1] = C[j];

  C[i + 1] = z;

  for (int j = n - 1; j >= i; j--)
    keys[j + 1] = keys[j];

  keys[i] = y->keys[t - 1];

  n = n + 1;
}

// Traverse
void BTreeNode::traverse() {
  int i;
  for (i = 0; i < n; i++) {
    if (leaf == false)
      C[i]->traverse();
    cout << " " << keys[i];
  }

  if (leaf == false)
    C[i]->traverse();
}

// Delete
void BTree::deletion(int k) {
  if (!root) {
    cout << "The tree is empty\n";
    return;
  }

  root->deletion(k);

  if (root->n == 0) {
    BTreeNode *tmp = root;
    if (root->leaf)
      root = NULL;
    else
      root = root->C[0];

    delete tmp;
  }
  return;
}