๐Expand2: Delete
1. ๅ ้ค็ฎๆณๅ็
cmu่ฟ้็ปไบ ๆผ็คบ็ฝ็ซ
ๅ ณไบๆดไธชๅ ้ค็ฎๆณ็่ฎฒ่งฃ่ฟไธช ppt ่ฎฒ็ๆฏ่พๆธ ๆฅ
็ฎๆณๆ่ฟฐ่งไธ่กจ
ไปฅๅไธๅพ
2 ๅ ้ค็ฎๆณๅฎ็ฐ
2.1 ็ฌฌไธๆญฅ : ๆพๅฐๅ
ๅซ็ฎๆ key็leaf node่ฟ่กๅ ้ค
ๆพๅฐๅ ๅซ็ฎๆ key็ leaf node
ๅฆๆๅฝๅๆฏ็ฉบๆ ๅ็ซๅณ่ฟๅ
ๅฆๅๅ ๆพๅฐ่ฆๅ ้ค็keyๆๅจ็page
้ๅ่ฐ็จ
RemoveAndDeleteRecordๅจๅถpageไธ็ดๆฅๅ ้คkeyๅผ
INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::Remove(const KeyType &key, Transaction *transaction) {
{
// ่ฟไธชไธ้จ้ๅฏนไบ้ๅนถๅ็delete
Page *page = FindLeafPage(key, false);
LeafPage *leafPage = reinterpret_cast<LeafPage*>(page->GetData()); //pined leafPage
leafPage->RemoveAndDeleteRecord(key,comparator_);RemoveAndDeleteRecordๅฝๆฐ
่ฟ้ๅฎ็ฐ่ถๆฅ่ถๅLeveldbๆฏๆไนๅไบใใ
ๅฉ็จ
KeyIndexๅฝๆฐๅฎ็ฐ็็็ฎๅใ
INDEX_TEMPLATE_ARGUMENTS
int B_PLUS_TREE_LEAF_PAGE_TYPE::RemoveAndDeleteRecord(const KeyType &key, const KeyComparator &comparator) {
int pos = KeyIndex(key, comparator);
if (pos < GetSize() && comparator(array_[pos].first, key) == 0) {
for (int j = pos + 1; j < GetSize(); j++) {
array_[j - 1] = array_[j];
}
IncreaseSize(-1);
}
return GetSize();
}ไนๅๅฐฑๆฏๅฏนไบๅ ้ค็ๅค็๏ผไธป่ฆๆไธคไธชไธไธชๆฏๅๅนถ๏ผไธไธชๅฐฑๆฏredistributeใๅ ทไฝๆต็จ่งไธ
2.2 Coalesceๅฎ็ฐๆต็จ
ๅถๅญ็ป็นๅ
ๅ
ณ้ฎๅญไธชๆฐๅฐไบๆๅฐๅผๅไธๆง่กใ่ฐ็จๅ ้ค็ๆ ธๅฟๅฝๆฐCoalesceAndRedistribute
ไธ้ขๆฏCoalesceAndRedistribute็้ป่พ
1.ๅฆๆๅฝๅ็ป็นๆฏๆ น่็นๅ่ฐ็จAdjustRoot(node)
AdjustRoot(node)่ฟ้็ๆ็คบ็ปไบๅ ถๅฎ่ฟไธชๅฝๆฐๅฐฑ้ๅฏนไธค็งๆ ๅต
Case1 : old_root_nodeๆฏๅ ้จ็ป็น๏ผไธๅคงๅฐไธบ1๏ผ่กจ็คบๅ ้จ็ป็นๅ ถๅฎๅทฒ็ปๆฒกๆkeyไบใๆไปฅ่ฆๆๅฎ็ๅญฉๅญๆดๆฐๆๆฐ็ๆ น่็น
Case2 : old_root_nodeๆฏๅถๅญ็ป็นใไธๅคงๅฐไธบ0๏ผ็ดๆฅๅ ไบๅฐฑๅฅฝใ
ๅฆๅไธ้่ฆๆpage่ขซๅ ้ค๏ผๅ็ดๆฅreturn flase
INDEX_TEMPLATE_ARGUMENTS
bool BPLUSTREE_TYPE::AdjustRoot(BPlusTreePage *old_root_node) {
// case 1 old_root_node (internal node) has only one size
if (!old_root_node->IsLeafPage() && old_root_node->GetSize() == 1) {
InternalPage *old_root_page = reinterpret_cast<InternalPage *>(old_root_node);
page_id_t new_root_page_id = old_root_page->adjustRootForInternal();
root_page_id_ = new_root_page_id;
UpdateRootPageId(0);
Page *new_root_page = buffer_pool_manager_->FetchPage(new_root_page_id);
BPlusTreePage *new_root = reinterpret_cast<BPlusTreePage *>(new_root_page->GetData());
new_root->SetParentPageId(INVALID_PAGE_ID);
buffer_pool_manager_->UnpinPage(new_root_page_id, true);
return true;
}
// case 2 : all elements deleted from the B+ tree
if (old_root_node->IsLeafPage() && old_root_node->GetSize() == 0) {
root_page_id_ = INVALID_PAGE_ID;
UpdateRootPageId(0);
return true;
}
return false;
}2.ๅฆๅๅ
ๅคๆญๆฏๅฆ่ฆ่ฟ่กCoalesce
่ฟ้่ฆๆพๅ ๅผ็ป็น่ฟ่กๅๅนถ๏ผๅฆๆๆปก่ถณๅๅนถ่ฆๆฑ็่ฏ
1. ๅคๆญๆฏๅฆๆปก่ถณๅๅนถ่ฆๆฑ
่ฟ้ๅฉ็จไธไธช่พ
ๅฉๅฝๆฐ่ฟ่กๅคๆญใๅฆๆไธ่ถ
่ฟๆๅคงsizeๅฐฑๅฏไปฅๅๅนถ
INDEX_TEMPLATE_ARGUMENTS
template <typename N>
bool BPLUSTREE_TYPE::IsCoalesce(N *nodeL, N *nodeR) {
// maxSize consider InternalPage and LeafPage
return nodeL->GetSize() + nodeR->GetSize() <= maxSize(nodeL);
}โ ๏ธ ๅๅนถๅฝๆฐๆฏๅ็ดๆฅๅ้ฉฑ่ฟ่กๅๅนถ๏ผไนๅฐฑๆฏๅๅฎๅทฆ่พน็node่ฟ่กๅๅนถ
2. ๅคๆญๅทฆ่พน็pageๆฏๅฆ่ฝ่ฟ่กๅๅนถ
// firstly find from left
if (left_sib_index >= 0) {
page_id_t sibling_pid = parent->ValueAt(left_sib_index);
Page *sibling_page = buffer_pool_manager_->FetchPage(sibling_pid); // pined sibling_page
N *sib_node = reinterpret_cast<N *>(sibling_page->GetData());
if (IsCoalesce(node, sib_node)) {
// coalesce
// unpin node and deleted node
bool del_parent = Coalesce(&sib_node, &node, &parent, cur_index, transaction);
// unpin sibling page
buffer_pool_manager_->UnpinPage(sibling_pid, true);
// unpin parent page;
buffer_pool_manager_->UnpinPage(parent_pid, true);
if (del_parent) {
buffer_pool_manager_->DeletePage(parent_pid);
}
return false; // node is merged into sib, and already deleted
}
buffer_pool_manager_->UnpinPage(sibling_pid, false); // unpin sibling page
}3. ๅฆๅๅคๆญๅณ่พนๆฏๅฆ่ฝ่ฟ่กๅๅนถ
// secondly find from right
if (right_sib_index < parent->GetSize()) {
page_id_t sibling_pid = parent->ValueAt(right_sib_index);
Page *sibling_page = buffer_pool_manager_->FetchPage(sibling_pid); // pined sibling_page
N *sib_node = reinterpret_cast<N *>(sibling_page->GetData());
if (IsCoalesce(node, sib_node)) {
// coalesce
// unpin right sib and deleted right sib
bool del_parent =
Coalesce(&node, &sib_node, &parent, cur_index, transaction);
buffer_pool_manager_->UnpinPage(node->GetPageId(), true); // unpin sibling page
buffer_pool_manager_->UnpinPage(parent_pid, true); // unpin parent page;
if (del_parent) {
buffer_pool_manager_->DeletePage(parent_pid);
}
return false; // node is merged into sib, and already deleted
}
buffer_pool_manager_->UnpinPage(sibling_pid, false); // unpin sibling page
}4. Coaleceๅฝๆฐ็ๅฎ็ฐ
ๅฎ็ฐไนๅๅ ็ไธคๅผ ๅพ
ๅจๅๅนถไนๅ๏ผ็ถไบฒ็ป็นๅฟ ้กป่ฆๆดๆฐใๅ ไธบ็งปๅจๆไฝๅฏผ่ดไบไนๅ็ถ็ป็น็ๆ้ๅ็ไบ้่ฏฏใ่ฟ้ไผๆถๅๅฐ็ถไบฒ็ป็นๆฏๅฆ้่ฆๅ ้ค็ๆ ๅต
ๅ ทไฝๆ ๅต่งไธๅพ
ๅฏ่ฝ็ฑไบๅถๅญ็ป็น็ๅๅนถๆไฝ๏ผๅฏผ่ด็ถไบฒ็ป็นๅๆnull็ฉบ็ป็นใๆ่
่ฏดๆฏๅ
ถไธๆปก่ถณๆๅฐ็ป็นไธชๆฐ่ฆๆฑใ่ฟๆ ทๅฐฑ่ฆๅฏน็ถไบฒ็ป็น่ฟ่กๅค็๏ผ่ฟไธชๆถๅๆฏ็ถไบฒ็ป็นไนๅฏไปฅ่ฟ่กๅๅนถ๏ผ่ฟไธชๆถๅๅๆฅ็็ถไบฒ็ป็นๅฐฑๆ ไบใๅๅนถไนๅ็็ปๆๅฆไธๅพ:
่ฎฐๅพ้ๅฝๅค็ๅฐฑๅฅฝ
INDEX_TEMPLATE_ARGUMENTS
template <typename N>
bool BPLUSTREE_TYPE::Coalesce(N **neighbor_node, N **node, BPlusTreeInternalPage<KeyType,
page_id_t, KeyComparator> **parent, int index, Transaction *transaction) {
// Assume that *neighbor_node is the left sibling of *node
// Move entries from node to neighbor_node
if ((*node)->IsLeafPage()) {
LeafPage *leaf_node = reinterpret_cast<LeafPage *>(*node);
LeafPage *leaf_neighbor = reinterpret_cast<LeafPage *>(*neighbor_node);
leaf_node->MoveAllTo(leaf_neighbor);
leaf_neighbor->SetNextPageId(leaf_node->GetNextPageId());
} else {
InternalPage *internal_node = reinterpret_cast<InternalPage *>(*node);
InternalPage *internal_neighbor = reinterpret_cast<InternalPage *>(*neighbor_node);
internal_node->MoveAllTo(internal_neighbor, (*parent)->KeyAt(index), buffer_pool_manager_);
}
buffer_pool_manager_->UnpinPage((*node)->GetPageId(), true);
buffer_pool_manager_->DeletePage((*node)->GetPageId());
(*parent)->Remove(index);
// If parent is underfull, recursive operation
if ((*parent)->GetSize() < minSize(*parent)) {
return CoalesceOrRedistribute(*parent, transaction);
}
return false;
}5. ๅถๅญ็ป็นๅๅ ้จ็ป็นๅฏนๅบ็ไธคไธชMoveAllToๅฝๆฐ
่ฟไธชๅฝๆฐๅฐฑไธๅไบใๅฎ็ฐๆฏ่พ็ฎๅ๏ผๅฏไธ่ฆๆณจๆ็ๅฐฑๆฏๅฏนไบๅ ้จ็ป็น็ๅๅนถๆไฝ๏ผ่ฆๆ้่ฆๅ ้ค็ๅ ้จ็ป็น็ๅถๅญ็ป็น่ฝฌ็งป่ฟๅปใไนๅฐฑๆฏ่ฆๆไธ้ข่ฟๆ ท็ไธ่ก
recipient->array_[recipient->GetSize()].first = middle_key;3. Redistributeๆต็จ
ๅฝ็ถไนๅฏไปฅๅ ็ไธไธ็ฎๆณ็คบๆๅพใ
ไธๅพๆฏๅฏนๅถๅญ็ป็น็็Redistributeๅฝๆฐ
่ฟ้ๅจ็งปๅจ็ๆถๅๅช่ฆ่ฎฐๅพๆดๆฐ็ถไบฒๅฏนๅบindex็keyๅผๅฐฑๅฅฝไบใ
็ถ่ๅฏนไบๅ ้จ็ป็นๅๅนถไธๆฏ่ฟไน็ฎๅ็ๆ ๅตไบใๅ ้จ็ป็นๅฏไปฅ็ดๆฅไปๅฎ็ๅ ๅผ็ป็นcopy็ถๅไฟฎๆนๅ ถๆ น่็นๅ๏ผ่ฟๆพ็ถไธๅ็ใ
ๅฏนไบ่ฟ็งๆ ๅต็ๅค็ๅฏไปฅ่งไธๅพ
ๅ ๆญคๆดไธชredistributeๆๆถๅ็ๅ็งๆ ๅตๅฐฑๅฆไธ
ๅๅถๅญ็ป็นๅทฆ่พนๅ
ๅๅถๅญ็ป็นๅณ่พนๅ
ๅ ้จ็ป็นๅทฆ่พนๅ
ๅ ้จ็ป็นๅณ่พนๅ
1. ๅฏนไบๅถๅญ็ป็นๅๅทฆ่พนๅ็ๆ
ๅต
ๅฅฝไบๅ ้ค็ฎๆณๅทฒ็ปๅฎ็ฐไบใ้ฆๅ ๆไปฌๅฏไปฅ้่ฟtestๅฝๆฐ
cd build
make b_plus_tree_delete_test
./test/b_plus_tree_delete_test --gtest_also_run_disabled_tests
็ถๅๆไปฌ่ชๅทฑๅไธไบtestใ่ฟ้ๆๅฐฑๆฟไธไธชไพๅญๆฅ็
ๆๅ ฅ10ใ5ใ7ใ4ใ9ๅพๅฐไธๅพๆฏๆญฃ็กฎ็๐
็ถๅๅ ้คๅ ็ด 7
ๅฏไปฅๅ็ฐๆฏๅฎๅ จๆญฃ็กฎ็ๅฅฝไบใ็ฌฌไบ้จๅๅฐฑๅฎๆไบใไธ้ขๅฐฑๆฏๆๅไธ้จๅๅฏนไบ๐็ๅฎ็ฐๅ่ฟญไปฃๅจ็ๅฎ็ฐ
Last updated