B+ 树删除

2025年3月17日 | 阅读19分钟

B 树和 B+ 树通常用于实现动态多级索引。然而，B 树用于索引的一个缺点是它还在 B 树节点中保存了对应于某个键值的数据指针（指向包含键值的磁盘文件块的指针）。这种方法显著减少了能放入 B 树节点中的项的数量，这导致 B 树结构增加，并且记录的搜索时间变长。B+ 树通过仅在树的叶子节点存储数据指针来消除上述缺陷。

因此，B 树的内部节点和 B+ 树的叶子节点具有非常不同的结构。值得强调的是，由于数据指针仅存在于叶子节点，因此所有键值及其对应的数据指针都必须由叶子节点存储，以便访问。此外，叶子节点相互连接以提供对记录的有序访问。因此，叶子节点构成索引的第一级，而内部节点是多级索引中的其他级别。

为了仅作为调节记录搜索的媒介，一些叶子节点的键值也出现在内部节点中。与 B 树不同，B+ 树有两个阶，“a”和“b”，一个用于内部节点，另一个用于外部（或叶子）节点。这从上面的描述中可以看出。具有“a”阶的内部 B+ 树具有以下节点结构

每个内部节点具有以下结构：其中每个 Ki 是键值对，每个 Pi 是树指针（指向树的另一个节点）（参考图 I）。
每个内部节点包含搜索字段的以下值：K1 < K2 < …. < Kc-1
对于 Pi 指向的子树中的搜索字段“X”的每个值，以下陈述均成立：Ki-1 < X <= Ki，其中 1 < i < c 且 Ki-1 < X。
每个内部节点最多包含 'a' 个树指针。
内部节点每个至少有 ceil(a/2) 个树指针，而根节点至少有 2 个树指针。
如果内部节点有 'c' 个指针，则有 'c -1' 个键值，其中 c< = a。

如果按顺序存储值，则大多数查询都可以更快地处理。但是，期望以排序的方式存储表行并一个接一个地存储是不切实际的，因为这样做需要为添加或删除的每一行重新创建表。

这促使我们考虑将行放入树结构中。我们的初步想法是平衡二叉搜索树，如红黑树，但由于数据库存储在磁盘上，这实际上并没有太大意义。磁盘通过一次读取和写入大量数据块来工作；这些块通常是 512 字节或四千字节大小。二叉搜索树的每个节点仅使用了其中的一小部分。

找到一个更整齐地放入磁盘块的结构是有意义的。

这导致了 B+ 树，其中每个节点最多包含 d 个键和最多 d 个指向子节点的引用。每个引用指向一个子树的根，该子树的所有值都介于节点中两个键之间，因此被认为“介于”节点中的两个键之间。

这里有一个 d=4 的相对较小的树。

B+ 树特性

只有叶子节点可以存储数据点。
键存在于内部节点中。
我们在 B+ 树中使用键进行直接元素搜索。
如果有“m”个元素，“m/2” -1 个键是最小值，“m-1”个键是最大值。
根节点至少有两个子节点和一个键。
根节点以外的每个节点对于“m”个元素来说，可以有最少“m/2”个子节点，最多“m”个子节点。

B+ 树删除过程

B+ 树删除

在 B+ 树中，删除键涉及几个步骤

搜索要删除的键：找到包含要删除键的叶子节点。
删除键：从叶子节点中删除键值对。如果节点有足够的键（满足 B+ 树属性所需的最小键数），则无需进一步操作。
调整树结构：如果叶子节点的键少于所需的最小值，则可能需要将该节点与其兄弟节点合并，或从兄弟节点借用键。
更新索引：如果正在删除的键是索引键（即位于内部节点中），则可能需要更新索引键以反映树结构中的更改。

在 B+ 树中，删除比插入更复杂，因为可能需要调整树结构以维护 B+ 树属性。但是，查找键的搜索时间仍然是对数级的，这使得 B+ 树成为索引和搜索大型数据集的高效数据结构。

C++ 程序

#include <bits/stdc++.h>

#include <iostream>
#include <random>
#include <utility>
#include <vector>

using namespace std;

class Node {
 public:
  Node(Node *parent = nullptr, bool isLeaf = false, Node *prev_ = nullptr,
       Node *next_ = nullptr)
      : parent(parent), isLeaf(isLeaf), prev(prev_), next(next_) {
    if (next_) {
      next_->prev = this;
    }

    if (prev_) {
      prev_->next = this;
    }
  }

  vector<int> keys;
  Node *parent;

  vector<Node *> children;
  vector<int> values;
  Node *next;
  Node *prev;

  bool isLeaf;

  int indexOfChild(int key) {
    for (int i = 0; i < keys.size(); i++) {
      if (key < keys[i]) {
        return i;
      }
    }
    return keys.size();
  }

  int indexOfKey(int key) {
    for (int i = 0; i < keys.size(); i++) {
      if (key == keys[i]) {
        return i;
      }
    }
    return -1;
  }

  Node *getChild(int key) { return children[indexOfChild(key)]; }

  void setChild(int key, vector<Node *> value) {
    int i = indexOfChild(key);
    keys.insert(keys.begin() + i, key);
    children.erase(children.begin() + i);
    children.insert(children.begin() + i, value.begin(), value.end());
  }

  tuple<int, Node *, Node *> splitInternal() {
    Node *left = new Node(parent, false, nullptr, nullptr);
    int mid = keys.size() / 2;

    copy(keys.begin(), keys.begin() + mid, back_inserter(left->keys));
    copy(children.begin(), children.begin() + mid + 1,
         back_inserter(left->children));

    for (Node *child : left->children) {
      child->parent = left;
    }

    int key = keys[mid];
    keys.erase(keys.begin(), keys.begin() + mid + 1);
    children.erase(children.begin(), children.begin() + mid + 1);

    return make_tuple(key, left, this);
  }

  int get(int key) {
    int index = -1;
    for (int i = 0; i < keys.size(); ++i) {
      if (keys[i] == key) {
        index = i;
        break;
      }
    }

    if (index == -1) {
      cout << "key " << key << " not found" << endl;
    }

    return values[index];
  }

  void set(int key, int value) {
    int i = indexOfChild(key);
    if (find(keys.begin(), keys.end(), key) == keys.end()) {
      keys.insert(keys.begin() + i, key);
      values.insert(values.begin() + i, value);
    } else {
      values[i - 1] = value;
    }
  }

  tuple<int, Node *, Node *> splitLeaf() {
    Node *left = new Node(parent, true, prev, this);
    int mid = keys.size() / 2;

    left->keys = vector<int>(keys.begin(), keys.begin() + mid);
    left->values = vector<int>(values.begin(), values.begin() + mid);

    keys.erase(keys.begin(), keys.begin() + mid);
    values.erase(values.begin(), values.begin() + mid);

    return make_tuple(keys[0], left, this);
  }
};

class BPlusTree {
 public:
  BPlusTree(int _maxCapacity = 4) {
    root = new Node(nullptr, true, nullptr, nullptr);
    maxCapacity = _maxCapacity > 2 ? _maxCapacity : 2;
    minCapacity = maxCapacity / 2;
    depth = 0;
  }

  Node *root;
  int maxCapacity;
  int minCapacity;
  int depth;

  Node *findLeaf(int key) {
    Node *node = root;
    while (!node->isLeaf) {
      node = node->getChild(key);
    }
    return node;
  }

  int get(int key) { return findLeaf(key)->get(key); }

  void set(int key, int value) {
    Node *leaf = findLeaf(key);
    leaf->set(key, value);
    if (leaf->keys.size() > maxCapacity) {
      insert(leaf->splitLeaf());
    }
  }

  void insert(tuple<int, Node *, Node *> result) {
    int key = std::get<0>(result);
    Node *left = std::get<1>(result);
    Node *right = std::get<2>(result);
    Node *parent = right->parent;
    if (parent == nullptr) {
      left->parent = right->parent = root =
          new Node(nullptr, false, nullptr, nullptr);
      depth += 1;
      root->keys = {key};
      root->children = {left, right};
      return;
    }
    parent->setChild(key, {left, right});
    if (parent->keys.size() > maxCapacity) {
      insert(parent->splitInternal());
    }
  }

  void removeFromLeaf(int key, Node *node) {
    int index = node->indexOfKey(key);
    if (index == -1) {
      cout << "Key " << key << " not found! Exiting ..." << endl;
      exit(0);
    }
    node->keys.erase(node->keys.begin() + index);
    node->values.erase(node->values.begin() + index);
    if (node->parent) {
      int indexInParent = node->parent->indexOfChild(key);
      if (indexInParent)
        node->parent->keys[indexInParent - 1] = node->keys.front();
    }
  }

  void removeFromInternal(int key, Node *node) {
    int index = node->indexOfKey(key);
    if (index != -1) {
      Node *leftMostLeaf = node->children[index + 1];
      while (!leftMostLeaf->isLeaf)
        leftMostLeaf = leftMostLeaf->children.front();

      node->keys[index] = leftMostLeaf->keys.front();
    }
  }

  void borrowKeyFromRightLeaf(Node *node, Node *next) {
    node->keys.push_back(next->keys.front());
    next->keys.erase(next->keys.begin());
    node->values.push_back(next->values.front());
    next->values.erase(next->values.begin());
    for (int i = 0; i < node->parent->children.size(); i++) {
      if (node->parent->children[i] == next) {
        node->parent->keys[i - 1] = next->keys.front();
        break;
      }
    }
  }

  void borrowKeyFromLeftLeaf(Node *node, Node *prev) {
    node->keys.insert(node->keys.begin(), prev->keys.back());
    prev->keys.erase(prev->keys.end() - 1);
    node->values.insert(node->values.begin(), prev->values.back());
    prev->values.erase(prev->values.end() - 1);
    for (int i = 0; i < node->parent->children.size(); i++) {
      if (node->parent->children[i] == node) {
        node->parent->keys[i - 1] = node->keys.front();
        break;
      }
    }
  }

  void mergeNodeWithRightLeaf(Node *node, Node *next) {
    node->keys.insert(node->keys.end(), next->keys.begin(), next->keys.end());
    node->values.insert(node->values.end(), next->values.begin(),
                        next->values.end());
    node->next = next->next;
    if (node->next) node->next->prev = node;
    for (int i = 0; i < next->parent->children.size(); i++) {
      if (node->parent->children[i] == next) {
        node->parent->keys.erase(node->parent->keys.begin() + i - 1);
        node->parent->children.erase(node->parent->children.begin() + i);

        break;
      }
    }
  }

  void mergeNodeWithLeftLeaf(Node *node, Node *prev) {
    prev->keys.insert(prev->keys.end(), node->keys.begin(), node->keys.end());
    prev->values.insert(prev->values.end(), node->values.begin(),
                        node->values.end());

    prev->next = node->next;
    if (prev->next) prev->next->prev = prev;

    for (int i = 0; i < node->parent->children.size(); i++) {
      if (node->parent->children[i] == node) {
        node->parent->keys.erase(node->parent->keys.begin() + i - 1);
        node->parent->children.erase(node->parent->children.begin() + i);
        break;
      }
    }
  }

  void borrowKeyFromRightInternal(int myPositionInParent, Node *node,
                                  Node *next) {
    node->keys.insert(node->keys.end(), node->parent->keys[myPositionInParent]);
    node->parent->keys[myPositionInParent] = next->keys.front();
    next->keys.erase(next->keys.begin());
    node->children.insert(node->children.end(), next->children.front());
    next->children.erase(next->children.begin());
    node->children.back()->parent = node;
  }

  void borrowKeyFromLeftInternal(int myPositionInParent, Node *node,
                                 Node *prev) {
    node->keys.insert(node->keys.begin(),
                      node->parent->keys[myPositionInParent - 1]);
    node->parent->keys[myPositionInParent - 1] = prev->keys.back();
    prev->keys.erase(prev->keys.end() - 1);
    node->children.insert(node->children.begin(), prev->children.back());
    prev->children.erase(prev->children.end() - 1);
    node->children.front()->parent = node;
  }

  void mergeNodeWithRightInternal(int myPositionInParent, Node *node,
                                  Node *next) {
    node->keys.insert(node->keys.end(), node->parent->keys[myPositionInParent]);
    node->parent->keys.erase(node->parent->keys.begin() + myPositionInParent);
    node->parent->children.erase(node->parent->children.begin() +
                                 myPositionInParent + 1);
    node->keys.insert(node->keys.end(), next->keys.begin(), next->keys.end());
    node->children.insert(node->children.end(), next->children.begin(),
                          next->children.end());
    for (Node *child : node->children) {
      child->parent = node;
    }
  }

  void mergeNodeWithLeftInternal(int myPositionInParent, Node *node,
                                 Node *prev) {
    prev->keys.insert(prev->keys.end(),
                      node->parent->keys[myPositionInParent - 1]);
    node->parent->keys.erase(node->parent->keys.begin() + myPositionInParent -
                             1);
    node->parent->children.erase(node->parent->children.begin() +
                                 myPositionInParent);
    prev->keys.insert(prev->keys.end(), node->keys.begin(), node->keys.end());
    prev->children.insert(prev->children.end(), node->children.begin(),
                          node->children.end());
    for (Node *child : prev->children) {
      child->parent = prev;
    }
  }

  void remove(int key, Node *node = nullptr) {
    if (node == nullptr) {
      node = findLeaf(key);
    }
    if (node->isLeaf) {
      removeFromLeaf(key, node);
    } else {
      removeFromInternal(key, node);
    }

    if (node->keys.size() < minCapacity) {
      if (node == root) {
        if (root->keys.empty() && !root->children.empty()) {
          root = root->children[0];
          root->parent = nullptr;
          depth -= 1;
        }
        return;
      }

      else if (node->isLeaf) {
        Node *next = node->next;
        Node *prev = node->prev;

        if (next && next->parent == node->parent &&
            next->keys.size() > minCapacity) {
          borrowKeyFromRightLeaf(node, next);
        } else if (prev && prev->parent == node->parent &&
                   prev->keys.size() > minCapacity) {
          borrowKeyFromLeftLeaf(node, prev);
        } else if (next && next->parent == node->parent &&
                   next->keys.size() <= minCapacity) {
          mergeNodeWithRightLeaf(node, next);
        } else if (prev && prev->parent == node->parent &&
                   prev->keys.size() <= minCapacity) {
          mergeNodeWithLeftLeaf(node, prev);
        }
      } else {
        int myPositionInParent = -1;

        for (int i = 0; i < node->parent->children.size(); i++) {
          if (node->parent->children[i] == node) {
            myPositionInParent = i;
            break;
          }
        }

        Node *next;
        Node *prev;

        if (node->parent->children.size() > myPositionInParent + 1) {
          next = node->parent->children[myPositionInParent + 1];
        } else {
          next = nullptr;
        }

        if (myPositionInParent) {
          prev = node->parent->children[myPositionInParent - 1];
        } else {
          prev = nullptr;
        }

        if (next && next->parent == node->parent &&
            next->keys.size() > minCapacity) {
          borrowKeyFromRightInternal(myPositionInParent, node, next);
        }

        else if (prev && prev->parent == node->parent &&
                 prev->keys.size() > minCapacity) {
          borrowKeyFromLeftInternal(myPositionInParent, node, prev);
        }

        else if (next && next->parent == node->parent &&
                 next->keys.size() <= minCapacity) {
          mergeNodeWithRightInternal(myPositionInParent, node, next);
        }

        else if (prev && prev->parent == node->parent &&
                 prev->keys.size() <= minCapacity) {
          mergeNodeWithLeftInternal(myPositionInParent, node, prev);
        }
      }
    }
    if (node->parent) {
      remove(key, node->parent);
    }
  }

  void print(Node *node = nullptr, string _prefix = "", bool _last = true) {
    if (!node) node = root;
    cout << _prefix << "? [";
    for (int i = 0; i < node->keys.size(); i++) {
      cout << node->keys[i];
      if (i != node->keys.size() - 1) {
        cout << ", ";
      }
    }
    cout << "]" << endl;

    _prefix += _last ? "   " : "?  ";

    if (!node->isLeaf) {
      for (int i = 0; i < node->children.size(); i++) {
        bool _last = (i == node->children.size() - 1);
        print(node->children[i], _prefix, _last);
      }
    }
  }
};

int main() {
  BPlusTree tree(3);
  vector<int> random_list = {5,  9,  1,  3,   4,   59,  65,  45,
                             89, 29, 68, 108, 165, 298, 219, 569,
                             37, 47, 53, 6,   43,  51,  57,  49};

  vector<int> random_list_2 =
      vector<int>(random_list.begin(), random_list.end());

  for (int r : random_list_2) {
    for (int i : random_list) {
      cout << endl << "-------------" << endl;
      cout << "Inserting " << i << endl << endl;
      cout << "-------------" << endl << endl;

      tree.set(i, i);
      tree.print();
    }

    cout << endl << "-------------------------" << endl;
    cout << "All keys are inserted ..." << endl;
    cout << "-------------------------" << endl << endl;

    tree.print();

    shuffle(random_list.begin(), random_list.end(), default_random_engine(r));
    for (int i : random_list) {
      tree.remove(i);
      cout << endl << "-------------" << endl;
      cout << "Removing " << i << endl;
      cout << "-------------" << endl << endl;
      tree.print();
    }
  }

  return 0;
}

输出

说明

此代码使用了一种称为 B+ 树的自平衡树数据结构，该结构通常用于数据库以快速存储和检索数据。它类似于二叉搜索树，但每个节点可以存储多个键并拥有两个以上的子节点。

Node 类

B+ 树中的节点由 Node 类表示。它的多个成员变量包括：

存储在节点中的键是存储在名为 keys 的整数向量中。
parent 是指向当前节点父节点的指针。
Children 是一个包含指向当前节点子节点的指针的向量。仅当当前节点不是叶子节点时才使用此项。
与节点键关联的数字存储在名为 values 的整数向量中。仅当当前节点是叶子节点时才使用此项。
"next" 和 "prev" 分别指树的下一个和上一个分支。为了方便有效的范围查询，这用于构建叶子节点的链表。（尚未实现）。
布尔值 isLeaf 表示当前节点是否为叶子节点。

Node 类有几个成员函数

Node(Node *parent = nullptr, bool isLeaf = false, Node *prev_ = nullptr, Node *next_ = nullptr) 是 Node 类的构造函数。它接受四个可选参数：指向父节点的指针，一个布尔值，指示节点是否为叶子节点，以及指向树中前一个和后一个节点的指针。如果提供了 prev 和 next 参数，它会相应地更新链表指针。
indexOfChild(int key) 返回包含指定键的子节点的索引。如果节点中不存在该键，则返回键将被添加的索引。
indexOfKey(int key) 函数返回指定键在 keys 向量中的位置。如果找不到键，则返回 -1。
getChild(int key) 的结果值是指向包含指定键的子节点的指针。
setChild(int key, vector value) 将指定的键和子节点向量放置在 keys 和 children 向量的正确位置。
splitInternal() 用于在内部节点已满时将其拆分。一半的键和子节点被转移到新节点，新节点也被赋予一个新节点。它返回一个元组，包含指向左节点的指针、指向右节点的指针以及将插入父节点的键。
get(int key) 返回与提供的键对应的键值。如果找不到键，则会打印错误消息。
set(int key, int value) 函数将指定的键和值放置在 keys 和 values 数组的正确位置。如果键已存在，则更新相关值。
当内部组件已满时，splitInternal() 用于对其进行拆分。
当叶子节点已满时，splitLeaf() 函数用于对其进行拆分。一半的键和值被转移到新创建的新节点。它返回一个元组，包含指向左节点的指针、指向右节点的指针以及将插入父节点的键。
当其中一个叶子节点变得不饱和时，merge(Node* sibling) 用于合并两个叶子节点。它更新链表指针并将兄弟节点的所有键和值转移到当前节点。

BPlusTree 类

B+ 树数据结构由 BPlusTree 类表示。它的多个成员变量包括：

root: 指向树根节点的指针。
maxCapacity: 一个整数，表示节点在必须拆分之前可以拥有的最大键数。
minCapacity: 一个整数，表示节点在被视为不饱和并可能需要与另一个节点合并或从相邻节点借用键之前可以拥有的最小键数。
depth: 一个数字，表示树的深度。

BPlusTree 类有几个成员方法。

BPlusTree(int _maxCapacity = 4) 是 BPlusTree 类的构造函数。它接受一个可选参数 _maxCapacity，该参数指定节点在需要拆分之前可以拥有的最大键数。如果未提供 _maxCapacity，则使用默认值 4。构造函数创建一个新的根节点并初始化 maxCapacity、minCapacity 和 depth 成员变量。
findLeaf(int key) 函数返回一个指向包含指定键的叶子节点的指针。它从根节点向下遍历树，直到达到叶子节点。
get(int key) 函数返回与指定键关联的数字。它使用 findLeaf 函数找到包含该键的叶子节点，然后使用 get 函数获取值。
set() 函数将指定的属性和值添加到树中。通过调用 findLeaf 方法识别键将被存储的叶子节点，然后调用叶子节点的 set 函数来插入键和值。如果叶子节点因此已满，则调用 insert 函数来拆分节点。
insert(tuple result) 函数使用插入节点拆分的后果。它需要一个元组，其中包含指向左子节点和右子节点的指针以及将插入父节点的值。为了创建新的根节点并更新根节点和深度成员变量，它首先确定父节点是否为空。如果不为空，它使用父节点的 setChild 函数将键和子节点放置在正确的位置。如果父节点已满，它通过反复调用 insert 方法来拆分父节点。
remove(int key) 函数从树中删除指定的键。它使用 findLeaf 函数找到包含该键的叶子节点，然后使用 removeFromLeaf 函数将键从该叶子节点中删除。如果叶子节点因此变得不饱和，它会确定是否需要与相邻节点合并，或者是否有具有可用键的相邻节点可以借用。如果节点是根节点并且由于移除而变为空，则根节点被更新以指向唯一的幸存子节点。
removeFromLeaf(int key, Node *node) 函数接受一个键并将其从叶子节点中删除。如果需要，它会更新父节点中的键，并从 keys 和 values 向量中删除键和相关值。
removeFromInternal(int key, Node *node) 函数从指定的内部节点中删除指定的键。如果键存在于 keys 向量中，则使用右子节点中的最小键来替换它。如果内部节点因此变得不饱和，它会确定是否可以从具有可用键的相邻节点借用键，或者是否需要与相邻节点合并。
borrowKeyFromRightLeaf(Node *node, Node *next) 函数从叶子节点的右邻居那里获取一个键。它从右邻居那里删除键和值，并将该邻居的第一个键和值添加到提供的节点中。如有必要，它还会更新右邻居父节点中的键。
borrowKeyFromLeftLeaf(Node *node, Node *prev) 函数从叶子节点的左邻居那里获取一个键。它从左邻居那里删除键和值，并将左邻居的最后一个键和值添加到提供的节点中。如有必要，它还会更新提供节点父节点中的键。
mergeNodeWithRightLeaf(Node *node) 函数将提供的节点与其右邻居合并。它更新链表指针并将右邻居的键和值附加到提供的节点中。然后删除相应的邻居节点。
mergeNodeWithLeftLeaf(Node *node) 函数将提供的节点与其左邻居合并。链表指针被更新，并将左邻居的键和值插入到提供的节点中的键和值向量的开头。然后，删除左邻居节点。
borrowKeyFromRightInternal(Node *node) 函数从内部节点的右邻居那里获取一个键。它从右邻居那里删除键和子节点，并将右邻居的第一个键和子节点放入提供的节点中。如果需要，它还会更新右邻居父节点中的键。
borrowKeyFromLeftInternal(Node *node) 函数从内部节点的左邻居那里获取一个键。

左邻居的最后一个键和子节点被删除，并插入到提供的节点中。

如果需要，它还会更新提供节点父节点中的键。

mergeNodeWithRightInternal(Node *node) 函数将内部节点与右邻居合并。如果需要，它会修改父节点中的键，并将相应邻居的键和子节点附加到提供的节点中。

然后删除相应的邻居节点。

mergeNodeWithLeftInternal(Node *node) 函数将内部节点与左邻居合并。它将左邻居的键和子节点插入到键和子节点向量的开头。

B+ 树的优点

与具有相同层数的 B 树相比，B+ 树可以在其内部节点中存储更多条目。这强调了每个特定键的搜索时间得到了多少改进。由于其较低的层数和 Pnext 指针，B+ 树在访问磁盘记录方面特别快速有效。
B+ 树允许数据进行顺序访问和直接访问。
获取记录需要同等数量的磁盘访问。
由于 B+ 树中存在重复的搜索键，因此不可能再次存储搜索键。

B+ 树的缺点

以顺序方式访问键的困难是 B 树的主要缺点。B+ 树仍然具有快速的随机访问。

B+ 树的应用

多级索引
更快的树操作（插入、删除、搜索）
索引数据库

B 树与 B+ 树

以下是 B 树和 B+ 树之间的一些区别：

数据和搜索键存储在 B 树的内部节点或叶子节点中。但是，数据仅存储在 B+ 树的叶子节点中。
由于所有数据都位于 B+ 树的叶子节点中，因此查找任何数据都非常简单。在 B 树的叶子节点中找不到数据。
数据可以位于 B 树的内部节点或叶子节点中。内部节点删除非常困难。数据仅存在于 B+ 树的叶子节点中。叶子节点删除相对简单，因为可以直接删除。
B 树的插入比 B+ 树更复杂。
B+ 树存储冗余搜索键，而 B 树没有冗余值。
在 B+ 树中，叶子节点数据按顺序链接列表排序，但在 B 树中，叶子节点不能使用链接列表存储。许多数据库系统的实现偏爱 B+ 树的结构简洁性。

基本区别在于它们如何利用内部存储。

概述

B+ 树是一种非线性存储结构，用于存储具有“一对多”关系的集合数据元素，通常用于数据库和操作系统文件系统。

非叶子节点不存储数据，只存储索引（冗余），并且可以放置更多索引。
叶子节点包含所有索引字段。
叶子节点通过指针链接以提高区间访问性能；

为什么选择 B+ 树？

由于 MySQL 通常将数据存储在磁盘上，读取数据会产生磁盘 IO 消耗。B+ 树的非叶子节点不存储数据。通常，节点的大小设置为磁盘页大小，因此B+ 树的每个节点可以放置更多键，B+ 树的高度更低，从而减少磁盘 IO 消耗。
B+ 树叶子节点形成一个链接列表，用于范围搜索和排序。

MySQL 使用 B+ 树作为索引。

由于 MySQL 通常将数据存储在磁盘上，读取数据会产生磁盘 IO 消耗。B+ 树的非叶子节点不存储数据，而 B 树的非叶子节点会存储数据。通常，节点的大小会设置为磁盘页大小，以便 B+ 树的每个节点可以容纳更多的键，而 B 树的键较少。因此，B 树的高度将高于 B+ 树，这将导致更多的磁盘 IO 消耗。
B+ 树叶子节点形成一个链接列表，用于范围搜索和排序。B 树进行范围搜索和排序需要递归遍历树。

B+ 树时间复杂度

最佳情况时间复杂度

B+ 树中的搜索操作与 B 树中的删除操作具有相同的最佳情况时间复杂度。因此，B+ 树删除的最佳情况时间复杂度为 O(logn)

平均情况时间复杂度

B+ 树的平均情况时间复杂度为 O(logn)。B+ 树的删除技术与搜索过程所需时间相同。因此，搜索和删除都需要相同的时间。

最坏情况时间复杂度

B+ 树的最坏情况时间复杂度为 O(logn)。

B+ 树空间复杂度

在 B+ 树中，最坏情况空间复杂度与平均空间复杂度相同。

平均和最佳空间复杂度为 O(n)

下一个主题B+ 树插入

B+ 树删除

B+ 树特性

B+ 树删除过程

B+ 树删除

C++ 程序

BPlusTree 类

B+ 树的优点

B+ 树的缺点

B+ 树的应用

B 树与 B+ 树

概述

为什么选择 B+ 树？

MySQL 使用 B+ 树作为索引。

B+ 树时间复杂度

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

B+ 树删除

B+ 树特性

B+ 树删除过程

B+ 树删除

C++ 程序

BPlusTree 类

B+ 树的优点

B+ 树的缺点

B+ 树的应用

B 树与 B+ 树

概述

为什么选择 B+ 树？

MySQL 使用 B+ 树作为索引。

B+ 树时间复杂度

相关帖子

检查两个数组是否相等

Python 中数组轮换的块交换算法

检查表达式中的括号是否平衡 (格式正确性)

后缀表达式到前缀表达式的转换

距离之和

线段树 (带节点更新的范围最大查询)

查找两个 BST 中和等于给定值 x 的对

对近乎排序的数组进行排序

使用 Python 对矩阵数据结构执行不同操作

排序算法的应用、优点和缺点

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器