Split a leaf page to make room for new tuples and recursively split the parent node as needed to accommodate a new entry. The new entry should have a key matching the key field of the first tuple in the right-hand page (the key is "copied up"), and child pointers pointing to the two leaf pages resul
(TransactionId tid, Map<PageId, Page> dirtypages, BTreeLeafPage page, Field field)
| 265 | * @throws TransactionAbortedException |
| 266 | */ |
| 267 | public BTreeLeafPage splitLeafPage(TransactionId tid, Map<PageId, Page> dirtypages, BTreeLeafPage page, Field field) |
| 268 | throws DbException, IOException, TransactionAbortedException { |
| 269 | // some code goes here |
| 270 | // |
| 271 | // Split the leaf page by adding a new page on the right of the existing |
| 272 | // page and moving half of the tuples to the new page. Copy the middle key up |
| 273 | // into the parent page, and recursively split the parent as needed to accommodate |
| 274 | // the new entry. getParentWithEmtpySlots() will be useful here. Don't forget to update |
| 275 | // the sibling pointers of all the affected leaf pages. Return the page into which a |
| 276 | // tuple with the given key field should be inserted. |
| 277 | //1. 将当前page的后半部分放入新page |
| 278 | int half = page.getNumTuples()/2; |
| 279 | BTreeLeafPage newPage = (BTreeLeafPage)getEmptyPage(tid,dirtypages,BTreePageId.LEAF); |
| 280 | Iterator<Tuple> iterator = page.reverseIterator(); |
| 281 | while(iterator.hasNext() && half>0){ |
| 282 | Tuple next = iterator.next(); |
| 283 | //这里要先删除在插入，就很坑 |
| 284 | page.deleteTuple(next); |
| 285 | newPage.insertTuple(next); |
| 286 | --half; |
| 287 | } |
| 288 | //2. 获取当前要插入的父节点，并插入新节点 |
| 289 | Tuple up = iterator.next(); |
| 290 | BTreeInternalPage parentPage = getParentWithEmptySlots(tid, dirtypages, page.getParentId(), field); |
| 291 | BTreeEntry insertEntry = new BTreeEntry(up.getField(keyField), page.getId(), newPage.getId()); |
| 292 | parentPage.insertEntry(insertEntry); |
| 293 | //3. 设置节点间的关系 |
| 294 | // page newPage rightSibling |
| 295 | if(page.getRightSiblingId()!=null){ |
| 296 | BTreeLeafPage right = (BTreeLeafPage) getPage(tid, dirtypages, page.getRightSiblingId(), Permissions.READ_WRITE); |
| 297 | right.setLeftSiblingId(newPage.getId()); |
| 298 | dirtypages.put(right.getId(),right); |
| 299 | } |
| 300 | newPage.setRightSiblingId(page.getRightSiblingId()); |
| 301 | newPage.setLeftSiblingId(page.getId()); |
| 302 | page.setRightSiblingId(newPage.getId()); |
| 303 | |
| 304 | page.setParentId(parentPage.getId()); |
| 305 | newPage.setParentId(parentPage.getId()); |
| 306 | |
| 307 | //4. 增加脏页 |
| 308 | dirtypages.put(parentPage.getId(),parentPage); |
| 309 | dirtypages.put(page.getId(),page); |
| 310 | dirtypages.put(newPage.getId(),newPage); |
| 311 | |
| 312 | //5. 返回要插入field的页 |
| 313 | if (field.compare(Op.GREATER_THAN_OR_EQ, up.getField(keyField))) { |
| 314 | return newPage; |
| 315 | } |
| 316 | return page; |
| 317 | } |
| 318 | |
| 319 | /** |
| 320 | * Split an internal page to make room for new entries and recursively split its parent page |