B Tree

B树的应用场景：读写磁盘

我们知道，磁盘由于有机械运动部分，导致其读写速度比主存慢许多，而读写磁盘的主要开销来自于磁盘机械臂的寻道；

为了摊还寻道时间，需要设计一种高效的数据结构，满足如下要求，以减少磁盘的读取次数：

• 批量读写：磁盘一次IO操作存取大量的数据项
• 有限载入：磁盘比内存大得多，不能将磁盘的所有数据载入内存；
• 缓存：根据局部性原理，最近访问过的数据应该留在内存一段时间，并且用高效的方式组织起来；
• 任务：将所需页面从磁盘复制到内存，将修改的页面写回磁盘；
• 数据结构的指针应该保存在内存中；

因此以下是个人理解：

• B树往往作为索引结构而存在，通过索引找到在磁盘中存储在磁盘中的数据项(关键字)；
• B树的每个结点被设计地可能很大，当读写磁盘时按照结点为单位，批量地将大量关键字读写，进行内存和磁盘地交换，即IO操作；
• B树的根节点存在于内存，而不是磁盘的存储结构；
• 换句话说，B树是一个维护内存和磁盘交换数据信息的数据结构，其设计作用为降低IO次数
• 在操作系统实现一次IO操作中中，B树算法应该先于IO调度算法：OS启动相关的管理进程，在B树中找到需要和磁盘交换的数据项，读写磁盘之前，IO调度算法再适当优化顺序，进一步减少寻道时间；

定义

一个结点关键字数目在$[d,m-1]$的B树是具有以下性质的有根树(对于某些$d$阶B树和$m$阶B树说法对应关系，$m=2d+1$)：

• 每个结点至多有$m$个子结点，即$m$个子树,$m-1$个关键字；
• 每个非根结点至少有$d+1$个子节点，即$d+1$个子树，$d$个关键字;
• 根节点至少有$1$个关键字；
• 关键字在结点内部升序排列；

其中B树的最小度数为$d$;特别的$d=2$时每个结点有$2,3,4$个关键字，也称$2-3-4$树，是最简单的B树，可以转化成RB树；

满结点：有$m$个子树的结点；

B树的高度
$$
h\le \log_d \frac{N+1}{2}
$$
而且可以注意到，B树的叶子结点均在最高一层；

下图是一个合法的B树，以下均按照该树举例；

操作

新建

B树初始化指创建一个空的根结点，并为新节点分配一个磁盘页；

对于一个$d$阶B树而言，其结点应该维护如下字段

• 当前关键字个数n;
• 关键字数组keys;
• 子节点数组child;
• 是否是叶子isLeaf;

类似于普通的树，也应该有初始化根，搜索，插入，分裂，删除，合并的方法

template<typename T>
class BTree {
private:
    int d;
    struct Node {
        std::vector<T> keys;  
        std::vector<Node*> child;
        bool isLeaf;         
        int n;     

        Node(bool leaf = true) : isLeaf(leaf), n(0) {}
    };
    Node* root; 
    
    void insertNonFull(Node* x, const T& k) ;
    void splitChild(Node* x, int i);
    Node* search(Node* x, const T& k);
    void remove(Node* x, const T& k);
    void merge(Node* x, int i);
    void fill(Node* x, int i) ;
    void borrowFromPrev(Node* x, int i);
    void borrowFromNext(Node* x, int i);
public:
    BTree(int _d);
    bool search(const T& k);
    void insert(const T& k);
    void remove(const T& k);
};

BTree::BTree(int _d):d(_d){
    this->root = new BTree::Node();
}

插入+分裂

插入关键字，先查找关键字是否存在，若不存在，在叶子结点插入；

• 插入非满结点：直接找到关键字对应的位置，在该非满结点添加关键字，插入后仍是一个合法的B树结点；
• 插入满结点：必须需要按中间关键字分裂成两个结点，一个满结点上有$m-1$个关键字，插入一个关键字后，需要将中间关键字上提到父节点，左右两边各分出两个含有$d$个关键字的结点

按照顺序3，14，7，1，8，5，11，17，13，6，23，12，20，26，4，16，18，24，25，19插入，建立一个2阶B树；

过程如下：

搜索

搜索B树是二叉搜索的直接推广，从根节点开始，搜索关键字$k$:

在一个结点中的key（关键字）查找可用顺序查找或者二分查找；

删除+合并

1. 如果是叶子结点，直接删除key；

   非叶子结点，删除之后，将右子树最左的叶结点的key上移，取代已删除的key；

2. 叶结点key数量>=d，则结束；

   若叶结点中的key小于d个，则观察兄弟结点中是否有>d个key的结点

3. 是，则向兄弟结点借key，并保持两个结点的keys平均分配至两个节点中

   否，则该结点与一个兄弟结点合并

上述B树按顺序删除8,20,18,5

实现代码

template<typename T>
class BTree {
private:
    // B树的最小度数d
    int d;
    
    struct Node {
        std::vector<T> keys;        // 关键字数组
        std::vector<Node*> child;   // 子节点指针数组 
        bool isLeaf;                // 是否为叶节点
        int n;                      // 当前关键字个数

        Node(bool leaf = true) : isLeaf(leaf), n(0) {}
    };

    Node* root;  // 根节点指针

    // 在非满节点x中插入关键字k
    void insertNonFull(Node* x, const T& k) {
        int i = x->n - 1;
        
        if(x->isLeaf) {
            // 在叶节点中插入
            while(i >= 0 && x->keys[i] > k) {
                x->keys[i + 1] = x->keys[i];
                i--;
            }
            x->keys[i + 1] = k;
            x->n++;
        } else {
            // 在内部节点中找到合适的子节点
            while(i >= 0 && x->keys[i] > k) i--;
            i++;
            
            if(x->child[i]->n == 2 * d - 1) {
                splitChild(x, i);
                if(k > x->keys[i]) i++;
            }
            insertNonFull(x->child[i], k);
        }
    }

    // 分裂节点
    void splitChild(Node* x, int i) {
        Node* y = x->child[i];
        Node* z = new Node(y->isLeaf);
        
        z->n = d - 1;
        
        // 将y的后半部分关键字复制到z
        for(int j = 0; j < d - 1; j++) {
            z->keys.push_back(y->keys[j + d]);
        }
        
        // 如果y不是叶节点，复制相应的子节点
        if(!y->isLeaf) {
            for(int j = 0; j < d; j++) {
                z->child.push_back(y->child[j + d]);
            }
        }
        
        y->n = d - 1;
        
        // 将新节点插入到x的子节点中
        x->child.insert(x->child.begin() + i + 1, z);
        x->keys.insert(x->keys.begin() + i, y->keys[d - 1]);
        x->n++;
    }

    // 在节点中查找关键字
    Node* search(Node* x, const T& k) {
        int i = 0;
        while(i < x->n && k > x->keys[i]) i++;
        
        if(i < x->n && k == x->keys[i]) return x;
        
        if(x->isLeaf) return nullptr;
        
        return search(x->child[i], k);
    }

    // 删除关键字
    void remove(Node* x, const T& k) {
        int i = 0;
        while(i < x->n && k > x->keys[i]) i++;

        if(i < x->n && k == x->keys[i]) {
            if(x->isLeaf) {
                // 从叶节点直接删除
                x->keys.erase(x->keys.begin() + i);
                x->n--;
            } else {
                // 从内部节点删除
                Node* pred = x->child[i];
                if(pred->n >= d) {
                    // 用前驱替换
                    T pred_key = pred->keys[pred->n - 1];
                    x->keys[i] = pred_key;
                    remove(pred, pred_key);
                } else {
                    Node* succ = x->child[i + 1];
                    if(succ->n >= d) {
                        // 用后继替换
                        T succ_key = succ->keys[0];
                        x->keys[i] = succ_key;
                        remove(succ, succ_key);
                    } else {
                        // 合并节点
                        merge(x, i);
                        remove(pred, k);
                    }
                }
            }
        } else {
            if(x->isLeaf) return;
            
            bool flag = (i == x->n);
            if(x->child[i]->n < d) {
                fill(x, i);
            }
            
            if(flag && i > x->n)
                remove(x->child[i - 1], k);
            else
                remove(x->child[i], k);
        }
    }

    // 合并节点
    void merge(Node* x, int i) {
        Node* child = x->child[i];
        Node* sibling = x->child[i + 1];
        
        child->keys.push_back(x->keys[i]);
        
        for(int j = 0; j < sibling->n; j++) {
            child->keys.push_back(sibling->keys[j]);
        }
        
        if(!child->isLeaf) {
            for(int j = 0; j <= sibling->n; j++) {
                child->child.push_back(sibling->child[j]);
            }
        }
        
        x->keys.erase(x->keys.begin() + i);
        x->child.erase(x->child.begin() + i + 1);
        x->n--;
        
        child->n = child->keys.size();
        delete sibling;
    }

    // 填充节点
    void fill(Node* x, int i) {
        if(i != 0 && x->child[i - 1]->n >= d) {
            borrowFromPrev(x, i);
        } else if(i != x->n && x->child[i + 1]->n >= d) {
            borrowFromNext(x, i);
        } else {
            if(i != x->n)
                merge(x, i);
            else
                merge(x, i - 1);
        }
    }

    // 从前一个兄弟节点借关键字
    void borrowFromPrev(Node* x, int i) {
        Node* child = x->child[i];
        Node* sibling = x->child[i - 1];
        
        child->keys.insert(child->keys.begin(), x->keys[i - 1]);
        
        if(!child->isLeaf) {
            child->child.insert(child->child.begin(), sibling->child[sibling->n]);
        }
        
        x->keys[i - 1] = sibling->keys[sibling->n - 1];
        
        child->n++;
        sibling->n--;
    }

    // 从后一个兄弟节点借关键字
    void borrowFromNext(Node* x, int i) {
        Node* child = x->child[i];
        Node* sibling = x->child[i + 1];
        
        child->keys.push_back(x->keys[i]);
        
        if(!child->isLeaf) {
            child->child.push_back(sibling->child[0]);
        }
        
        x->keys[i] = sibling->keys[0];
        
        sibling->keys.erase(sibling->keys.begin());
        
        if(!sibling->isLeaf) {
            sibling->child.erase(sibling->child.begin());
        }
        
        child->n++;
        sibling->n--;
    }

public:
    BTree(int _d) : d(_d) {
        root = new Node();
    }

    // 查找关键字
    bool search(const T& k) {
        return search(root, k) != nullptr;
    }

    // 插入关键字
    void insert(const T& k) {
        if(root->n == 2 * d - 1) {
            Node* s = new Node(false);
            s->child.push_back(root);
            root = s;
            splitChild(s, 0);
            insertNonFull(s, k);
        } else {
            insertNonFull(root, k);
        }
    }

    // 删除关键字
    void remove(const T& k) {
        if(!root) return;
        
        remove(root, k);
        
        if(root->n == 0) {
            Node* tmp = root;
            if(root->isLeaf)
                root = nullptr;
            else
                root = root->child[0];
            delete tmp;
        }
    }
};

评价

• B树的查找性能逼近二分查找；
• 改变B树结构（插入与删除操作）不需要移动大段的内存数据