BPlusTree

(Updated: )

B+ Tree

简介

在下面的操作分析中，如果觉得过于抽象，可以用这个网站手动模拟一下，方便理解

尤其是删除，手动模拟几种分支判断会帮助理解/写代码

定义

type

1
enum type {INTERNAL, LEAF};

每个节点两种类型, 内部节点或叶子节点

Value

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T> struct Value{
protected:
    T value;
    int count;
    Value<T>(T value, int count) : value(value), count(count) {}
    Value<T>() {}
    ~Value<T>() {}
    bool operator<(const Value<T> &x) const{
        return value < x.value;
    }
    friend class Node<T>;
    friend class BPlusTree<T>;
};

节点中用来存值, 以及值出现的次数

Node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int M = 3, m = (M - 1) / 2;
template <typename T> class Node{
protected:
    Node<T> *fa, *nxt, *pre;
    Node<T> **son;
    Value<T> **leaf_val;
    Value<T> ***internal_val;
    int cnt, sz; // cnt: num of val, <= M - 1; when >= M, split
    type t;
    Node<T>(type t, Node<T> *fa) : t(t), fa(fa){
        nxt = pre = NULL, cnt = sz = 0;
        leaf_val = NULL, internal_val = NULL;
        if(t == LEAF) leaf_val = new Value<T> * [M];
        else internal_val = new Value<T> **[M];
        son = new Node<T> * [M + 1];
        for (int i = 0; i <= M; ++i){
            if (i < M){
                if(t == LEAF) leaf_val[i] = NULL;
                else internal_val[i] = NULL;
            }
            son[i] = NULL;
        }
    }
    Node<T>() {}
    ~Node<T>() {delete [] son, delete [] leaf_val, delete [] internal_val; }
    friend class BPlusTree<T>;
};

有一个向上的 fa 指针，向右的 nxt 指针 (为了方便又加了 pre 指针，都一样的)，类型 t (表示是叶子还是内部节点)，键值数量 cnt, 实际值数量 sz (指的是叶子节点里存储的实际值；只在查询时用上)，儿子集合和键值集合

还有两个常数，一个是阶数 (最大儿子数量), 一个是最少键值数量 (为了判断方便，这里取的是键值最小数量，熟悉的最小儿子数量是 )

除了根节点的内部节点儿子数量在 范围内，键值数量为

根节点儿子数量在 范围内，键值数量为

叶子节点键值数量为 ，没有儿子

同时, 分成 internal_val 和 leaf_val 两个指针数组存储值对象, 如果是叶子直接存值, 如果是内部节点, 则存储一个指向叶子节点 leaf_val 的指针

也就是说 internal_val 是三级指针

BPlusTree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
template <typename T> class BPlusTree{
private:
    int traverse(Node<T> *u, T val);
    int get_id(Node<T> *u);
    void pushup(Node<T> *u);
    void insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val);
    void insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val);
    void insert_leaf_by_id(Node<T> *u, int id, Value<T> *val);
    Value<T>** delete_internal_right_by_id(Node<T> *u, int id);
    Value<T>** delete_internal_left_by_id(Node<T> *u, int id);
    Value<T>* delete_leaf_by_id(Node<T> *u, int id);
    void linkin(Node<T> *u, Node<T> *v);
    void linkout(Node<T> *u, Node<T> *v);
    void split(Node<T> *u);
    void merge(Node<T> *u, Node<T> *v);
    void fix(Node<T> *u);
    void clear(Node<T> *u){
        if(!u) return;
        for(int i = 0; i <= u->cnt; ++i) clear(u->son[i]);
        delete u, u = nullptr;
    }
    void destroy(Node<T> *u){
        while(u && u->t == INTERNAL) u = u->son[0];
        while(u){
            for(int i = 0; i < u->cnt; ++i) 
                delete u->leaf_val[i], u->leaf_val[i] = nullptr;
            u = u->nxt;
        }
    }
public:
    Node<T> *root;
    void insert(Node<T> *u, T val);
    void erase(Node<T> *u, T val);
    int getrank(Node<T> *x, T val);
    T getval(Node<T> *x, int rank);
    int getpre(Node<T> *x, T val);
    int getnxt(Node<T> *x, T val);
    BPlusTree<T>() { root = NULL; }
    ~BPlusTree<T>() { destroy(root); clear(root); }
};

基础操作

traverse

用于插入/删除时, 在节点内比较键值

1
2
3
4
5
6
7
8
template<typename T> int BPlusTree<T>::traverse(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (u->t == LEAF && val <= u->leaf_val[i]->value) break;
        else if (u->t == INTERNAL && val < u->internal_val[i][0]->value) break;
    }
    return i;
}

get_id

用来获得当前节点是父亲的哪个儿子

1
2
3
4
5
6
template <typename T> int BPlusTree<T>::get_id(Node<T> *u){ // get the index of u 
    Node<T> *fa = u->fa;
    if (!fa) return 0;
    for (int i = 0; i <= fa->cnt; ++i) 
        if (fa->son[i] == u) return i;
}

这个暴力枚举单次 , 不会对整体复杂度造成影响

pushup

主要用来维护 sz, 用于查询

1
2
3
4
5
6
7
8
9
template <typename T> void BPlusTree<T>::pushup(Node<T> *u){
    if(!u) return;
    u->sz = 0;
    if (u->t == LEAF){
        for (int i = 0; i < u->cnt; ++i) u->sz += u->leaf_val[i]->count;
    }else{
        for (int i = 0; i <= u->cnt; ++i) u->sz += u->son[i]->sz;
    }
}

linkin/ linkout

由于节点之间由 nxt, pre 指针相连, 实际是一个双向链表, 那么在增删节点时对这个链表进行维护操作

1
2
3
4
5
6
7
8
9
10
template <typename T> void BPlusTree<T>::linkin(Node<T> *u, Node<T> *v){ // double linked list, insert v
    Node<T> *nxt = u->nxt; 
    v->nxt = u->nxt, v->pre = u, u->nxt = v;
    if(nxt) nxt->pre = v;
}
template <typename T> void BPlusTree<T>::linkout(Node<T> *u, Node<T> *v){ // double linked list, delete v
    Node<T> *nxt = v->nxt; 
    u->nxt = nxt, v->nxt = NULL, v->pre = NULL;
    if (nxt) nxt->pre = u;
}

insert_leaf_by_id

向叶子节点的 leaf_val[id] 位置插入一个值, 需要将后半个数组移动位置, 腾出一个空位, 再将值填进去

1
2
3
4
5
6
template <typename T> void BPlusTree<T>::insert_leaf_by_id(Node<T> *u, int id, Value<T> *val){ 
    // insert val[id]
    for (int i = u->cnt; i >= id + 1; --i) u->leaf_val[i] = u->leaf_val[i - 1];
    u->leaf_val[id] = val;
    ++u->cnt, pushup(u);
}

insert_internal_left/right_by_id

在后面将删除时会提到, 插入内部节点分为从左 / 从右插入

因为插内部节点时不仅插入值, 还要插入儿子, 而原本儿子比值多一个, 所以把儿子贴在原数组的左边 / 右边, 对应的下标是不同的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename T> void BPlusTree<T>::insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val){ 
    // insert val[id] and son[id]
    for (int i = u->cnt; i >= id; --i){ 
        if (i >= 1) u->internal_val[i] = u->internal_val[i - 1];
        u->son[i + 1] = u->son[i];
    }
    u->son[id] = s, s->fa = u, u->internal_val[id] = val;
    ++u->cnt, pushup(u);
}
template <typename T> void BPlusTree<T>::insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val){ 
    // insert val[id] and son[id + 1]
    for (int i = u->cnt; i >= id + 1; --i)
        u->internal_val[i] = u->internal_val[i - 1], u->son[i + 1] = u->son[i];
    u->son[id + 1] = s, s->fa = u, u->internal_val[id] = val;
    ++u->cnt, pushup(u);
}

delete_leaf_by_id

删除值数组的 leaf_val[id] 位置的值

同时将这个值对应的指针传出, 在外面需要决定是否 delete 这个值对象

1
2
3
4
5
6
7
template <typename T> Value<T>* BPlusTree<T>::delete_leaf_by_id(Node<T> *u, int id){ 
    // delete val[id]
    Value<T> *deleted_val = u->leaf_val[id];
    for (int i = id + 1; i < u->cnt; ++i) u->leaf_val[i - 1] = u->leaf_val[i];
    u->leaf_val[u->cnt - 1] = NULL, u->cnt--, pushup(u);
    return deleted_val;
}

delete_internal_left/right_by_id

同上, 插入内部节点时, 从左边 / 右边扣一个儿子下来, 对应的下标有区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename T> Value<T>** BPlusTree<T>::delete_internal_left_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id]
    Value<T> **deleted_val = u->internal_val[id];
    for (int i = id + 1; i <= u->cnt; ++i){
        if(i < u->cnt) u->internal_val[i - 1] = u->internal_val[i];
        u->son[i - 1] = u->son[i];
    }
    u->internal_val[u->cnt - 1] = NULL, u->son[u->cnt] = NULL;
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> Value<T>** BPlusTree<T>::delete_internal_right_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id + 1]
    Value<T> **deleted_val = u->internal_val[id];
    for (int i = id + 1; i < u->cnt; ++i) 
        u->internal_val[i - 1] = u->internal_val[i], u->son[i] = u->son[i + 1];
    u->internal_val[u->cnt - 1] = NULL, u->son[u->cnt] = NULL;
    u->cnt--, pushup(u);
    return deleted_val;
}

插入

0x00 空

直接插入一个根节点，类型为 LEAF, 并存有一个键值

0x01 叶子不满

直接将值插入到叶子，退出

0x02 叶子满

需要分裂成两个节点

注意如果当前节点是根，需要新建一个根

将 分裂出一个 , 将一般的数据移动到 中，使得 和 都满足儿子数量最少为

如果是叶子节点，那么让 保留前 个键值，让 继承后 个键值，将第 个键值上送给父亲(这里键值从 开始编号)


图中

如果是内部节点，那么让 保留前 个儿子 (前 个键值)，将第 个键值上送给父亲 (这里键值从 开始编号)，让 继承后 个儿子 (后 个键值)

图中

于是有分裂的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T> void BPlusTree<T>::split(Node<T> *u){
    int mid = (u->t == LEAF) ? M / 2 : (M - 1) / 2;
    Node<T> *fa = u->fa;
    if (!fa) root = fa = new Node<T>(INTERNAL, NULL), fa->son[0] = u, u->fa = fa;
    Node<T> *v = new Node<T>(u->t, fa);
    int id = get_id(u);
    Value<T> **p = (u->t == LEAF ? v->leaf_val : u->internal_val[mid]);
    insert_internal_right_by_id(fa, id, v, p); // insert the middle value into parent
    if (u->t == LEAF){
        for (int i = mid; i < u->cnt; ++i) v->leaf_val[i - mid] = u->leaf_val[i], u->leaf_val[i] = NULL;
        u->cnt = mid, v->cnt = M - mid;
        linkin(u, v);
    }else{
        for (int i = mid + 1; i <= u->cnt; ++i){
            if (i < u->cnt) v->internal_val[i - mid - 1] = u->internal_val[i], u->internal_val[i] = NULL;
            v->son[i - mid - 1] = u->son[i], u->son[i]->fa = v, u->son[i] = NULL;
        }
        u->cnt = mid, v->cnt = M - mid - 1;
    }
    pushup(u), pushup(v);
}

那么我们可以写出插入的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename T> void BPlusTree<T>::insert(Node<T> *u, T val){
    if (!root){ // new root 
        root = new Node<T>(LEAF, NULL);
        insert_leaf_by_id(root, 0, new Value<T>(val, 1));
        pushup(root);
        return;
    }
    int i = traverse(u, val); // get the rank of val
    if (u->t == INTERNAL) insert(u->son[i], val);
    else{
        if (i < u->cnt && val == u->leaf_val[i]->value){
            ++u->leaf_val[i]->count, pushup(u);
            return;
        }
        insert_leaf_by_id(u, i, new Value<T>(val, 1));
    }
    if (u->cnt >= M) split(u); // need to split when number of value >= M 
    pushup(u);
}

注意如果键值已经存在, 就将计数器加 , 不改变树结构

删除

0x00 删除后根的值为空

将根删除, 根指针指向原本的根唯一的儿子作为新根

如果儿子为空, 则说明整棵树已经删空

0x01 删除后不需要维护

直接 delete 值对象, 退出即可

0x02 删除后需要维护

如果删除后值数量 , 那么就需要维护

删除的维护 fix 分为 borrow_pre, borrow_nxt 和 merge 三种情况, 比较复杂

borrow_pre

如果当前节点的左兄弟值数量 , 说明减少一个值仍然满足 , 则可以借给当前节点一个值

此时我们可以把兄弟最右边的值和儿子扣下来, 左插给当前节点, 记这个值为 pre

如果当前节点是叶子节点, 就直接将 pre 插入当前节点, 在兄弟节点中删除这个值

图中

如果当前节点是内部节点, 则需要将兄弟节点最靠右的值插入父亲节点对应于当前节点与兄弟节点之间的位置

同时将父亲那个位置的值插入当前节点最左边的位置

因为兄弟节点要将最右边的儿子转让给当前节点, 而当前节点底层的最左边的叶子节点会改变成转让来的节点, 所以对应父亲节点的值变成转让来的节点的左边底层的值, 当前节点的值需要插入一个父亲节点的对应值

注意这种情况只发生在叶子节点需要合并时, 因为只有这样才会让内部节点值数量减少

图中 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (id > 0 && fa->son[id - 1]->cnt > m){ // borrow pre
    Node<T> *v = fa->son[id - 1];
    if(u->t == LEAF){
        Value<T> *pre = v->leaf_val[v->cnt - 1];
        insert_leaf_by_id(u, 0, pre);
        delete_leaf_by_id(v, v->cnt - 1);
    }else{
        Node<T> *s = v->son[v->cnt];
        Value<T> **pre = fa->internal_val[id - 1];
        fa->internal_val[id - 1] = v->internal_val[v->cnt - 1]; // change parent
        insert_internal_left_by_id(u, 0, s, pre);
        delete_internal_right_by_id(v, v->cnt - 1);
    }
    pushup(u), pushup(v);
}

borrow_nxt

与上面对称

如果当前节点的右兄弟值数量 , 说明减少一个值仍然满足 , 则可以借给当前节点一个值

此时我们可以把兄弟最左边的值和儿子扣下来, 右插给当前节点, 记这个值为 nxt

如果当前节点是叶子节点, 就直接将 nxt 插入当前节点, 在兄弟节点中删除这个值

如果当前节点是内部节点, 则需要将兄弟节点最靠左的值插入父亲节点对应于当前节点与兄弟节点之间的位置

同时将父亲那个位置的值插入当前节点最右边的位置

因为兄弟节点要将最左边的儿子转让给当前节点, 而兄弟节点底层的最左边的叶子节点会改变成转让节点后面的节点, 所以对应父亲节点的值变成后面节点左边底层的值, 当前节点的值需要插入一个父亲节点的对应值, 也就是转让来的节点左边底层对应的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if (id < fa->cnt && fa->son[id + 1]->cnt > m){ // borrow nxt
    Node<T> *v = fa->son[id + 1];
    if(u->t == LEAF){
        Value<T> *nxt = v->leaf_val[0];
        delete_leaf_by_id(v, 0);               
        insert_leaf_by_id(u, u->cnt, nxt); 
    }else{
        Node<T> *s = v->son[0];
        Value<T> **nxt = fa->internal_val[id];
        fa->internal_val[id] = v->internal_val[0]; // change parent
        delete_internal_left_by_id(v, 0);               
        insert_internal_right_by_id(u, u->cnt, s, nxt); 
    }
    pushup(u), pushup(v);
}

merge

如果左右都不够借, 那就合并当前节点和任意一个兄弟节点

如果两个叶子节点合并, 就直接将值数组合并

图中

如果是内部节点合并, 假设合并的节点为 和

则需要将父亲节点对应的一个值和 最左边儿子一起右插入

因为 最左边儿子对应的值不在 中, 而在父亲节点中

图中

对于级联合并的情况:

图中

对于需要删除根的情况:

图中

同时, 无论叶子还是内部节点, 都需要将父亲节点的一个值删去, 保证值数量正确

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T> void BPlusTree<T>::merge(Node<T> *u, Node<T> *v){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    if (u->t == LEAF){
        for (int i = 0; i < v->cnt; ++i)
            u->leaf_val[u->cnt++] = v->leaf_val[i], v->leaf_val[i] = NULL;
        v->cnt = 0;
        linkout(u, v);
    }else{
        insert_internal_right_by_id(u, u->cnt, v->son[0], fa->internal_val[id]);
        for (int i = 0; i < v->cnt; ++i){
            u->internal_val[u->cnt++] = v->internal_val[i], v->internal_val[i] = NULL;
            u->son[u->cnt] = v->son[i + 1], v->son[i + 1]->fa = u, v->son[i + 1] = NULL;
        }
        v->cnt = 0;
    }
    delete_internal_right_by_id(fa, id); // what if this sentence is put in front of if (u->t == LEAF) sentence?
    delete v, v = nullptr;
    pushup(u);
}

于是可以写出删除的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T> void BPlusTree<T>::erase(Node<T> *u, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL) erase(u->son[i], val);
    else{
        if (i >= u->cnt || u->leaf_val[i]->value != val) return; // not found
        if (u->leaf_val[i]->count > 1){
            --u->leaf_val[i]->count, pushup(u);
            return;
        }
        Value<T> *deleted_value = delete_leaf_by_id(u, i);
        delete deleted_value, deleted_value = nullptr;
    }
    if (u == root && !u->cnt){
        root = u->son[0];
        if(root) root->fa = NULL, pushup(root);
        delete u, u = nullptr;
        return;
    }
    if (u->cnt < m) fix(u);
    pushup(u);
}

查询

我们可以写出常见的 种平衡树查询函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
template <typename T> int BPlusTree<T>::getrank(Node<T> *u, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL){
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->son[j]->sz;
        return rank + getrank(u->son[i], val);
    }else{
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->leaf_val[j]->count;
        return rank + 1;
    }
}
template <typename T> T BPlusTree<T>::getval(Node<T> *u, int rank){
    int i = 0;
    if (u->t == INTERNAL){
        for (; i <= u->cnt; ++i){
            if (rank <= u->son[i]->sz) break;
            else rank -= u->son[i]->sz;
        }
        return getval(u->son[i], rank);
    }else{
        for (; i < u->cnt; ++i){
            if (rank >= 1 && rank <= u->leaf_val[i]->count) return u->leaf_val[i]->value;
            else rank -= u->leaf_val[i]->count;
        }
    }
}
template <typename T> int BPlusTree<T>::getpre(Node<T> *u, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL) return getpre(u->son[i], val);
    else{
        if (i == 0) u = u->pre, i = u->cnt;
        return u->leaf_val[i - 1]->value;
    }
}
template <typename T>int BPlusTree<T>::getnxt(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if(u->t == LEAF && val < u->leaf_val[i]->value) break;
        else if(u->t == INTERNAL && val < u->internal_val[i][0]->value) break;
    }
    if (u->t == INTERNAL) return getnxt(u->son[i], val);
    else{
        if (i == u->cnt) u = u->nxt, i = 0;
        return u->leaf_val[i]->value;
    }
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8 + 10;
const int M = 3, m = (M - 1) / 2;
int n;
template <typename T> class Node;
template <typename T> class BPlusTree;
enum type {INTERNAL, LEAF};
template <typename T> struct Value{
protected:
    T value;
    int count;
    Value<T>(T value, int count) : value(value), count(count) {}
    Value<T>() {}
    ~Value<T>() {}
    bool operator<(const Value<T> &x) const{
        return value < x.value;
    }
    friend class Node<T>;
    friend class BPlusTree<T>;
};
template <typename T> class Node{
protected:
    Node<T> *fa, *nxt, *pre;
    Node<T> **son;
    Value<T> **leaf_val;
    Value<T> ***internal_val;
    int cnt, sz; // cnt: num of val, <= M - 1; when >= M, split
    type t;
    Node<T>(type t, Node<T> *fa) : t(t), fa(fa){
        nxt = pre = NULL, cnt = sz = 0;
        leaf_val = NULL, internal_val = NULL;
        if(t == LEAF) leaf_val = new Value<T> * [M];
        else internal_val = new Value<T> **[M];
        son = new Node<T> * [M + 1];
        for (int i = 0; i <= M; ++i){
            if (i < M){
                if(t == LEAF) leaf_val[i] = NULL;
                else internal_val[i] = NULL;
            }
            son[i] = NULL;
        }
    }
    Node<T>() {}
    ~Node<T>() {delete [] son, delete [] leaf_val, delete [] internal_val; } // add this line will cause luogu P3369 RE
    friend class BPlusTree<T>;
};
template <typename T> class BPlusTree{
private:
    int traverse(Node<T> *u, T val);
    int get_id(Node<T> *u);
    void pushup(Node<T> *u);
    void insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val);
    void insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val);
    void insert_leaf_by_id(Node<T> *u, int id, Value<T> *val);
    Value<T>** delete_internal_right_by_id(Node<T> *u, int id);
    Value<T>** delete_internal_left_by_id(Node<T> *u, int id);
    Value<T>* delete_leaf_by_id(Node<T> *u, int id);
    void linkin(Node<T> *u, Node<T> *v);
    void linkout(Node<T> *u, Node<T> *v);
    void split(Node<T> *u);
    void merge(Node<T> *u, Node<T> *v);
    void fix(Node<T> *u);
    void clear(Node<T> *u){
        if(!u) return;
        for(int i = 0; i <= u->cnt; ++i) clear(u->son[i]);
        delete u, u = nullptr;
    }
    void destroy(Node<T> *u){
        while(u && u->t == INTERNAL) u = u->son[0];
        while(u){
            for(int i = 0; i < u->cnt; ++i) 
                delete u->leaf_val[i], u->leaf_val[i] = nullptr;
            u = u->nxt;
        }
    }
public:
    Node<T> *root;
    void insert(Node<T> *u, T val);
    void erase(Node<T> *u, T val);
    int getrank(Node<T> *x, T val);
    T getval(Node<T> *x, int rank);
    int getpre(Node<T> *x, T val);
    int getnxt(Node<T> *x, T val);
    BPlusTree<T>() { root = NULL; }
    ~BPlusTree<T>() { destroy(root); clear(root); }
};
template <typename T> int BPlusTree<T>::get_id(Node<T> *u){ // get the index of u 
    Node<T> *fa = u->fa;
    if (!fa) return 0;
    for (int i = 0; i <= fa->cnt; ++i) 
        if (fa->son[i] == u) return i;
}
template <typename T> void BPlusTree<T>::linkin(Node<T> *u, Node<T> *v){ // double linked list, insert v
    Node<T> *nxt = u->nxt; 
    v->nxt = u->nxt, v->pre = u, u->nxt = v;
    if(nxt) nxt->pre = v;
}
template <typename T> void BPlusTree<T>::linkout(Node<T> *u, Node<T> *v){ // double linked list, delete v
    Node<T> *nxt = v->nxt; 
    u->nxt = nxt, v->nxt = NULL, v->pre = NULL;
    if (nxt) nxt->pre = u;
}
template <typename T> void BPlusTree<T>::pushup(Node<T> *u){
    if(!u) return;
    u->sz = 0;
    if (u->t == LEAF){
        for (int i = 0; i < u->cnt; ++i) u->sz += u->leaf_val[i]->count;
    }else{
        for (int i = 0; i <= u->cnt; ++i) u->sz += u->son[i]->sz;
    }
}
template <typename T> void BPlusTree<T>::insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val){ 
    // insert val[id] and son[id + 1]
    for (int i = u->cnt; i >= id + 1; --i)
        u->internal_val[i] = u->internal_val[i - 1], u->son[i + 1] = u->son[i];
    u->son[id + 1] = s, s->fa = u, u->internal_val[id] = val;
    ++u->cnt, pushup(u);
}
template <typename T> void BPlusTree<T>::insert_leaf_by_id(Node<T> *u, int id, Value<T> *val){ 
    // insert val[id]
    for (int i = u->cnt; i >= id + 1; --i) u->leaf_val[i] = u->leaf_val[i - 1];
    u->leaf_val[id] = val;
    ++u->cnt, pushup(u);
}
template <typename T> void BPlusTree<T>::insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val){ 
    // insert val[id] and son[id]
    for (int i = u->cnt; i >= id; --i){ 
        if (i >= 1) u->internal_val[i] = u->internal_val[i - 1];
        u->son[i + 1] = u->son[i];
    }
    u->son[id] = s, s->fa = u, u->internal_val[id] = val;
    ++u->cnt, pushup(u);
}
template <typename T> Value<T>* BPlusTree<T>::delete_leaf_by_id(Node<T> *u, int id){ 
    // delete val[id]
    Value<T> *deleted_val = u->leaf_val[id];
    for (int i = id + 1; i < u->cnt; ++i) u->leaf_val[i - 1] = u->leaf_val[i];
    u->leaf_val[u->cnt - 1] = NULL, u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> Value<T>** BPlusTree<T>::delete_internal_right_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id + 1]
    Value<T> **deleted_val = u->internal_val[id];
    for (int i = id + 1; i < u->cnt; ++i) 
        u->internal_val[i - 1] = u->internal_val[i], u->son[i] = u->son[i + 1];
    u->internal_val[u->cnt - 1] = NULL, u->son[u->cnt] = NULL;
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> Value<T>** BPlusTree<T>::delete_internal_left_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id]
    Value<T> **deleted_val = u->internal_val[id];
    for (int i = id + 1; i <= u->cnt; ++i){
        if(i < u->cnt) u->internal_val[i - 1] = u->internal_val[i];
        u->son[i - 1] = u->son[i];
    }
    u->internal_val[u->cnt - 1] = NULL, u->son[u->cnt] = NULL;
    u->cnt--, pushup(u);
    return deleted_val;
}
template<typename T> int BPlusTree<T>::traverse(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (u->t == LEAF && val <= u->leaf_val[i]->value) break;
        else if (u->t == INTERNAL && val < u->internal_val[i][0]->value) break;
    }
    return i;
}
template <typename T> void BPlusTree<T>::split(Node<T> *u){
    int mid = (u->t == LEAF) ? M / 2 : (M - 1) / 2;
    Node<T> *fa = u->fa;
    if (!fa) root = fa = new Node<T>(INTERNAL, NULL), fa->son[0] = u, u->fa = fa;
    Node<T> *v = new Node<T>(u->t, fa);
    int id = get_id(u);
    Value<T> **p = (u->t == LEAF ? v->leaf_val : u->internal_val[mid]);
    insert_internal_right_by_id(fa, id, v, p);
    if (u->t == LEAF){
        for (int i = mid; i < u->cnt; ++i) v->leaf_val[i - mid] = u->leaf_val[i], u->leaf_val[i] = NULL;
        u->cnt = mid, v->cnt = M - mid;
        linkin(u, v);
    }else{
        for (int i = mid + 1; i <= u->cnt; ++i){
            if (i < u->cnt) v->internal_val[i - mid - 1] = u->internal_val[i], u->internal_val[i] = NULL;
            v->son[i - mid - 1] = u->son[i], u->son[i]->fa = v, u->son[i] = NULL;
        }
        u->cnt = mid, v->cnt = M - mid - 1;
    }
    pushup(u), pushup(v);
}
template <typename T> void BPlusTree<T>::insert(Node<T> *u, T val){
    if (!root){
        root = new Node<T>(LEAF, NULL);
        insert_leaf_by_id(root, 0, new Value<T>(val, 1));
        pushup(root);
        return;
    }
    int i = traverse(u, val);
    if (u->t == INTERNAL) insert(u->son[i], val);
    else{
        if (i < u->cnt && val == u->leaf_val[i]->value){
            ++u->leaf_val[i]->count, pushup(u);
            return;
        }
        insert_leaf_by_id(u, i, new Value<T>(val, 1));
    }
    if (u->cnt >= M) split(u);
    pushup(u);
}
template <typename T> void BPlusTree<T>::merge(Node<T> *u, Node<T> *v){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    if (u->t == LEAF){
        for (int i = 0; i < v->cnt; ++i)
            u->leaf_val[u->cnt++] = v->leaf_val[i], v->leaf_val[i] = NULL;
        v->cnt = 0;
        linkout(u, v);
    }else{
        insert_internal_right_by_id(u, u->cnt, v->son[0], fa->internal_val[id]);
        for (int i = 0; i < v->cnt; ++i){
            u->internal_val[u->cnt++] = v->internal_val[i], v->internal_val[i] = NULL;
            u->son[u->cnt] = v->son[i + 1], v->son[i + 1]->fa = u, v->son[i + 1] = NULL;
        }
        v->cnt = 0;
    }
    delete_internal_right_by_id(fa, id); // what if this sentence is put in front of if (u->t == LEAF) sentence?
    delete v, v = nullptr;
    pushup(u);
}
template <typename T> void BPlusTree<T>::fix(Node<T> *u){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    if (!fa) return;
    if (id > 0 && fa->son[id - 1]->cnt > m){ // borrow pre
        Node<T> *v = fa->son[id - 1];
        if(u->t == LEAF){
            Value<T> *pre = v->leaf_val[v->cnt - 1];
            insert_leaf_by_id(u, 0, pre);
            delete_leaf_by_id(v, v->cnt - 1);
        }else{
            Node<T> *s = v->son[v->cnt];
            Value<T> **pre = fa->internal_val[id - 1];
            fa->internal_val[id - 1] = v->internal_val[v->cnt - 1]; // change parent
            insert_internal_left_by_id(u, 0, s, pre);
            delete_internal_right_by_id(v, v->cnt - 1);
        }
        pushup(u), pushup(v);
    }else if (id < fa->cnt && fa->son[id + 1]->cnt > m){ // borrow nxt
        Node<T> *v = fa->son[id + 1];
        if(u->t == LEAF){
            Value<T> *nxt = v->leaf_val[0];
            delete_leaf_by_id(v, 0);               
            insert_leaf_by_id(u, u->cnt, nxt); 
        }else{
            Node<T> *s = v->son[0];
            Value<T> **nxt = fa->internal_val[id];
            fa->internal_val[id] = v->internal_val[0]; // change parent
            delete_internal_left_by_id(v, 0);               
            insert_internal_right_by_id(u, u->cnt, s, nxt); 
        }
        pushup(u), pushup(v);
    }else{
        if (id > 0) merge(fa->son[id - 1], u);
        else merge(u, fa->son[id + 1]);
    }
}
template <typename T> void BPlusTree<T>::erase(Node<T> *u, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL) erase(u->son[i], val);
    else{
        if (i >= u->cnt || u->leaf_val[i]->value != val) return; // not found
        if (u->leaf_val[i]->count > 1){
            --u->leaf_val[i]->count, pushup(u);
            return;
        }
        Value<T> *deleted_value = delete_leaf_by_id(u, i);
        delete deleted_value, deleted_value = nullptr;
    }
    if (u == root && !u->cnt){
        root = u->son[0];
        if(root) root->fa = NULL, pushup(root);
        delete u, u = nullptr;
        return;
    }
    if (u->cnt < m) fix(u);
    pushup(u);
}
template <typename T> int BPlusTree<T>::getrank(Node<T> *u, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL){
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->son[j]->sz;
        return rank + getrank(u->son[i], val);
    }else{
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->leaf_val[j]->count;
        return rank + 1;
    }
}
template <typename T> T BPlusTree<T>::getval(Node<T> *u, int rank){
    int i = 0;
    if (u->t == INTERNAL){
        for (; i <= u->cnt; ++i){
            if (rank <= u->son[i]->sz) break;
            else rank -= u->son[i]->sz;
        }
        return getval(u->son[i], rank);
    }else{
        for (; i < u->cnt; ++i){
            if (rank >= 1 && rank <= u->leaf_val[i]->count) return u->leaf_val[i]->value;
            else rank -= u->leaf_val[i]->count;
        }
    }
}
template <typename T> int BPlusTree<T>::getpre(Node<T> *u, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL) return getpre(u->son[i], val);
    else{
        if (i == 0) u = u->pre, i = u->cnt;
        return u->leaf_val[i - 1]->value;
    }
}
template <typename T>int BPlusTree<T>::getnxt(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if(u->t == LEAF && val < u->leaf_val[i]->value) break;
        else if(u->t == INTERNAL && val < u->internal_val[i][0]->value) break;
    }
    if (u->t == INTERNAL) return getnxt(u->son[i], val);
    else{
        if (i == u->cnt) u = u->nxt, i = 0;
        return u->leaf_val[i]->value;
    }
}
void solve(){
    scanf("%d", &n);
    BPlusTree<int> *S = new BPlusTree<int>();
    for (int i = 1; i <= n; ++i){
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1){
            S->insert(S->root, x);
        }else if (op == 2){
            S->erase(S->root, x);
        }else if (op == 3){
            printf("%d\n", S->getrank(S->root, x));
        }else if (op == 4){
            printf("%d\n", S->getval(S->root, x));
        }else if (op == 5){
            printf("%d\n", S->getpre(S->root, x));
        }else if (op == 6){
            printf("%d\n", S->getnxt(S->root, x));
        }
    }
    delete S;
}
int main(){
    solve();
    return 0;
}

关于跳表实现的 B+ 树

使用跳表替换 B+ 树的数组, 可以将节点内 traverse 函数获取下标的复杂度从 降为

所以整个 B+ 树的复杂度降为

由于跳表在小数据下可能效率低下, 并且 在 较大时才会明显好于 , 所以这种实现方式只适用于 很大的情况

这里给出一个只实现了 insert, erase 的跳表 B+ 树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8 + 10;
const int MAXL = 20;
const double p = 0.5;
const int M = 10000, m = (M - 1) / 2;
int n, ccnt, o;
template <typename T> class Node;
enum type {INTERNAL, LEAF};
template <typename T> struct Value{
public:
    T value;
    int count;
    Value<T>(T value, int count) : value(value), count(count) {}
    Value<T>() {}
    ~Value<T>() {}
    bool operator<(const Value<T> &x) const{
        return value < x.value;
    }
};
/*--------------------- Value List---------------------- */
template <typename T> class SkipList;
template <typename T> class SLNode{
public:
    SLNode<T> **forward;
    int *next;
    Value<T> *leaf_key;
    SkipList<T> *internal_key;
    type t;
    int level;
    SLNode<T>() {}
    ~SLNode<T>() {
        delete [] forward;
        delete [] next;
    }
    SLNode<T>(Value<T> *leaf_key, SkipList<T> *internal_key, type t) : 
        leaf_key(leaf_key), internal_key(internal_key), t(t) {
        next = new int [MAXL + 1];
        forward = new SLNode<T> *[MAXL + 1]; 
        for (int i = 0; i <= MAXL; ++i)
            forward[i] = NULL, next[i] = 0;
        level = RandomLevel();
    }
    int RandomLevel(){
        int lv = 0;
        int maxn = 1023;
        while (lv < MAXL && rand() % maxn < (int)(p * maxn)) ++lv;
        return lv;
    }
    friend class SkipList<T>;
};
template <typename T> class SkipList {
public:
    int level;
    int length;
    type t;
    SLNode<T> *head;
    SkipList<T>(type t) :t(t) { head = new SLNode<T>(0, 0, t), level = 0, length = 0; }
    ~SkipList<T>() {
        SLNode<T> *p = head;
        while(p){
            SLNode<T> *q = p->forward[0];
            delete p, p = q;
        }   
    }
    SLNode<T>* operator [](int rank){ // from 0
        // speed up internal_key to O(1)
        if(rank == 0) return head->forward[0];
        ++rank;
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->next[i] < rank)
                rank -= p->next[i], p = p->forward[i];
        }
        p = p->forward[0];
        return p;
    }
    int getrank_leaf(T key){
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value < key)
                now += p->next[i], p = p->forward[i];
        }
        return now + 1;
    }
    int getrank_Leaf(T key){
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value <= key)
                now += p->next[i], p = p->forward[i];
        }
        return now + 1;
    }
    int getrank_internal(T key){
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && (*p->forward[i]->internal_key)[0]->leaf_key->value <= key)
                now += p->next[i], p = p->forward[i];
        }
        return now + 1;
    }
    void insert_leaf(Value<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value < key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++; // now += p->next[0]
        SLNode<T> *NewNode = new SLNode<T>(key, NULL, t);
        if (level < NewNode->level){
            NewNode->level = head->level = ++level;
            update[level] = head, pos[level] = 0;
        }
        for (int i = 0; i <= level; ++i){
            p = update[i];
            if (i <= NewNode->level){
                NewNode->forward[i] = p->forward[i];
                if (p->forward[i]) NewNode->next[i] = p->next[i] - (now - pos[i]) + 1;
                else NewNode->next[i] = 0;
                p->next[i] = now - pos[i];
                p->forward[i] = NewNode;
            }else{
                if (p->forward[i]) p->next[i]++;
                else p->next[i] = 0;
            }
        }
        length++;
    }

    void insert_internal(SkipList<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && (*p->forward[i]->internal_key)[0]->leaf_key->value < (*key)[0]->leaf_key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++; // now += p->next[0]
        SLNode<T> *NewNode = new SLNode<T>(NULL, key, t);
        if (level < NewNode->level){
            NewNode->level = head->level = ++level;
            update[level] = head, pos[level] = 0;
        }
        for (int i = 0; i <= level; ++i){
            p = update[i];
            if (i <= NewNode->level){
                NewNode->forward[i] = p->forward[i];
                if (p->forward[i]) NewNode->next[i] = p->next[i] - (now - pos[i]) + 1;
                else NewNode->next[i] = 0;
                p->next[i] = now - pos[i];
                p->forward[i] = NewNode;
            }else{
                if (p->forward[i]) p->next[i]++;
                else p->next[i] = 0;
            }
        }
        length++;
    }


    bool erase_leaf(Value<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value < key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++;
        if (!p || p->leaf_key->value != key->value)
            return false;
        
        for (int i = 0; i <= level; ++i){
            if (update[i]->forward[i] != p){
                if (update[i]->forward[i]) update[i]->next[i]--;
                else update[i]->next[i] = 0;
            }else{
                update[i]->forward[i] = p->forward[i];
                update[i]->next[i] += p->next[i] - 1;
            }
        }
        delete p;
        while (level > 0 && head->forward[level] == NULL) level--;
        head->level = level;
        length--;
        return true;
    }

    bool erase_internal(SkipList<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && (*p->forward[i]->internal_key)[0]->leaf_key->value < (*key)[0]->leaf_key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++;
        if (!p || (*p->internal_key)[0]->leaf_key->value != (*key)[0]->leaf_key->value)
            return false;
        
        for (int i = 0; i <= level; ++i){
            if (update[i]->forward[i] != p){
                if (update[i]->forward[i]) update[i]->next[i]--;
                else update[i]->next[i] = 0;
            }else{
                update[i]->forward[i] = p->forward[i];
                update[i]->next[i] += p->next[i] - 1;
            }
        }
        delete p;
        while (level > 0 && head->forward[level] == NULL) level--;
        head->level = level;
        length--;
        return true;
    }
};
template <typename T> pair<SkipList<T>*, SkipList<T>*> splitlist(SkipList<T>* u, int rank){
    SkipList<T>* v = new SkipList<T>(u->t);
    SLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    SLNode<T> *p = u->head;
    int now = 0, level = u->level;
    for (int i = level; i >= 0; --i){
        while (p->forward[i] != NULL && now + p->next[i] < rank)
            now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    v->level = level, v->head->level = level;
    v->length = u->length - now + 1, u->length = now - 1;
    for (int i = 0; i <= level; ++i){
        p = update[i];
        v->head->forward[i] = p->forward[i];
        if (p->forward[i]) v->head->next[i] = p->next[i] - (now - pos[i]) + 1;
        else v->head->next[i] = 0;
        p->next[i] = 0;
        p->forward[i] = NULL;
    }
    return make_pair(u, v);
}
template <typename T> SkipList<T>* mergelist(SkipList<T>* u, SkipList<T>* v){
    SLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    SLNode<T> *p = u->head;
    int now = 0;
    for (int i = u->level; i >= 0; --i){
        while (p->forward[i] != NULL) now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    for (int i = 0; i <= v->level; ++i){
        if(i > u->level){
            u->head->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) u->head->next[i] = u->length + v->head->next[i];
            else u->head->next[i] = 0;
        }else{
            update[i]->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) update[i]->next[i] = (u->length - pos[i]) + v->head->next[i];
            else update[i]->next[i] = 0;
        }
        v->head->forward[i] = NULL;
    }
    u->level = max(u->level, v->level);
    u->head->level = u->level;
    u->length += v->length, v->length = 0;
    // delete v; // v will be deleted in B+ tree (when Node is deleted, Node->Value will also be deleted)
    return u;
}
/*--------------------- Node List---------------------- */

template <typename T> class NodeSkipList;
template <typename T> class NodeSLNode{
public:
    NodeSLNode<T> **forward;
    int *next;
    Node<T> *key;
    type t;
    int level;
    NodeSLNode<T>() {}
    ~NodeSLNode<T>() {
        delete [] forward;
        delete [] next;
    }
    NodeSLNode<T>(Node<T> *key) : key(key) {
        next = new int [MAXL + 1];
        forward = new NodeSLNode<T> *[MAXL + 1]; 
        for (int i = 0; i <= MAXL; ++i)
            forward[i] = NULL, next[i] = 0;
        level = RandomLevel();
    }
    int RandomLevel(){
        int lv = 0;
        int maxn = 1023;
        while (lv < MAXL && rand() % maxn < (int)(p * maxn)) ++lv;
        return lv;
    }
    friend class NodeSkipList<T>;
};
template <typename T> class NodeSkipList {
public:
    int level;
    int length;
    int size;
    type t;
    NodeSLNode<T> *head;
    NodeSkipList<T>() { head = new NodeSLNode<T>(0), size = 0, level = 0, length = 0; }
    ~NodeSkipList<T>() {
        NodeSLNode<T> *p = head;
        while(p){
            NodeSLNode<T> *q = p->forward[0];
            delete p, p = q;
        }   
    }
    NodeSLNode<T>* operator [](int rank){ // from 0
        // speed up internal_key to O(1)
        if(rank == 0) return head->forward[0];
        ++rank;
        NodeSLNode<T> *p = head;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->next[i] < rank)
                rank -= p->next[i], p = p->forward[i];
        }
        p = p->forward[0];
        return p;
    }
    void insert(Node<T> *key){
        NodeSLNode<T> *NewNode = new NodeSLNode<T>(key);
        if (level < NewNode->level)
            NewNode->level = head->level = ++level;        
        for (int i = 0; i <= level; ++i){
            head->next[i] = 1, head->forward[i] = NewNode;
            NewNode->next[i] = 0, NewNode->forward[i] = NULL;
        }
        length = 1;
    }
};
template <typename T> pair<NodeSkipList<T>*, NodeSkipList<T>*> SplitList(NodeSkipList<T>* u, int rank){
    NodeSkipList<T>* v = new NodeSkipList<T>();
    NodeSLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    NodeSLNode<T> *p = u->head;
    int now = 0, level = u->level;
    for (int i = level; i >= 0; --i){
        while (p->forward[i] != NULL && now + p->next[i] < rank)
            now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    v->level = level, v->head->level = level;
    v->length = u->length - now + 1, u->length = now - 1;
    for (int i = 0; i <= level; ++i){
        p = update[i];
        v->head->forward[i] = p->forward[i];
        if (p->forward[i]) v->head->next[i] = p->next[i] - (now - pos[i]) + 1;
        else v->head->next[i] = 0;
        p->next[i] = 0, p->forward[i] = NULL;
    }
    return make_pair(u, v);
}
template <typename T> NodeSkipList<T>* MergeList(NodeSkipList<T>* u, NodeSkipList<T>* v){
    NodeSLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    NodeSLNode<T> *p = u->head;
    int now = 0;
    for (int i = u->level; i >= 0; --i){
        while (p->forward[i] != NULL) now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    for (int i = 0; i <= v->level; ++i){
        if(i > u->level){
            u->head->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) u->head->next[i] = u->length + v->head->next[i];
            else u->head->next[i] = 0;
        }else{
            update[i]->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) update[i]->next[i] = (u->length - pos[i]) + v->head->next[i];
            else update[i]->next[i] = 0;
        }
        v->head->forward[i] = NULL;
    }
    u->level = max(u->level, v->level);
    u->head->level = u->level;
    u->length += v->length, v->length = 0;
    // delete v; // v will be deleted in B+ tree (when Node is deleted, Node->Value will also be deleted)
    return u;
}
/*--------------------- BPlusTree ---------------------- */
template <typename T> class Node{
public:
    Node<T> *fa, *nxt, *pre;
    NodeSkipList<T> *son;
    SkipList<T> *val;
    int sz;
    type t;
    Node<T>(type t, Node<T> *fa) : t(t), fa(fa){
        nxt = pre = NULL;
        val = new SkipList<T>(t);
        son = new NodeSkipList<T>();
    }
    Node<T>() {}
    ~Node<T>() {delete son, delete val; } // add this line will cause luogu P3369 RE
};
template <typename T> class BPlusTree{
private:
    int traverse(Node<T> *u, T val);
    int Traverse(Node<T> *u, T val);
    void insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val);
    void insert_leaf_by_id(Node<T> *u, int id, Value<T> *val);
    void insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val);
    SkipList<T>* delete_internal_right_by_id(Node<T> *u, int id);
    Value<T>* delete_leaf_by_id(Node<T> *u, int id);
    SkipList<T>* delete_internal_left_by_id(Node<T> *u, int id);
    void linkin(Node<T> *u, Node<T> *v);
    void linkout(Node<T> *u, Node<T> *v);
    void split(Node<T> *u, Node<T> *fa, int id);
    void merge(Node<T> *u, Node<T> *v, Node<T> *fa, int id);
    void fix(Node<T> *u, Node<T> *fa, int id);
    void clear(Node<T> *u){
        if(!u) return;
        NodeSLNode<T> *p = u->son->head->forward[0];
        while(p) 
            clear(p->key), p = p->forward[0];
        delete u, u = nullptr;
    }
    void destroy(Node<T> *u){
        while(u && u->t == INTERNAL) u = (*u->son)[0]->key;
        while(u){
            SLNode<T> *p = u->val->head->forward[0];
            while(p){
                delete p->leaf_key, p->leaf_key = nullptr;
                p = p->forward[0];
            }
            u = u->nxt;
        }
    }
public:
    Node<T> *root;
    void insert(Node<T> *u, Node<T> *fa, T val, int id);
    void erase(Node<T> *u, Node<T> *fa, T val, int id);
    int getrank(Node<T> *x, T val);
    T getval(Node<T> *x, int rank);
    int getpre(Node<T> *x, T val);
    int getnxt(Node<T> *x, T val);
    BPlusTree<T>() { root = NULL; }
    ~BPlusTree<T>() { destroy(root); clear(root); }
    void dfs(Node<T> *x) {
        assert(x!=NULL);
        cerr<<x->val<<"(type="<<(x->t==LEAF?"LEAF":"INTERNAL")<<",cnt="<<x->val->length;
        cerr<<")->[";
        SLNode<T> *p = x->val->head->forward[0];
        if(x->t == LEAF){
            while(p){
                if(p->leaf_key) cerr << p->leaf_key->value << " ";
                else cerr << "NULL ";
                p = p->forward[0];
            }
        }else{
            while(p){
                if((*p->internal_key)[0]) cerr << (*p->internal_key)[0]->leaf_key->value << " ";
                else cerr << "NULL ";
                p = p->forward[0];
            }
        }
        cerr<<"]\n";
        if(x->t==LEAF) return;
        NodeSLNode<T> *q = x->son->head->forward[0];
        while(q){
            dfs(q->key);
            q = q->forward[0];
        }
    }
};
template<typename T> int BPlusTree<T>::traverse(Node<T> *u, T val){
    int i = 0;
    if(u->t == LEAF) i = u->val->getrank_leaf(val) - 1;
    else i = u->val->getrank_internal(val) - 1;
    return i;
}
template<typename T> int BPlusTree<T>::Traverse(Node<T> *u, T val){
    int i = 0;
    if(u->t == LEAF) i = u->val->getrank_Leaf(val) - 1; // different
    else i = u->val->getrank_internal(val) - 1;
    return i;
}
template <typename T> void BPlusTree<T>::linkin(Node<T> *u, Node<T> *v){
    Node<T> *nxt = u->nxt; // double linked list, insert v
    v->nxt = u->nxt, v->pre = u, u->nxt = v;
    if(nxt) nxt->pre = v;
}
template <typename T> void BPlusTree<T>::linkout(Node<T> *u, Node<T> *v){
    Node<T> *nxt = v->nxt; // double linked list, delete v
    u->nxt = nxt, v->nxt = NULL, v->pre = NULL;
    if (nxt) nxt->pre = u;
}
template<typename T> void insert_son(Node<T> *u, Node<T> *s, int id){
    pair<NodeSkipList<T>*, NodeSkipList<T>* > p = SplitList(u->son, id + 1);
    NodeSkipList<T>* q = new NodeSkipList<T>();
    q->insert(s);
    u->son = MergeList(p.first, MergeList(q, p.second));
    delete p.second, p.second = nullptr;
    delete q, q = nullptr;
}
template<typename T> void delete_son(Node<T> *u, int id){
    pair<NodeSkipList<T>*, NodeSkipList<T>* > p = SplitList(u->son, id + 1);
    pair<NodeSkipList<T>*, NodeSkipList<T>* > q = SplitList(p.second, 2);
    u->son = MergeList(p.first, q.second);
    delete q.first, q.first = nullptr;
    delete q.second, q.second = nullptr;
}
template<typename T> void erase_val(Node<T> *u, int id){
    pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, id + 1);
    pair<SkipList<T>*, SkipList<T>* > q = splitlist(p.second, 2);
    u->val = mergelist(p.first, q.second);
    delete q.first, q.first = nullptr;
    delete q.second, q.second = nullptr;
}
template <typename T> void BPlusTree<T>::insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val){ 
    // insert val[id] and son[id + 1]
    insert_son(u, s, id + 1);
    u->val->insert_internal(val);
}
template <typename T> void BPlusTree<T>::insert_leaf_by_id(Node<T> *u, int id, Value<T> *val){ 
    // insert val[id]
    u->val->insert_leaf(val);
}
template <typename T> void BPlusTree<T>::insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val){ 
    // insert val[id] and son[id]
    insert_son(u, s, id);
    u->val->insert_internal(val);
}
template <typename T> Value<T>* BPlusTree<T>::delete_leaf_by_id(Node<T> *u, int id){ 
    // delete val[id]
    Value<T> *deleted_val = (*u->val)[id]->leaf_key;
    u->val->erase_leaf(deleted_val);
    return deleted_val;
}
template <typename T> SkipList<T>* BPlusTree<T>::delete_internal_right_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id + 1]
    SkipList<T> *deleted_val = ((*u->val)[id]) ? (*u->val)[id]->internal_key : NULL;
    delete_son(u, id + 1), erase_val(u, id);
    return deleted_val;
}
template <typename T> SkipList<T>* BPlusTree<T>::delete_internal_left_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id]
    SkipList<T> *deleted_val = ((*u->val)[id]) ? (*u->val)[id]->internal_key : NULL;
    delete_son(u, id), erase_val(u, id);
    return deleted_val;
}
template <typename T> void BPlusTree<T>::split(Node<T> *u, Node<T> *fa, int id){
    int mid = (u->t == LEAF) ? M / 2 : (M - 1) / 2;
    if (!fa){
        root = fa = new Node<T>(INTERNAL, NULL);
        fa->son->insert(u);
    }
    Node<T> *v = new Node<T>(u->t, fa);
    SkipList<T> *value = NULL;
    if (u->t == LEAF){
        pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, mid + 1);
        u->val = p.first;
        delete v->val, v->val = p.second;
        linkin(u, v);
        value = v->val;
    }else{
        value = (*u->val)[mid]->internal_key;
        pair<NodeSkipList<T>*, NodeSkipList<T>* > f = SplitList(u->son, mid + 2);
        u->son = f.first;
        delete v->son, v->son = f.second;
        pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, mid + 1);
        u->val = p.first;
        pair<SkipList<T>*, SkipList<T>* > q = splitlist(p.second, 2);
        delete q.first, q.first = nullptr;
        delete v->val, v->val = q.second;
    }
    insert_internal_right_by_id(fa, id, v, value);
}
template <typename T> void BPlusTree<T>::insert(Node<T> *u, Node<T> *fa, T val, int id){
    if (!root){
        root = new Node<T>(LEAF, NULL);
        insert_leaf_by_id(root, 0, new Value<T>(val, 1));
        return;
    }
    int i = traverse(u, val);
    if (u->t == INTERNAL) insert((*u->son)[i]->key, u, val, i);
    else{
        if (i < u->val->length && val == (*u->val)[i]->leaf_key->value){
            ++(*u->val)[i]->leaf_key->count;
            return;
        }
        insert_leaf_by_id(u, i, new Value<T>(val, 1));
    }
    if (u->val->length >= M) split(u, fa, id);
}
template <typename T> void BPlusTree<T>::merge(Node<T> *u, Node<T> *v, Node<T> *fa, int id){
    if (u->t == LEAF){
        u->val = mergelist(u->val, v->val);
        linkout(u, v);
    }else{
        insert_internal_right_by_id(u, u->val->length, (*v->son)[0]->key, (*fa->val)[id]->internal_key);
        pair<NodeSkipList<T> *, NodeSkipList<T> *> p = SplitList(v->son, 2);
        u->son = MergeList(u->son, p.second);
        delete p.second, p.second = nullptr;
        u->val = mergelist(u->val, v->val);   
    }
    delete_internal_right_by_id(fa, id); // what if this sentence is put in front of if (u->t == LEAF) sentence?
    delete v, v = nullptr;
}
template <typename T> void BPlusTree<T>::fix(Node<T> *u, Node<T> *fa, int id){
    if (!fa) return;
    if (id > 0 && (*fa->son)[id - 1]->key->val->length > m){ // borrow pre 
        Node<T> *v = (*fa->son)[id - 1]->key;
        if(u->t == LEAF){
            Value<T> *pre = (*v->val)[v->val->length - 1]->leaf_key;
            insert_leaf_by_id(u, 0, pre);
            delete_leaf_by_id(v, v->val->length - 1);
        }else{
            Node<T> *s = (*v->son)[v->val->length]->key;
            SkipList<T> *pre = (*fa->val)[id - 1]->internal_key;
            (*fa->val)[id - 1]->internal_key = (*v->val)[v->val->length - 1]->internal_key; // change parent
            insert_internal_left_by_id(u, 0, s, pre);
            delete_internal_right_by_id(v, v->val->length - 1);
        }
    }else if (id < fa->val->length && (*fa->son)[id + 1]->key->val->length > m){ // borrow nxt
        Node<T> *v = (*fa->son)[id + 1]->key;
        if(u->t == LEAF){
            Value<T> *nxt = (*v->val)[0]->leaf_key;
            delete_leaf_by_id(v, 0);               
            insert_leaf_by_id(u, u->val->length, nxt); 
        }else{
            Node<T> *s = (*v->son)[0]->key;
            SkipList<T> *nxt = (*fa->val)[id]->internal_key;
            (*fa->val)[id]->internal_key = (*v->val)[0]->internal_key; // change parent
            delete_internal_left_by_id(v, 0);               
            insert_internal_right_by_id(u, u->val->length, s, nxt); 
        }
    }else{
        if (id > 0) merge((*fa->son)[id - 1]->key, u, fa, id - 1);
        else merge(u, (*fa->son)[id + 1]->key, fa, id);
    }   
}
template <typename T> void BPlusTree<T>::erase(Node<T> *u, Node<T> *fa, T val, int id){
    int i = traverse(u, val);
    if (u->t == INTERNAL) erase((*u->son)[i]->key, u, val, i);
    else{
        if (i >= u->val->length || (*u->val)[i]->leaf_key->value != val) return; // not found
        if ((*u->val)[i]->leaf_key->count > 1){
            --(*u->val)[i]->leaf_key->count;
            return;
        }
        Value<T> *deleted_value = delete_leaf_by_id(u, i);
        delete deleted_value, deleted_value = nullptr;
    }
    if (u == root && !u->val->length){
        root = (*u->son)[0] ? (*u->son)[0]->key : NULL;
        delete u, u = nullptr;
        return;
    }
    if (u->val->length < m) fix(u, fa, id);
}
void solve(){
    scanf("%d", &n);
    BPlusTree<int> *S = new BPlusTree<int>();
    for (int i = 1; i <= n; ++i){
        int op, x;
        scanf("%d%d", &op, &x);
        o = i;
        if (op == 1){
            S->insert(S->root, NULL, x, 0);
        }else if (op == 2){
            S->erase(S->root, NULL, x, 0);
        }
    }
    delete S;
}
int main(){
    for(int i=1;i<=1;++i){
        clock_t start = clock();
        freopen("P3369_10.in", "r", stdin);
        freopen("P3369_10.ans", "w", stdout);
        solve();
        clock_t end = clock();
        cerr<<end-start<<endl;
    }
    return 0;
}

可以用这个代码测试一下对于 时的运行速度, 这份代码是会明显快于普通 B+ 树的