写在前面

弃坑宣言（？）

由于15445课程周期长，lab资源都是C++的，用Java实现对我来说属实有点艰难，写得很痛苦，故决定弃坑，做完b+树就放弃了，写得也不一定对，慎看

lab1：CMU15445 BufferPool Java版本 | 62bit的秘密基地

课程相关资源

我看的是2019年的课，实验做的是2020年的

课程视频可以在油管和B站找到，这里我推荐simniso这个团队，他们翻译得很好

实验一说明地址：Project #1 - Buffer Pool | CMU 15-445/645 :: Intro to Database Systems (Fall 2020)

实验官方Git hub地址：cmu-db/bustub: The BusTub Relational Database Management System (Educational) (github.com)

具体实现

BPlusTreeParentPage

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
package storage.page;

import java.io.Serializable;
import java.util.ArrayList;

public class BPlusTreeParentPage <K extends Comparable<K>>  extends Page implements Serializable  {
    public enum PageType {
        INTERNAL, LEAF;
    }
    //private int size;//当前有多少键值对
    private int maxSize;//最大键值对数量
    private int parentPageId;//

    private PageType pageType;
    //protected K[] index;
    protected ArrayList<K> keys;
    //protected int countKeys;



    public int getMaxSize() {
        return maxSize;
    }

    public void setMaxSize(int maxSize) {
        this.maxSize = maxSize;
    }

    public int getParentPageId() {
        return parentPageId;
    }

    public void setParentPageId(int parentPageId) {
        this.parentPageId = parentPageId;
    }

//    public K[] getIndex() {
//        return index;
//    }
//
//    public void setIndex(K[] index) {
//        this.index = index;
//    }


    public ArrayList<K> getKeys() {
        return keys;
    }

    public void setKeys(ArrayList<K> keys) {
        this.keys = keys;
    }

    public PageType getPageType() {
        return pageType;
    }

    public void setPageType(PageType pageType) {
        this.pageType = pageType;
    }

    public int getMinSize() {
        return maxSize / 2;
    }

//    public int getCountKeys() {
//        return countKeys;
//    }
//
//    public void setCountKeys(int countKeys) {
//        this.countKeys = countKeys;
//    }

    //二分查找
//    protected int binarySearch(K key, int l, int r){
//
//        int mid = 0;
//        int res = -1;
//        while(l <= r){
//            mid = l + ((r - l) >> 1);
//            if(index[mid].compareTo(key) > 0){
//                r = mid - 1;
//            }else if(index[mid].compareTo(key) < 0){
//                l = mid + 1;
//            }
//            res = mid;
//        }
//        return res;
//    }

}

BPlusTreeInternalPage

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
package storage.page;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class BPlusTreeInternalPage<K extends Comparable<K>> extends BPlusTreeParentPage<K> implements Serializable {
    private ArrayList<Integer> children;

    /**
     *  有效的K总是比children少一个
     *
     *              K      K      K
     *        child  child  child  child
     *  设keys的第一个key为无效
     */

    ////////////////////////////////////////////////////////////////////////////////////////////////////////
    public BPlusTreeInternalPage(K key,int leftChild, int rightChild, int pageId, int parentPageId, int maxSize){
        setPageId(pageId);
        setParentPageId(parentPageId);
        setPageType(PageType.INTERNAL);
        setMaxSize(maxSize);
        children = new ArrayList<>();
//        index =(K[]) Array.newInstance(key.getClass().componentType(), maxSize);
//        index[1] = key;
        keys.add(null);//第一个key无效
        keys.add(key);
        //countKeys = 1;
        children.add(leftChild);
        children.add(rightChild);
    }
    public BPlusTreeInternalPage(List<K> ks, List<Integer> children, int pageId, int parentPageId, int maxSize){
        setPageId(pageId);
        setParentPageId(parentPageId);
        setPageType(PageType.INTERNAL);
        setMaxSize(maxSize);
        this.children = new ArrayList<>(children);
        keys = new ArrayList<>(ks);
//        index =(K[]) Array.newInstance(ks.getClass().componentType(), maxSize);
//        for(int i = 1; i < ks.length; i++){
//            index[i] = ks[i];
//        }
        //countKeys = ks.length;
    }
    //////////////////////////////////////////////////////////////////////////////////////////////////////////


    /**
     * 查
     *
     * 查询key
     * @param key 要查找的值
     * @return 含有key的child的页号
     */
    public int select(K key){
        //int index = binarySearch(key, 1, countKeys);
        int selectIndex = Collections.binarySearch(keys, key);
        if(selectIndex < 0){
            selectIndex = -selectIndex - 1;
            return children.get(selectIndex);
            //return children.get(countKeys + 1);
        }else{
            return children.get(selectIndex + 1);
        }
        //else return children.get(index - 1);
    }

    /**
     * 增
     *
     * 有时一个叶子节点会分裂成两个
     * 这时就得插入一条新记录来对应新的叶子节点
     * @param key
     */
    public void insert(K key, int pageId) {
        //int insertIndex = binarySearch(key, 1, countKeys);//二分法找到要插入的位置
        int insertIndex = Collections.binarySearch(keys, key);
//        for(int i = countKeys; i >= insertIndex; i--){
//            index[i + 1] = index[i];
//        }
//        index[insertIndex] = key;
        insertIndex = -insertIndex - 1;
        keys.add(insertIndex, key);
        children.add(insertIndex + 1, pageId);
        //countKeys++;
    }

    /**
     * 删
     *
     * 有时某个叶子节点与其他叶子节点合并了
     * 这时就要删掉对应这个叶子节点的记录
     */
    public void delete(K key, int pageId) {
        //int deleteIndex = binarySearch(key, 1, countKeys);
        int deleteIndex = Collections.binarySearch(keys, key);
        if(deleteIndex >= 0) keys.remove(key);
        children.remove(Integer.valueOf(pageId));
        //countKeys--;
    }

    /**
     * 改
     *
     * 有时要重新分配叶子节点的记录(达到每个页都是半满的状态)
     * 有些叶子节点的最小值发生了变化
     * 这时有些记录需要改变
     * @param oldKey 发生变化的child在变化以前的第一条记录的key
     */
    public void update(K oldKey, K newKey){
        //int updateIndex = binarySearch(oldKey, 1, countKeys);
        //int pageId = children.get(updateIndex);
        int updateIndex = Collections.binarySearch(keys, oldKey);
        if(updateIndex < 0) return;
        keys.remove(oldKey);
        //insert(newKey,pageId);
        keys.add(updateIndex, oldKey);
    }

    public ArrayList<Integer> getChildren() {
        return children;
    }

    public void setChildren(ArrayList<Integer> children) {
        this.children = children;
    }

    public int size(){return keys.size();}

}

BPlusTreeLeafPage

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
package storage.page;

import common.Config;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class BPlusTreeLeafPage <K extends Comparable<K>, V>
        extends BPlusTreeParentPage<K> implements Serializable {
    private int nextPageId;
    private int prevPageId;
    private final ArrayList<V> values;

    public BPlusTreeLeafPage(K key, V value, int pageId, int parentPageId, int maxSize) {
        setPageId(pageId);
        setParentPageId(parentPageId);
        setPageType(PageType.LEAF);
        setNextPageId(Config.INVALID_PAGE_ID);
        setPrevPageId(Config.INVALID_PAGE_ID);
        setMaxSize(maxSize);
        values = new ArrayList<>();
        values.add(value);
        //index[1] = key;
        keys = new ArrayList<>();
        keys.add(key);
        //countKeys = 1;
    }

    public BPlusTreeLeafPage(List<K> ks, List<V> vs, int pageId, int parentPageId, int maxSize) {
        setPageId(pageId);
        setParentPageId(parentPageId);
        setPageType(PageType.LEAF);
        setNextPageId(Config.INVALID_PAGE_ID);
        setPrevPageId(Config.INVALID_PAGE_ID);
        setMaxSize(maxSize);
        values = new ArrayList<>(vs);
        keys = new ArrayList<>(ks);
//        index =(K[]) Array.newInstance(ks.getClass().componentType(), maxSize);
//        for(int i = 0; i < ks.length; i++){
//            index[i] = ks[i];
//        }
        //countKeys = ks.size();
    }
    public int getPrevPageId() {
        return this.prevPageId;
    }

    public void setPrevPageId(int prevPageId) {
        this.prevPageId = prevPageId;
    }

    public int getNextPageId() {
        return this.nextPageId;
    }

    public void setNextPageId(int nextPageId) {
        this.nextPageId = nextPageId;
    }

    public ArrayList<V> getValues() {
        return this.values;
    }

    public int size(){return keys.size();}
    //增
    public boolean insert(K key, V value) {
        //int insertIndex = binarySearch(key, 0, countKeys - 1);//二分法找到要插入的位置
        int insertIndex = Collections.binarySearch(keys, key);
        //if(index[insertIndex] == key) return false;
        if(keys.get(insertIndex) == key) return false;
//        for(int i = countKeys - 1; i >= insertIndex; i--){
//            index[i + 1] = index[i];
//        }
        insertIndex = -insertIndex - 1;
        keys.add(insertIndex, key);
        //index[insertIndex] = key;
        values.add(insertIndex, value);
        //countKeys++;
        return true;
    }
    //查
    public V select(K key) {
        //int selectIndex = binarySearch(key, 0, countKeys - 1);
        int selectIndex = Collections.binarySearch(keys, key);
        if(selectIndex < 0) return null;
        return values.get(selectIndex);
    }
    //改
    public boolean update(K key, V value){
        //int updateIndex = binarySearch(key, 0, countKeys - 1);

        int updateIndex = Collections.binarySearch(keys, key);
        //if(index[updateIndex] == null) return false;
        if(updateIndex < 0) return true;
        values.set(updateIndex, value);
        return true;
    }

    //删
    public void delete(K key) {
        //int deleteIndex = binarySearch(key, 0, countKeys - 1);
        int deleteIndex = Collections.binarySearch(keys, key);
        //if(deleteIndex == -1) return;
        if(deleteIndex < 0) return;
//        for(int i = deleteIndex; i <countKeys; i++){
//            index[i] = index[i + 1];
//        }
        keys.remove(deleteIndex);
        values.remove(deleteIndex);
        //countKeys--;
    }

}

BPlusTreeIndex

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
package storage.index;

import buffer.Block;
import buffer.BufferPoolManager;
import storage.page.BPlusTreeInternalPage;
import storage.page.BPlusTreeLeafPage;
import storage.page.BPlusTreeParentPage;


import java.util.ArrayList;

import static common.Config.INVALID_PAGE_ID;


@SuppressWarnings("unchecked")
public class BPlusTreeIndex <K extends Comparable<K>, V> {
    private final String indexName;
    private final BufferPoolManager bufferPoolManager;
    int leafMaxSize;
    int internalMaxSize;
    BPlusTreeParentPage<K> root;
    int level;
    public BPlusTreeIndex(String indexName, BufferPoolManager bufferPoolManager, int leafMaxSize, int internalMaxSize) {
        this.indexName = indexName;
        this.bufferPoolManager = bufferPoolManager;
        this.leafMaxSize = leafMaxSize;
        this.internalMaxSize = internalMaxSize;
        this.level = 0;
        root = null;
    }
    public boolean isEmpty_(){
        return level == 0;
    }

    public void startNewTree(K key, V value){
        Block block = bufferPoolManager.findFreeBlock();
        if(block == null){
            throw  new RuntimeException("out of memory");
        }
        root = new BPlusTreeLeafPage<>(
                key,
                value,
                block.frame.getPageId(),
                INVALID_PAGE_ID,
                leafMaxSize
        );
        level++;
    }


    public BPlusTreeLeafPage<K, V> findLeafPage(K key){
        int curLevel = level;
        if(level == 0) return null;
        if(level == 1) return (BPlusTreeLeafPage<K, V>) bufferPoolManager.fetchPg(root.getPageId());
        BPlusTreeInternalPage<K> curPage = (BPlusTreeInternalPage<K>)bufferPoolManager.fetchPg(root.getPageId());
        while(curLevel > 1){
            int childPageId = curPage.select(key);
            bufferPoolManager.unpinPg(curPage.getPageId(),false);
            curPage = (BPlusTreeInternalPage<K>) bufferPoolManager.fetchPg(childPageId);
            curLevel--;
        }
        bufferPoolManager.unpinPg(curPage.getPageId(),false);
        return (BPlusTreeLeafPage<K, V>) bufferPoolManager.fetchPg(curPage.select(key));
    }


    //点查询
    public V select(K key){
        return findLeafPage(key).select(key);
    }



    public void insert(K key, V value){
        if(isEmpty_()){
            startNewTree(key, value);
            return;
        }
        BPlusTreeLeafPage<K, V> curPage = findLeafPage(key);
        if(!curPage.insert(key, value)) bufferPoolManager.unpinPg(curPage.getPageId(), false);
        if(curPage.getValues().size() == leafMaxSize) splitLeafPage(curPage);
    }



    public void splitLeafPage(BPlusTreeLeafPage<K, V> leftPage){
        Block block = bufferPoolManager.findFreeBlock();//找一个空闲的页
        int from = leafMaxSize / 2;
        int to = leafMaxSize;
        K splitKey = leftPage.getKeys().get(from);//新页的第一个key
        BPlusTreeLeafPage<K, V> rightPage = new BPlusTreeLeafPage<>(//新建一个页
                leftPage.getKeys().subList(from, to),//subList是左闭右开的
                leftPage.getValues().subList(from, to),
                block.frame.getPageId(),
                leftPage.getParentPageId(),
                leafMaxSize
        );
        block.frame = rightPage;//替换
        //删除重复的内容
        leftPage.getValues().subList(from, to).clear();
        leftPage.getKeys().subList(from, to).clear();

        //设置指针
        rightPage.setPrevPageId(leftPage.getPageId());
        rightPage.setNextPageId(leftPage.getNextPageId());
        leftPage.setNextPageId(rightPage.getPageId());

        if(rightPage.getParentPageId() != INVALID_PAGE_ID){//有父页
            //找到父页
            BPlusTreeInternalPage<K> parent = (BPlusTreeInternalPage<K>) bufferPoolManager.fetchPg(rightPage.getParentPageId());
            //插入新页的记录
            parent.insert(splitKey, rightPage.getPageId());
            //如果父页满了
            if(parent.getKeys().size() == internalMaxSize) slipInternalPage(parent);
            else bufferPoolManager.unpinPg(parent.getPageId(), true);
        }else{//没有父页
            Block newParentBlock = bufferPoolManager.findFreeBlock();//找一个空页
            BPlusTreeInternalPage<K> parent = new BPlusTreeInternalPage<>(
                    splitKey,
                    leftPage.getPageId(),
                    rightPage.getPageId(),
                    newParentBlock.frame.getPageId(),//将id设置为block对应的id
                    INVALID_PAGE_ID,
                    internalMaxSize
            );
            newParentBlock.frame = parent;//替换
            rightPage.setParentPageId(parent.getPageId());
            leftPage.setParentPageId(parent.getPageId());
            level++;//层数增加
            root = parent;//更新根节点
        }
        bufferPoolManager.unpinPg(leftPage.getPageId(), true);
    }

    public void slipInternalPage(BPlusTreeInternalPage<K> leftPage){
        Block block = bufferPoolManager.findFreeBlock();//获取一个空闲缓冲页
        if(block == null){
            throw  new RuntimeException("out of memory");
        }
        int from = internalMaxSize / 2;
        int to = internalMaxSize;
        K splitKey = leftPage.getKeys().get(from);

        BPlusTreeInternalPage<K> rightPage = new BPlusTreeInternalPage<>(
                leftPage.getKeys().subList(from, to),
                leftPage.getChildren().subList(from, to),
                block.frame.getPageId(),
                leftPage.getParentPageId(),
                internalMaxSize
        );
        leftPage.getChildren().subList(from, to).clear();
        rightPage.getKeys().set(0,null);//第一个key无效
        block.frame = rightPage;
        if(rightPage.getParentPageId() != INVALID_PAGE_ID){
            BPlusTreeInternalPage<K> parent = (BPlusTreeInternalPage<K>) bufferPoolManager.fetchPg(rightPage.getParentPageId());
            parent.insert(splitKey, rightPage.getPageId());
            if(parent.getKeys().size() == internalMaxSize) slipInternalPage(parent);//递归
            else bufferPoolManager.unpinPg(parent.getPageId(), true);
        }else{
            Block newParentBlock = bufferPoolManager.findFreeBlock();
            BPlusTreeInternalPage<K> parent = new BPlusTreeInternalPage<>(
                    splitKey,
                    leftPage.getPageId(),
                    rightPage.getPageId(),
                    newParentBlock.frame.getPageId(),
                    INVALID_PAGE_ID,
                    internalMaxSize
            );
            newParentBlock.frame = parent;
            rightPage.setParentPageId(parent.getPageId());
            leftPage.setParentPageId(parent.getPageId());
            level++;
            root = parent;
        }
        bufferPoolManager.unpinPg(leftPage.getPageId(), true);
    }

    public void delete(K key){
        if(isEmpty_()) return;
        BPlusTreeLeafPage<K, V> curPage = findLeafPage(key);
        curPage.delete(key);
        if(curPage == root) return;//如果是根节点说明只有一个节点,没什么好调整的
        if(curPage.size() < leafMaxSize / 2){
            BPlusTreeLeafPage<K, V> nextPage = (BPlusTreeLeafPage<K, V>) bufferPoolManager.fetchPg(curPage.getNextPageId());
            BPlusTreeLeafPage<K, V> prevPage = (BPlusTreeLeafPage<K, V>) bufferPoolManager.fetchPg(curPage.getPrevPageId());
            if(prevPage != null){
                if(prevPage.size() < leafMaxSize / 2){//可以合并
                    mergeLeaf(curPage, prevPage);
                }else{//合并不了就借
                    borrowPrevLeaf(curPage, prevPage);
                }
            }else if(nextPage != null){
                if(nextPage.size() < leafMaxSize / 2){
                    mergeLeaf(nextPage, curPage);
                }else{
                    borrowNextLeaf(curPage, nextPage);
                }
            }
        }
    }

    //用prev吞并cur
    public void mergeLeaf(BPlusTreeLeafPage<K, V> cur, BPlusTreeLeafPage<K, V> prev){
        prev.getKeys().addAll(cur.getKeys());
        prev.getValues().addAll(cur.getValues());
        prev.setNextPageId(cur.getNextPageId());
        BPlusTreeInternalPage<K> parent = (BPlusTreeInternalPage<K>) bufferPoolManager.fetchPg(cur.getParentPageId());
        parent.delete(cur.getKeys().get(0), cur.getPageId());
        if(parent.size() < internalMaxSize / 2){
            if(parent == root){
                if(parent.size() == 0) {
                    root = prev;
                    prev.setParentPageId(INVALID_PAGE_ID);

                }
            }else{
                BPlusTreeInternalPage<K> grandparent = (BPlusTreeInternalPage<K>) bufferPoolManager.fetchPg(parent.getParentPageId());
                int index = grandparent.getChildren().indexOf(parent.getPageId());
                BPlusTreeInternalPage<K> preParent = null;
                BPlusTreeInternalPage<K> nextParent = null;
                if(index != 0){
                    int preParentId = grandparent.getChildren().get(index - 1);
                    preParent = (BPlusTreeInternalPage<K>)bufferPoolManager.fetchPg(preParentId);
                }
                if(index != grandparent.getChildren().size() - 1){
                    int nextParentId = grandparent.getChildren().get(index + 1);
                    nextParent = (BPlusTreeInternalPage<K>)bufferPoolManager.fetchPg(nextParentId);
                }
                if(preParent != null){
                    if(preParent.size() < internalMaxSize / 2) mergeInternal(parent, preParent);
                    else {
                        borrowPrevInternal(parent, preParent);
                        bufferPoolManager.unpinPg(preParent.getPageId(), true);
                        if(nextParent != null) bufferPoolManager.unpinPg(nextParent.getPageId(), false);
                    }
                }else if(nextParent != null){
                    if(nextParent.size() < internalMaxSize / 2) mergeInternal(nextParent, parent);
                    else {
                        borrowNextInternal(parent, nextParent);
                        bufferPoolManager.unpinPg(nextParent.getPageId(), true);
                    }
                }
            }
        }
        bufferPoolManager.unpinPg(parent.getPageId(), true);
        bufferPoolManager.deletePg(cur.getPageId());
        bufferPoolManager.unpinPg(prev.getPageId(), true);
    }

    //用prev吞并cur
    private void mergeInternal(BPlusTreeInternalPage<K> cur, BPlusTreeInternalPage<K> prev) {
        //用cur第一个child的第一个key替换cur的第一个无效的key
        BPlusTreeLeafPage<K, V> child = (BPlusTreeLeafPage<K, V>) bufferPoolManager.fetchPg(cur.getChildren().get(0));
        cur.getKeys().set(0, child.getKeys().get(0));

        prev.getKeys().addAll(cur.getKeys());
        prev.getChildren().addAll(cur.getChildren());
        BPlusTreeInternalPage<K> parent = (BPlusTreeInternalPage<K>) bufferPoolManager.fetchPg(cur.getParentPageId());
        parent.delete(cur.getKeys().get(0), cur.getPageId());
        if(parent.size() < internalMaxSize / 2){
            if(parent == root){
                if(parent.size() == 0) {
                    root = prev;
                    prev.setParentPageId(INVALID_PAGE_ID);
                }
            }else{
                BPlusTreeInternalPage<K> grandparent = (BPlusTreeInternalPage<K>) bufferPoolManager.fetchPg(parent.getParentPageId());
                int index = grandparent.getChildren().indexOf(parent.getPageId());
                BPlusTreeInternalPage<K> preParent = null;
                BPlusTreeInternalPage<K> nextParent = null;
                if(index != 0){
                    int preParentId = grandparent.getChildren().get(index - 1);
                    preParent = (BPlusTreeInternalPage<K>)bufferPoolManager.fetchPg(preParentId);
                }
                if(index != grandparent.getChildren().size() - 1){
                    int nextParentId = grandparent.getChildren().get(index + 1);
                    nextParent = (BPlusTreeInternalPage<K>)bufferPoolManager.fetchPg(nextParentId);
                }
                if(preParent != null){
                    if(preParent.size() < internalMaxSize / 2) mergeInternal(parent, preParent);
                    else {
                        borrowPrevInternal(parent, preParent);
                        bufferPoolManager.unpinPg(preParent.getPageId(), true);
                        if(nextParent != null)bufferPoolManager.unpinPg(nextParent.getPageId(), false);
                    }
                }else if(nextParent != null){
                    if(nextParent.size() < internalMaxSize / 2) mergeInternal(nextParent, parent);
                    else {
                        borrowNextInternal(parent, nextParent);
                        bufferPoolManager.unpinPg(nextParent.getPageId(), true);
                    }
                }
            }
        }
        bufferPoolManager.unpinPg(parent.getPageId(), true);
        bufferPoolManager.deletePg(cur.getPageId());
        bufferPoolManager.unpinPg(prev.getPageId(), true);
    }


    public void borrowPrevLeaf(BPlusTreeLeafPage<K, V> cur, BPlusTreeLeafPage<K, V> prev){
        //重新分配两个页的内容,让两个页的size几乎相等
        int borrowSize = prev.size() - (cur.size() + prev.size()) / 2;
        int from = prev.size() - borrowSize + 1;
        int to = prev.size() + 1;
        K oldKey = cur.getKeys().get(0);
        ArrayList<K> newKeys = new ArrayList<>(prev.getKeys().subList(from, to));
        ArrayList<V> newValues = new ArrayList<>(prev.getValues().subList(from, to));
        newKeys.addAll(cur.getKeys());
        newValues.addAll(cur.getValues());
        cur.getKeys().clear();
        cur.getValues().clear();
        cur.getKeys().addAll(newKeys);
        cur.getValues().addAll(newValues);
        K newKey = cur.getKeys().get(0);
        BPlusTreeInternalPage<K> parent = (BPlusTreeInternalPage<K>) bufferPoolManager.fetchPg(cur.getParentPageId());
        parent.update(oldKey, newKey);
        bufferPoolManager.unpinPg(parent.getPageId(), true);
    }

    public void borrowNextLeaf(BPlusTreeLeafPage<K, V> cur, BPlusTreeLeafPage<K, V> next){
        //重新分配两个页的内容,让两个页的size几乎相等
        int borrowSize = next.size() - (cur.size() + next.size()) / 2;
        int from = 0;
        int to = borrowSize + 1;
        cur.getKeys().addAll(next.getKeys().subList(from, to));
        cur.getValues().addAll(next.getValues().subList(from, to));
        K oldKey = next.getKeys().get(0);
        next.getKeys().subList(from, to).clear();
        next.getValues().subList(from, to).clear();
        K newKey = cur.getKeys().get(0);
        BPlusTreeInternalPage<K> parent = (BPlusTreeInternalPage<K>) bufferPoolManager.fetchPg(next.getParentPageId());
        parent.update(oldKey, newKey);
        bufferPoolManager.unpinPg(parent.getPageId(), true);
    }

    private void borrowPrevInternal(BPlusTreeInternalPage<K> cur, BPlusTreeInternalPage<K> prev) {
        int borrowSize = prev.size() - (cur.size() + prev.size()) / 2;
        int from = prev.size() - borrowSize + 1;
        int to = prev.size();
        K oldKey = cur.getKeys().get(0);
        ArrayList<K> newKeys = new ArrayList<>(prev.getKeys().subList(from, to));
        ArrayList<Integer> newChildren = new ArrayList<>(prev.getChildren().subList(from, to));
        newKeys.addAll(cur.getKeys());
        newChildren.addAll(cur.getChildren());
        cur.getKeys().clear();
        cur.getChildren().clear();
        cur.getKeys().addAll(newKeys);
        cur.getChildren().addAll(newChildren);
        K newKey = cur.getKeys().get(0);
        BPlusTreeInternalPage<K> parent = (BPlusTreeInternalPage<K>) bufferPoolManager.fetchPg(cur.getParentPageId());
        parent.update(oldKey, newKey);
        bufferPoolManager.unpinPg(parent.getPageId(), true);
    }

    private void borrowNextInternal(BPlusTreeInternalPage<K> cur, BPlusTreeInternalPage<K> next) {
        int borrowSize = next.size() - (cur.size() + next.size()) / 2;
        int from = 0;
        int to = borrowSize + 1;
        BPlusTreeLeafPage<K, V> child = (BPlusTreeLeafPage<K, V>) bufferPoolManager.fetchPg(next.getChildren().get(0));
        next.getKeys().set(0, child.getKeys().get(0));
        cur.getKeys().addAll(next.getKeys().subList(from, to));
        K oldKey = next.getKeys().get(0);
        next.getKeys().subList(from, to).clear();
        next.getKeys().set(0, null);//第一个key设为无效
        BPlusTreeInternalPage<K> parent = (BPlusTreeInternalPage<K>) bufferPoolManager.fetchPg(next.getParentPageId());
        parent.update(oldKey, next.getKeys().get(1));
        bufferPoolManager.unpinPg(parent.getPageId(), true);
    }
}