一、B 树的定义与性质

1. 每个节点最多有 M-1 个关键字（key)，M 个子树指针

2. 每个非根节点至少有 ceil(M/2) - 1 个关键字(为了保证了树的紧凑性和平衡性，防止树退化成链表)

3. 所有叶子节点处于同一层

4. 关键字在节点中按递增排列，子树区间有序

5. 插入和删除后必须保持平衡（通过分裂或合并）

代码实现（以3阶b树为例）

b树结构

const int M = 3;
template <typename T>
class BTree;


template <typename T>
class BTreeNode{
public:
    friend BTree<T>;
    BTreeNode(bool leaf) : isLeaf_(leaf){}

    ~BTreeNode(){
        for (auto &child : children_)
            delete child;
    }
    //  插入模块
    void insertNonFull(const T &key);
    void splitChild(int idx, BTreeNode* fullChild);

    //删除模块
    void remove(const T& key);
    void removeFromLeaf(int idx);
    void removeFromNonLeaf(int idx);
    T getPred(int idx);
    T getSucc(int idx);
    void fill(int idx);
    void borrowFromPrev(int idx);
    void borrowFromNext(int idx);
    void merge(int idx);
    int findKey(const T& key);


private:
    std::vector<T> keys_;
    std::vector<BTreeNode*> children_;
    bool isLeaf_;
};

template <typename T>
class BTree{
public:
    BTree(): root_(nullptr){}    
    ~BTree(){ delete root_; }     

    void insert(const T& key);
    void remove(const T& key);


private:
    BTreeNode<T> root_;

};

插入节点 

在插入节点都是先判满（若满就分裂）在插入

在BTree维护insert插入入口函数，处理树空或根节点已满的情况

insertNonFull在未满节点中插入 key，递归查找目标位置并且处理子节点已满的情况

splitChild将满子节点 y 分裂成两个节点，将中间 key 上移到父节点

template <typename T>
void BTree<T>::insert(const T& key){
    if(root_ == nullptr){
        root_ = new BTreeNode<T>(true);
        root_.keys_.push_back(key);
        return;
    }
    if(root_.keys_.size() == M - 1){// 不满足性质一，需要分裂
        //s作为新的根节点
        BTreeNode<T> *s = (BTreeNode<T> *)new BTreeNode<T>(false);

        s->children_.push_back(root_);
        s->splitChild(0, root_);

        //寻找插入位置
        int i = 0;
        while (i < s->keys.size() && key > s->keys[i])
            i++;
        s->children[i]->insertNonFull(key);
        
        root_ = s;
    }else{
        root_.insertNonFull(key);
    }
}

template <typename T>
void BTreeNode<T>::insertNonFull(const T &key){

    int i = keys_.size() - 1;

    if(isLeaf_){
        keys_.push_back(0);//站位
        while(i >= 0 && keys_[i] > key){
            keys_[i + 1] = keys_[i];
            --i;
        }
        keys_[i + 1] = key;
    }else{

        while(i >= 0 && key < keys_[i]) --i;
        ++i;

        if(children_[i]->keys_.size() == M - 1){
            splitChild(i, children_[i]);
            if(key > keys_[i]){
                ++i;
            }
        }
        children_[i]->insertNonFull(key);
    }

}
template<typename T>
void BTreeNode<T>::splitChild(int i, BTreeNode* y){
    //z作为y的分裂节点
    auto z = new BTreeNode<T>(y->isLeaf_);
    int mid = M / 2;
    for(int j = mid + 1; j < M - 1; ++j){
        z->keys_.push_back(y->keys_[j]);
    }
    if(!y->isLeaf_){
        for(int j = mid + 1; j < M; ++j){
            z->children_.push_back(y->children_[j]);
        }
    }
    // 更新y节点
    y->keys_.resize(mid);
    if(!y->isLeaf_){
        y->children_.resize(mid + 1);
    }
    // 将中间 key(y->keys_[mid]) 插入当前节点（父节点）keys[i] (keys_.begin() + i)
    keys_.insert(keys_.begin() + i, y->keys_[mid]);
    //把z也插入到当前节点(父节点的)children中
    children_.insert(children_.begin() + i + 1, z);
}

删除节点

分为能否在本层找到要删除的节点（若不能在本层找到就会递归去子树里找然后通过对子树的判断进行处理）

首先是能在本层找到删除的节点

case 1.1

case 1.2.1 右子树满足ceil(M/2) - 1 的话先通过getPred找到左子树的最右下角的key然后进行将其与要删除的key替换，然后删除要被替换的key

case 1.2.2，左子树满足ceil(M/2) - 1 的话先通过getSucc找到左子树的最左下角的key然后进行将其与要删除的key替换，然后删除要被替换的key

case1.2.3两子树都不够的话进行merge

还有就是不在本层的情况了，当 子节点太小（关键字少于 ⌈M/2⌉ - 1），从子节点借或者合并

case 2.1左兄弟足够borrowFromPrev

case 2.2右兄弟足够borrowFromNext

case3.3都不够merge

template<typename T>
void BTreeNode<T>::remove(const T& key) {
    int idx = findKey(key);
    
    if(idx < keys_.size() && keys_[idx] == key){//case 1: key在当前节点
        if(isLeaf_){                        //case 1.1: 当前节点是叶子节点直接删
            removeFromLeaf(idx);
        }else{                              //case 1.2: 当前节点是非叶子节点用前驱/后继替代
            removeFromNonLeaf(idx);
        }
    }else{//case 2: key不在当前节点
        if(isLeaf_) return; //  找不到

        //判断是否是最后一个子节点
        bool flag = (idx == keys_.size());

        //若子节点太小（关键字少于 ⌈M/2⌉ - 1），从子节点兄弟借或者合并
        if(children_[idx]->keys_.size() < (M + 1) / 2 - 1){
            fill(idx);
        }
        // 如果合并了，可能要递归到左边兄弟？？？？？？？？？？？？？？？？？？
        if(flag && idx > keys_.size()) {
            children_[idx - 1]->remove(key);
        }else{
            children_[idx]->remove(key);
        }
    
    }
}
template<typename T>
int BTreeNode<T>::findKey(const T& key) {
    int idx = 0;
    while (idx < keys_.size() && keys_[idx] < key)
        idx++;
    return idx;
}

template<typename T>
void BTreeNode<T>::removeFromLeaf(int idx){
    keys_.erase(keys_.begin() + idx);
}
//左子树最右下角的 key
template<typename T>
T BTreeNode<T>::getPred(int idx){
    BTreeNode<T> *cur = children_[idx];
    while(!cur->isLeaf_){
        cur = cur->children_.back();
    }
    return cur->keys_.back();
}

//右子树最左下角的 key
template<typename T>
T BTreeNode<T>::getSucc(int idx) {
    BTreeNode* cur = children_[idx + 1];
    while (!cur->isLeaf_)
        cur = cur->children_.front();
    return cur->keys.front();
}
template<typename T>
void BTreeNode<T>::merge(int idx) {
    auto left = children_[idx];
    auto right = children_[idx + 1];
    //把父节点的 key[idx] 插入 left，将right的所有key和孩子并入left
    left->keys_.push_back(keys_[idx]);
    left->keys.insert(left->keys_end(), right->keys_.begin(), right->keys.end());
    if(!left->isLeaf_){
        left->children_.insert(left->children_.end(), right->children_begin(), right->children_end());
    }
    keys_.erase(keys_.begin() + idx);
    children_.erase(children_.begin() + idx + 1);
    delete right;
}

template<typename T>
void BTreeNode<T>::removeFromNonLeaf(int idx){
    T k = keys_[idx];
    if(children_[idx]->keys_.size() >= (M + 1) / 2){//case1.2.1左子树足够
        T pred = getPred(idx);
        keys_[idx] = pred;
        children_[idx]->remove(pred);
    }else if(children_[idx + 1]->keys_.size() >= (M + 1) / 2){//case1.2.2右子树足够
        T succ = getSucc(idx);
        keys_[idx] = succ;
        children_[idx + 1]->remove(succ);
    }else{//case1.2.3两子树都不够，合并
        merge(idx);
        children_[idx]->remove(k);
    }
}
//从左兄弟借一个 key
template<typename T>
void BTreeNode<T>::borrowFromPrev(int idx) {
    auto child = children_[idx];
    auto sibling = children_[idx - 1];

    child->keys_.insert(child->keys_.begin(), keys_[idx - 1]); // 父 key 下移
    if (!child->isLeaf_)
        child->children_.insert(child->children_.begin(), sibling->children_.back()); // 移动孩子指针

    keys_[idx - 1] = sibling->keys_.back(); // 兄弟 key 上移到父
    sibling->keys_.pop_back();
    if (!sibling->isLeaf_)
        sibling->children_.pop_back();
}
template<typename T>
void BTreeNode<T>::borrowFromNext(int idx) {
    auto child = children_[idx];
    auto sibling = children_[idx + 1];

    child->keys.push_back(keys_[idx]); // 父 key 下移
    if (!child->isLeaf)
        child->children_.push_back(sibling->children_.front()); // 移动孩子指针

    keys_[idx] = sibling->keys_.front(); // 兄弟 key 上移到父
    sibling->keys_.erase(sibling->keys_.begin());
    if (!sibling->isLeaf_)
        sibling->children_.erase(sibling->children_.begin());
}


//保证 children[idx] 至少有 ⌈M/2⌉ - 1 个 key。
template<typename T>
void BTreeNode<T>::fill(int idx) {
    if (idx > 0 && children_[idx - 1]->keys.size() > (M + 1) / 2 - 1)
        borrowFromPrev(idx); // 从左兄弟借
    else if (idx < keys_.size() && children_[idx + 1]->keys.size() > (M + 1) / 2 - 1)
        borrowFromNext(idx); // 从右兄弟借
    else {
        // 两边都不够，只能合并
        if (idx < keys_.size())
            merge(idx);
        else
            merge(idx - 1);
    }
}

更多资料：https://github.com/0voice