MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

C++ 实现B+树深入讲解

2021-03-317.5k 阅读

B+树概述

B+树是一种多路平衡查找树，它在数据库索引等领域有着广泛的应用。与B树不同，B+树所有的数据都存储在叶子节点，内部节点仅用于索引，这使得它在范围查询时具有更高的效率。B+树的每个节点可以有多个子节点，通常节点的子节点数量在某个范围内，这个范围取决于具体的实现和应用场景。

B+树的结构特点

  1. 节点类型
    • 叶子节点：存储实际的数据记录，并且叶子节点之间通过链表相连，这一特性使得范围查询变得非常高效。例如，在一个按学号索引的B+树中，叶子节点存储每个学生的详细信息（学号、姓名、成绩等），通过链表可以方便地遍历所有学号在某个范围内的学生记录。
    • 内部节点：主要用于索引，其包含指向子节点的指针以及用于划分范围的键值。内部节点的键值并不存储完整的数据，只是起到引导查询方向的作用。比如在一个存储文件路径索引的B+树中，内部节点的键值可能是路径中的目录名，通过这些键值可以快速定位到包含具体文件信息的叶子节点。
  2. 平衡特性 B+树始终保持平衡，即从根节点到每个叶子节点的路径长度相同。这一特性保证了查询操作的时间复杂度稳定，无论数据量如何增长，查询效率都能维持在一个较好的水平。例如，对于一个有1000个数据记录的B+树和一个有1000000个数据记录的B+树，只要它们的高度相近，查询时间复杂度就基本相同。

C++ 实现B+树的基本思路

  1. 定义节点结构 在C++中，我们首先要定义B+树的节点结构。对于叶子节点和内部节点，可以分别定义结构体或类。
// 定义叶子节点
template <typename Key, typename Value>
struct LeafNode {
    Key keys[ORDER];
    Value values[ORDER];
    LeafNode* next;
    int count;
    LeafNode() : next(nullptr), count(0) {}
};

// 定义内部节点
template <typename Key>
struct InternalNode {
    Key keys[ORDER];
    InternalNode* children[ORDER + 1];
    int count;
    InternalNode() : count(0) {}
};

这里的ORDER是一个常量，表示B+树节点的最大子节点数。叶子节点存储键值对(Key, Value)，并且有一个指针next指向下一个叶子节点，形成链表结构。内部节点存储键值Key以及指向子节点的指针children。 2. 插入操作 插入操作是B+树实现的关键部分。当插入一个新的键值对时，首先要找到合适的叶子节点。如果叶子节点未满，则直接插入；如果叶子节点已满，则需要进行节点分裂。

template <typename Key, typename Value>
void BPlusTree<Key, Value>::insert(const Key& key, const Value& value) {
    if (root == nullptr) {
        root = new LeafNode<Key, Value>();
        root->keys[0] = key;
        root->values[0] = value;
        root->count = 1;
        return;
    }
    LeafNode<Key, Value>* leaf = findLeaf(key);
    if (leaf->count < ORDER) {
        insertIntoLeaf(leaf, key, value);
    } else {
        LeafNode<Key, Value>* newLeaf = new LeafNode<Key, Value>();
        splitLeaf(leaf, newLeaf);
        if (key < leaf->keys[0]) {
            insertIntoLeaf(leaf, key, value);
        } else {
            insertIntoLeaf(newLeaf, key, value);
        }
        insertIntoParent(leaf, newLeaf, leaf->keys[0]);
    }
}

上述代码中，findLeaf函数用于找到合适的叶子节点，insertIntoLeaf函数将键值对插入到叶子节点，splitLeaf函数用于分裂已满的叶子节点，insertIntoParent函数将新分裂的节点插入到父节点。 3. 查找操作 查找操作相对简单，从根节点开始，根据键值在内部节点中选择合适的子节点，直到找到叶子节点，然后在叶子节点中查找键值对应的记录。

template <typename Key, typename Value>
Value BPlusTree<Key, Value>::search(const Key& key) const {
    if (root == nullptr) {
        throw std::runtime_error("Tree is empty");
    }
    const LeafNode<Key, Value>* leaf = findLeaf(key);
    for (int i = 0; i < leaf->count; ++i) {
        if (leaf->keys[i] == key) {
            return leaf->values[i];
        }
    }
    throw std::runtime_error("Key not found");
}

这里的findLeaf函数在查找过程中起到关键作用，它沿着树的路径一直找到包含目标键值的叶子节点。

B+树插入操作的详细实现

  1. 找到合适的叶子节点
template <typename Key, typename Value>
LeafNode<Key, Value>* BPlusTree<Key, Value>::findLeaf(const Key& key) {
    Node* current = root;
    while (!isLeaf(current)) {
        InternalNode<Key>* internal = static_cast<InternalNode<Key>*>(current);
        int i = 0;
        while (i < internal->count && key > internal->keys[i]) {
            ++i;
        }
        current = internal->children[i];
    }
    return static_cast<LeafNode<Key, Value>*>(current);
}

该函数从根节点开始，在内部节点中根据键值选择合适的子节点，直到找到叶子节点。在内部节点中，通过比较键值key与节点中的键值internal->keys[i]来决定下一步走向哪个子节点。 2. 插入到叶子节点

template <typename Key, typename Value>
void BPlusTree<Key, Value>::insertIntoLeaf(LeafNode<Key, Value>* leaf, const Key& key, const Value& value) {
    int i = leaf->count - 1;
    while (i >= 0 && key < leaf->keys[i]) {
        leaf->keys[i + 1] = leaf->keys[i];
        leaf->values[i + 1] = leaf->values[i];
        --i;
    }
    leaf->keys[i + 1] = key;
    leaf->values[i + 1] = value;
    leaf->count++;
}

此函数将键值对插入到叶子节点中。首先，从叶子节点的最后一个位置开始，将大于插入键值的元素向后移动，然后将新的键值对插入到合适的位置。 3. 叶子节点分裂

template <typename Key, typename Value>
void BPlusTree<Key, Value>::splitLeaf(LeafNode<Key, Value>* leaf, LeafNode<Key, Value>* newLeaf) {
    int mid = ORDER / 2;
    newLeaf->next = leaf->next;
    leaf->next = newLeaf;
    for (int i = mid; i < ORDER; ++i) {
        newLeaf->keys[i - mid] = leaf->keys[i];
        newLeaf->values[i - mid] = leaf->values[i];
        newLeaf->count++;
        leaf->count--;
    }
}

当叶子节点已满时，需要进行分裂。这里将叶子节点的后半部分数据移动到新的叶子节点中，并调整叶子节点的链表关系。 4. 插入到父节点

template <typename Key, typename Value>
void BPlusTree<Key, Value>::insertIntoParent(Node* leftChild, Node* rightChild, const Key& key) {
    if (leftChild == root) {
        InternalNode<Key>* newRoot = new InternalNode<Key>();
        newRoot->keys[0] = key;
        newRoot->children[0] = leftChild;
        newRoot->children[1] = rightChild;
        newRoot->count = 1;
        root = newRoot;
        return;
    }
    InternalNode<Key>* parent = findParent(leftChild);
    int i = parent->count;
    while (i > 0 && key < parent->keys[i - 1]) {
        parent->keys[i] = parent->keys[i - 1];
        parent->children[i + 1] = parent->children[i];
        --i;
    }
    parent->keys[i] = key;
    parent->children[i + 1] = rightChild;
    parent->count++;
    if (parent->count == ORDER) {
        InternalNode<Key>* newInternal = new InternalNode<Key>();
        splitInternal(parent, newInternal);
        insertIntoParent(parent, newInternal, newInternal->keys[0]);
    }
}

该函数将新分裂的节点插入到父节点中。如果父节点是根节点，则创建一个新的根节点。否则，在父节点中找到合适的位置插入新节点。如果父节点已满，还需要对父节点进行分裂。

B+树查找操作的详细实现

  1. 从根节点到叶子节点的遍历
template <typename Key, typename Value>
const LeafNode<Key, Value>* BPlusTree<Key, Value>::findLeaf(const Key& key) const {
    const Node* current = root;
    while (!isLeaf(current)) {
        const InternalNode<Key>* internal = static_cast<const InternalNode<Key>*>(current);
        int i = 0;
        while (i < internal->count && key > internal->keys[i]) {
            ++i;
        }
        current = internal->children[i];
    }
    return static_cast<const LeafNode<Key, Value>*>(current);
}

这个函数与插入操作中的findLeaf类似，从根节点开始，根据键值在内部节点中选择合适的子节点，逐步向下直到找到叶子节点。不同之处在于这里是常量版本，用于查找操作。 2. 在叶子节点中查找键值

template <typename Key, typename Value>
Value BPlusTree<Key, Value>::search(const Key& key) const {
    if (root == nullptr) {
        throw std::runtime_error("Tree is empty");
    }
    const LeafNode<Key, Value>* leaf = findLeaf(key);
    for (int i = 0; i < leaf->count; ++i) {
        if (leaf->keys[i] == key) {
            return leaf->values[i];
        }
    }
    throw std::runtime_error("Key not found");
}

在找到叶子节点后，遍历叶子节点中的键值对，查找与目标键值匹配的记录。如果找到则返回对应的值，否则抛出异常表示键值未找到。

B+树的删除操作

  1. 删除操作的基本思路 删除操作比插入操作更为复杂。首先要找到包含要删除键值的叶子节点，然后从叶子节点中删除该键值对。如果删除后叶子节点中的键值对数量低于下限（通常为ORDER / 2），则需要进行节点合并或调整操作。
  2. 找到包含要删除键值的叶子节点
template <typename Key, typename Value>
LeafNode<Key, Value>* BPlusTree<Key, Value>::findLeafForDelete(const Key& key) {
    Node* current = root;
    while (!isLeaf(current)) {
        InternalNode<Key>* internal = static_cast<InternalNode<Key>*>(current);
        int i = 0;
        while (i < internal->count && key > internal->keys[i]) {
            ++i;
        }
        current = internal->children[i];
    }
    return static_cast<LeafNode<Key, Value>*>(current);
}

这个函数与插入和查找操作中的findLeaf类似，用于找到包含要删除键值的叶子节点。 3. 从叶子节点中删除键值对

template <typename Key, typename Value>
void BPlusTree<Key, Value>::deleteFromLeaf(LeafNode<Key, Value>* leaf, const Key& key) {
    int i = 0;
    while (i < leaf->count && leaf->keys[i] != key) {
        ++i;
    }
    if (i == leaf->count) {
        throw std::runtime_error("Key not found");
    }
    for (; i < leaf->count - 1; ++i) {
        leaf->keys[i] = leaf->keys[i + 1];
        leaf->values[i] = leaf->values[i + 1];
    }
    leaf->count--;
}

此函数在叶子节点中找到要删除的键值对，并将其从叶子节点中移除。如果未找到键值对，则抛出异常。 4. 处理叶子节点删除后的调整

template <typename Key, typename Value>
void BPlusTree<Key, Value>::adjustAfterDelete(LeafNode<Key, Value>* leaf) {
    if (leaf->count >= ORDER / 2) {
        return;
    }
    LeafNode<Key, Value>* sibling = getSibling(leaf);
    if (sibling->count > ORDER / 2) {
        redistribute(leaf, sibling);
    } else {
        merge(leaf, sibling);
    }
}

当叶子节点删除键值对后，如果其键值对数量低于下限，则根据情况进行重新分配（redistribute）或合并（merge）操作。getSibling函数用于获取叶子节点的兄弟节点，redistribute函数用于从兄弟节点借一个键值对过来，merge函数用于将叶子节点与其兄弟节点合并。

B+树在实际应用中的优势与场景

  1. 优势
    • 范围查询高效：由于叶子节点通过链表相连，在进行范围查询时，只需要找到范围起始的叶子节点，然后沿着链表遍历即可。例如，在数据库中查询年龄在某个区间内的用户记录，B+树可以快速定位到起始记录，然后高效地遍历后续符合条件的记录。
    • 平衡结构保证稳定性能：B+树的平衡特性使得无论数据量如何变化，查询、插入和删除操作的时间复杂度都能保持在O(log n)级别，其中n是树中节点的数量。这在数据量较大且动态变化的场景下非常重要，如大型数据库系统。
  2. 应用场景
    • 数据库索引：大多数关系型数据库都使用B+树来实现索引结构。例如，MySQL的InnoDB存储引擎默认使用B+树索引。通过B+树索引，数据库可以快速定位到满足查询条件的数据记录，大大提高查询效率。
    • 文件系统：在文件系统中，B+树可以用于索引文件路径。通过将文件路径的各个部分作为键值存储在B+树中，可以快速定位到特定文件或目录，提高文件系统的查找和管理效率。

总结B+树的C++实现要点

  1. 节点结构设计：合理设计叶子节点和内部节点的结构，确保能够有效地存储数据和索引信息。叶子节点存储实际数据并通过链表相连，内部节点用于引导查询方向。
  2. 插入、查找和删除操作：插入操作需要考虑节点分裂，查找操作要高效地从根节点定位到叶子节点并查找键值，删除操作则要处理节点合并和调整等复杂情况。每个操作都要保证B+树的平衡特性。
  3. 应用场景适配：理解B+树在不同场景下的优势，如数据库索引和文件系统等，以便在实际项目中正确地应用B+树来提高系统性能。

通过以上对B+树的深入讲解以及C++实现的详细介绍，希望读者能够对B+树有更全面的理解，并能够在实际开发中灵活运用B+树解决相关问题。在实际应用中，还可以根据具体需求对B+树的实现进行优化，如调整节点大小、改进内存管理等，以进一步提高系统的性能。