Split an internal page to make room for new entries and recursively split its parent page as needed to accommodate a new entry. The new entry for the parent should have a key matching the middle key in the original internal page being split (this key is "pushed up" to the parent). The child pointers
(TransactionId tid, Map<PageId, Page> dirtypages, BTreeInternalPage page, Field field)
| 339 | * @throws TransactionAbortedException |
| 340 | */ |
| 341 | public BTreeInternalPage splitInternalPage(TransactionId tid, Map<PageId, Page> dirtypages, |
| 342 | BTreeInternalPage page, Field field) |
| 343 | throws DbException, IOException, TransactionAbortedException { |
| 344 | // some code goes here |
| 345 | // |
| 346 | // Split the internal page by adding a new page on the right of the existing |
| 347 | // page and moving half of the entries to the new page. Push the middle key up |
| 348 | // into the parent page, and recursively split the parent as needed to accommodate |
| 349 | // the new entry. getParentWithEmtpySlots() will be useful here. Don't forget to update |
| 350 | // the parent pointers of all the children moving to the new page. updateParentPointers() |
| 351 | // will be useful here. Return the page into which an entry with the given key field |
| 352 | // should be inserted. |
| 353 | //1. 将当前page的后半部分放入新page |
| 354 | int half = page.getNumEntries()/2; |
| 355 | BTreeInternalPage newPage = (BTreeInternalPage) getEmptyPage(tid, dirtypages, BTreePageId.INTERNAL); |
| 356 | Iterator<BTreeEntry> iterator = page.reverseIterator(); |
| 357 | while(iterator.hasNext() && half>0){ |
| 358 | BTreeEntry next = iterator.next(); |
| 359 | page.deleteKeyAndRightChild(next); |
| 360 | newPage.insertEntry(next); |
| 361 | half--; |
| 362 | } |
| 363 | //2. 分裂完，中间的entry插入父节点。注意up节点要在原page中删除，并设置左右子节点。 |
| 364 | BTreeEntry up = iterator.next(); |
| 365 | page.deleteKeyAndRightChild(up); |
| 366 | up.setLeftChild(page.getId()); |
| 367 | up.setRightChild(newPage.getId()); |
| 368 | //这里父节点可能还会分裂获取 |
| 369 | BTreeInternalPage parentPage = getParentWithEmptySlots(tid, dirtypages, page.getParentId(), field); |
| 370 | parentPage.insertEntry(up); |
| 371 | page.setParentId(parentPage.getId()); |
| 372 | newPage.setParentId(parentPage.getId()); |
| 373 | |
| 374 | //3. 设置newPage子节点的父节点指向 |
| 375 | updateParentPointers(tid,dirtypages,newPage); |
| 376 | |
| 377 | //4. 增加脏页 |
| 378 | dirtypages.put(parentPage.getId(),parentPage); |
| 379 | dirtypages.put(newPage.getId(),newPage); |
| 380 | dirtypages.put(page.getId(),page); |
| 381 | //5. 返回要插入field的页 |
| 382 | if (field.compare(Op.GREATER_THAN_OR_EQ, up.getKey())) { |
| 383 | return newPage; |
| 384 | } |
| 385 | return page; |
| 386 | } |
| 387 | |
| 388 | /** |
| 389 | * Method to encapsulate the process of getting a parent page ready to accept new entries. |