面试题：C++ 优化 B+ 树查询性能的策略与实现

影响 B+ 树查询性能的因素

节点扇出（Fan - out）：节点中能够容纳的子节点或键值对数量。扇出越大，树的高度越低，查询时需要遍历的节点数越少，但过大的扇出可能导致内存碎片和管理复杂。
树的高度：高度直接决定了查询路径长度，查询一个键值通常需要遍历从根节点到叶节点的一条路径，树越高，查询越慢。
节点分裂与合并：插入和删除操作可能导致节点分裂与合并，这会影响树的结构，频繁的分裂与合并会降低查询性能。
缓存命中率：如果 B+ 树节点能够较好地被缓存，查询时可直接从缓存获取数据，减少磁盘 I/O（若数据存储在磁盘），提高查询性能。

优化策略

优化节点结构
- 增加节点扇出：合理调整节点中键值对和子节点指针的存储方式，以容纳更多元素。例如，使用更紧凑的数据结构存储键值对。
- 减少内部节点冗余：内部节点仅存储用于索引的键值，避免不必要的数据冗余，节省空间，进而提高扇出。
调整算法
- 优化插入和删除算法：减少节点分裂和合并的频率。例如，在插入时采用“预分裂”策略，提前判断是否可能导致节点分裂，若可能则提前调整节点结构。删除时采用“延迟合并”策略，当节点删除元素后空间利用率过低，不立即合并，而是等待后续操作看是否有机会重新利用该空间。
- 缓存优化：采用缓存机制，将常用节点缓存在内存中。可以使用 LRU（最近最少使用）缓存策略，当缓存满时，淘汰最近最少使用的节点。

C++ 代码修改示例

优化节点结构

// 假设原来的键值对结构
struct KeyValuePair {
    Key key;
    Value value;
};
// 优化为紧凑结构，若 Value 较大，可只存指针
struct CompactKeyValuePair {
    Key key;
    Value* valuePtr;
};

// 假设原来的节点结构
template <typename Key, typename Value>
struct BPlusTreeNode {
    bool isLeaf;
    int numKeys;
    Key keys[MaxKeys];
    Value values[MaxKeys];
    BPlusTreeNode* children[MaxKeys + 1];
};

// 优化后的节点结构
template <typename Key, typename Value>
struct OptimizedBPlusTreeNode {
    bool isLeaf;
    int numKeys;
    CompactKeyValuePair keyValuePairs[MaxKeys];
    OptimizedBPlusTreeNode* children[MaxKeys + 1];
};

优化插入算法（预分裂示例）

template <typename Key, typename Value>
void OptimizedBPlusTree<Key, Value>::insert(const Key& key, const Value& value) {
    if (root == nullptr) {
        root = new OptimizedBPlusTreeNode<Key, Value>();
        root->isLeaf = true;
        root->keyValuePairs[0].key = key;
        root->keyValuePairs[0].valuePtr = new Value(value);
        root->numKeys = 1;
        return;
    }
    OptimizedBPlusTreeNode<Key, Value>* node = root;
    OptimizedBPlusTreeNode<Key, Value>* parent = nullptr;
    while (!node->isLeaf) {
        int i = 0;
        while (i < node->numKeys && key > node->keyValuePairs[i].key) {
            i++;
        }
        parent = node;
        node = node->children[i];
    }
    // 预分裂
    if (node->numKeys == MaxKeys) {
        OptimizedBPlusTreeNode<Key, Value>* newNode = new OptimizedBPlusTreeNode<Key, Value>();
        newNode->isLeaf = true;
        int mid = MaxKeys / 2;
        newNode->numKeys = MaxKeys - mid;
        for (int i = mid; i < MaxKeys; i++) {
            newNode->keyValuePairs[i - mid] = node->keyValuePairs[i];
        }
        node->numKeys = mid;
        if (parent == nullptr) {
            OptimizedBPlusTreeNode<Key, Value>* newRoot = new OptimizedBPlusTreeNode<Key, Value>();
            newRoot->isLeaf = false;
            newRoot->keyValuePairs[0].key = newNode->keyValuePairs[0].key;
            newRoot->keyValuePairs[0].valuePtr = nullptr;
            newRoot->children[0] = node;
            newRoot->children[1] = newNode;
            newRoot->numKeys = 1;
            root = newRoot;
        } else {
            int i = 0;
            while (i < parent->numKeys && key > parent->keyValuePairs[i].key) {
                i++;
            }
            for (int j = parent->numKeys; j > i; j--) {
                parent->children[j + 1] = parent->children[j];
            }
            parent->children[i + 1] = newNode;
            for (int j = parent->numKeys - 1; j >= i; j--) {
                parent->keyValuePairs[j + 1] = parent->keyValuePairs[j];
            }
            parent->keyValuePairs[i].key = newNode->keyValuePairs[0].key;
            parent->keyValuePairs[i].valuePtr = nullptr;
            parent->numKeys++;
        }
    }
    int i = 0;
    while (i < node->numKeys && key > node->keyValuePairs[i].key) {
        i++;
    }
    for (int j = node->numKeys; j > i; j--) {
        node->keyValuePairs[j] = node->keyValuePairs[j - 1];
    }
    node->keyValuePairs[i].key = key;
    node->keyValuePairs[i].valuePtr = new Value(value);
    node->numKeys++;
}

缓存优化（LRU 缓存简单示例）

#include <list>
#include <unordered_map>

template <typename Key, typename Node>
class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity) {}

    Node* get(const Key& key) {
        auto it = cache.find(key);
        if (it == cache.end()) {
            return nullptr;
        }
        cacheList.splice(cacheList.begin(), cacheList, it->second);
        return it->second->second;
    }

    void put(const Key& key, Node* node) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            cacheList.splice(cacheList.begin(), cacheList, it->second);
            it->second->second = node;
            return;
        }
        cacheList.push_front({key, node});
        cache[key] = cacheList.begin();
        if (cache.size() > capacity) {
            Key lruKey = cacheList.back().first;
            cache.erase(lruKey);
            cacheList.pop_back();
        }
    }

private:
    std::list<std::pair<Key, Node*>> cacheList;
    std::unordered_map<Key, std::list<std::pair<Key, Node*>>::iterator> cache;
    int capacity;
};

// 在 B+ 树类中使用 LRU 缓存
template <typename Key, typename Value>
class OptimizedBPlusTree {
public:
    OptimizedBPlusTree() : root(nullptr), cache(10) {} // 假设缓存容量为10
    //...其他成员函数
    Value* search(const Key& key) {
        OptimizedBPlusTreeNode<Key, Value>* node = cache.get(key);
        if (node != nullptr) {
            // 从缓存中找到节点，直接查找值
            for (int i = 0; i < node->numKeys; i++) {
                if (node->keyValuePairs[i].key == key) {
                    return node->keyValuePairs[i].valuePtr;
                }
            }
        } else {
            // 未命中缓存，正常查找
            OptimizedBPlusTreeNode<Key, Value>* current = root;
            while (!current->isLeaf) {
                int i = 0;
                while (i < current->numKeys && key > current->keyValuePairs[i].key) {
                    i++;
                }
                current = current->children[i];
            }
            for (int i = 0; i < current->numKeys; i++) {
                if (current->keyValuePairs[i].key == key) {
                    cache.put(key, current);
                    return current->keyValuePairs[i].valuePtr;
                }
            }
        }
        return nullptr;
    }

private:
    OptimizedBPlusTreeNode<Key, Value>* root;
    LRUCache<Key, OptimizedBPlusTreeNode<Key, Value>*> cache;
};

星途面试题库

面试题：C++ 优化 B+ 树查询性能的策略与实现

知识考点

面试题答案

影响 B+ 树查询性能的因素

优化策略

C++ 代码修改示例