็ดขๅผ่ด่ดฃๅฟซ้ๅฐๆฃ็ดขๆฐๆฎ๏ผ่ไธ้่ฆๆ็ดขๆฐๆฎๅบ่กจไธญ็ๆฏไธ่ก๏ผ็ดขๅผ่ฟๆไพไบๅฟซ้็้ๆบ่ฎฟ้ฎไปฅๅ้ซๆๅฐ่ฎฟ้ฎๆๅบ่ฎฐๅฝใๅ ๆญค๏ผๅจ่ฟไธช็ผ็จไฝไธไธญ๏ผๆไปฌ้่ฆๅฎ็ฐๅบไบ B+ ๆ ็ๅจๆ็ดขๅผ็ปๆใ
CHECKPOINT #1
TASK #1 - B+TREE PAGES
ๅฎ็ฐไธไธช Page ็ฑปๆฅๅญๅจ B+ ๆ ็ๆฐๆฎ
b_plus_tree_page.cpp ็ๅฎ็ฐ
็ดๆฅๆ นๆฎๅฝๆฐ่ฆๆฑ่ฎพ็ฝฎๆ่ฟๅๅฏนๅบ็ๅญๆฎตๅณๅฏใ
IsRootPage ๅฝๆฐๆ นๆฎ parent_id_ ๆฏๅฆๆฏ INVALID_PAGE_ID ่ฟๅ true ๆ่
false
GetMinSize()๏ผ้่ฆๅบๅ 1๏ผๆ น็ป็นไธไธบๅถๅญ็ป็นใ2๏ผๆ น็ป็นใ3๏ผๅ
ถไป
b_plus_tree_internal_page.cpp ็ๅฎ็ฐ
MappingType ็็ฑปๅไธบ std::pair<KeyType, ValueType>๏ผๅฆไฝ่ทๅ็ฌฌ i ไธช MappingType๏ผ=> ๅจๅ
ถๅคดๆไปถๆไธไธช array ็ MappingType ๆฐ็ป๏ผarray[0] ่กจ็คบ่ฟๆฏไธไธชๅผนๆงๆฐ็ป๏ผ
ๆณจๆๆไบๅฝๆฐ้่ฆๅคๆญ index ๆฏๅฆๅๆณ๏ผไฝฟ็จ assert()
ๅฐ bpm ๅๅบ็้กต้ข่ฝฌๆขไธบ internal page/leaf page๏ผ้่ฆ๏ผ
b_plus_tree_internal_page.cpp
Page *page = buffer_pool_manager_->FetchPage(page_id);
assert(page != nullptr);
// ๅฐ page ่ฝฌๆ BPlusTreeInternalPage ็ฑป
BPlusTreeInternalPage *bpt_node = reinterpret_cast<BPlusTreeInternalPage *>(page->GetData());
// do something
buffer_pool_manager_->UnpinPage(bpt_node->GetPageId(), flag); // ๆฏๅฆไฟฎๆนไบ้กต้ข๏ผflag ไธบ true ๆ่
false
// ่ฟๅ index ่ฟไธชไฝ็ฝฎ็ Key
KeyType KeyAt(int index) const;
// ่ฎพ็ฝฎ index ่ฟไธชไฝ็ฝฎ็ Key = key
void SetKeyAt(int index, const KeyType &key);
// ่ฟๅ array ไธญ Value == value ็ไธๆ
int ValueIndex(const ValueType &value) const;
// ่ฟๅ index ่ฟไธชไฝ็ฝฎ็ Value
ValueType ValueAt(int index) const;
/**
* ไฝฟ็จไบๅๆ็ดขๆพๅฐ็ฌฌไธไธชๅคงไบ็ญไบ key ็ไธๆ ๏ผๆณจๆๅทฆๅบ้ดไป 1 ๅผๅง
*/
ValueType Lookup(const KeyType &key, const KeyComparator &comparator) const;
/**
* ๅฝๆๅ
ฅๅฏผ่ดไป leaf page ๅฐ root page ๆบขๅบๆถ๏ผๆไปฌๅบ่ฏฅๅๅปบไธไธชๆฐ็ root page๏ผ็ถๅๅๅงๅๅฎ
* array[0].first = old_value
* ๆณจ๏ผ่ฟไธชๆนๆณๅช่ฝ็ฑ InsertIntoParent() ่ฐ็จ(b_plus_tree.cpp)
*/
void PopulateNewRoot(const ValueType &old_value, const KeyType &new_key, const ValueType &new_value);
/**
* ๅจ old_value ไฝ็ฝฎไนๅๆๅ
ฅไธไธช <Key, Value>
* ๆณจ๏ผๅฏไปฅไฝฟ็จ ValueIndex ๆฅๆพๅฐ old_value ็ไธๆ ๏ผๆๅ
ฅๅๅซๅฟไบๆดๆฐ size_
*/
int InsertNodeAfter(const ValueType &old_value, const KeyType &new_key, const ValueType &new_value);
/**
* ๅ ้ค array[index] ่ฟไธชๅ
็ด ๏ผๅ้ข็ๅ
็ด ๅๅ็งปไธไฝ๏ผ
* ๆณจ๏ผๅ ้คๅ
็ด ๅๅซๅฟไบๆดๆฐ size_
*/
void Remove(int index);
/**
* ๅ ้ค internal page ไธญ็ๅฏไธไธไธชๅ
็ด ๏ผๅนถ่ฟๅๅฎ็ value
*/
ValueType RemoveAndReturnOnlyChild();
Split and Merge utility methods
/**
* Split: ็ฑไบๆๅ
ฅไธไธช <K, V> ๅฏผ่ด page full๏ผๅ ๆญคๅฐ่ฟไธ้กตไธๅ็ <K, V> ็งปๅฐ "recipient" ้กต
*/
void MoveHalfTo(BPlusTreeInternalPage *recipient, BufferPoolManager *buffer_pool_manager);
// ่พ
ๅฉๅฝๆฐ๏ผๆง่ก <K, V> ๆท่ดๆไฝ๏ผๅๆถๆดๆฐ่ฟไบ่ขซ็งปๅจ่็น็ parent_page_id
void CopyNFrom(MappingType *items, int size, BufferPoolManager *buffer_pool_manager);
/**
* Merge: ๅฐ่ฏฅ้กต็ๆๆ <K, V> ็งปๅฐ "recipient" ้กต
*/
void MoveAllTo(BPlusTreeInternalPage *recipient, const KeyType &middle_key, BufferPoolManager *buffer_pool_manager);
/****** Redistribute ******/
/**
* ๅๅฝๅ้กต็็ฌฌไธไธชๆๆ็ <K, V>
* ๅฐ <middle_key, ValueAt(0)> ็งปๅฐ "recipient" page ็ๆๅไธไธช slot
* ็ถๅๆดๆฐ parent page ็ middl_key
*/
void MoveFirstToEndOf(BPlusTreeInternalPage *recipient, const KeyType &middle_key,
BufferPoolManager *buffer_pool_manager);
/**
* ๅฐ pair ๆทปๅ ๅฐ array ๆซๅฐพ๏ผ็ถๅๆดๆฐ่ฟไธช entry ็ parent page id
*/
void CopyLastFrom(const MappingType &pair, BufferPoolManager *buffer_pool_manager);
/**
* ๅๅฝๅ้กต็ๆๅไธไธชๆๆ็ <K, V>
* ๅฐ <middle_key, ValueAt(size - 1)> ็งปๅฐ "recipient" page ็็ฌฌไธไธช slot
* ็ถๅๆดๆฐ parent page ็ middl_key
*/
void MoveLastToFrontOf(BPlusTreeInternalPage *recipient, const KeyType &middle_key,
BufferPoolManager *buffer_pool_manager);
/**
* ๅฐ pair ๆทปๅ ๅฐ array ็็ฌฌไธไธชๆๆไฝ็ฝฎ๏ผ็ถๅๆดๆฐ่ฟไธช entry ็ parent page id
*/
void CopyFirstFrom(const MappingType &pair, BufferPoolManager *buffer_pool_manager);
ๆณจ๏ผMerge ๅ Redistribute ็ๅ ไธชๅฝๆฐๅฏไปฅๆพๅจ CP2 ไธญๅฎๆ
b_plus_tree_Leaf_page.cpp ็ๅฎ็ฐ
// ่ฟๅๅฝๅ page ็ไธไธไธช page ็ page id
page_id_t GetNextPageId() const;
// ่ฎพ็ฝฎ next_page_id
void SetNextPageId(page_id_t next_page_id);
// ่ฟๅ array[index] ไฝ็ฝฎ็ Key
KeyType KeyAt(int index) const;
// ่ฟๅ array ไธญ็ฌฌไธไธชๅคงไบ็ญไบ key ็ index
int KeyIndex(const KeyType &key, const KeyComparator &comparator) const;
// ่ฟๅ array[index]
const MappingType &GetItem(int index);
InsertionใSearchใDelete
/**
* ๅฐ <key, value> ๆๅ
ฅๅฐๅถๅญ่๏ผ่ฟๅๆๅ
ฅๅ็ page size
* 1. ๆพๅฐ้่ฆๆๅ
ฅๅฐไฝ็ฝฎ๏ผๅคๆญ่ฏฅไฝ็ฝฎ็ key ๆฏๅฆ็ญไบ "key"๏ผ็ฑไบๅชๆฏๆ unique key๏ผๆไปฅ็ธ็ญๆถ็ดๆฅ่ฟๅ page size
* 2. ๆง่กๆๅ
ฅๆไฝ
* 3. ๆดๆฐ size_
*/
int Insert(const KeyType &key, const ValueType &value, const KeyComparator &comparator);
/**
* ๆฅๆพ key ๆฏๅฆๅจๅถๅญ่็นไธญใๅฆๆๅจ๏ผๅฐ key ๅฏนๅบ็ Value ๅญๅจ "value" ไธญ๏ผ่ฟๅ true๏ผๅฆๅ่ฟๅ false
*/
bool Lookup(const KeyType &key, ValueType *value, const KeyComparator &comparator) const;
/**
* ๅจๅถๅญ่็นไธญๅ ้ค key
* ๅฆๆ key ไธๅญๅจ๏ผ็ดๆฅ่ฟๅ page size
* ๅฆๅๅ ้ค่ฟไธช key๏ผๆดๆฐ size_๏ผ่ฟๅ page size
*/
int RemoveAndDeleteRecord(const KeyType &key, const KeyComparator &comparator);
Split and Merge utility methods
// ็ฑปไผผไบ BPlusTreeInternalPage ็ๅฎ็ฐ
void MoveHalfTo(BPlusTreeLeafPage *recipient);
void CopyNFrom(MappingType *items, int size);
void MoveAllTo(BPlusTreeLeafPage *recipient);
void MoveFirstToEndOf(BPlusTreeLeafPage *recipient);
void CopyLastFrom(const MappingType &item);
void MoveLastToFrontOf(BPlusTreeLeafPage *recipient);
void CopyFirstFrom(const MappingType &item);
ๅๆงฝ๏ผไธ้ข็ๅไธช Move ๅฝๆฐๅ BPlusTreeInternalPage ็ฑปไธญ็ๅๅๅฝๆฐๅๆฐไธไธ่ด๏ผๅฏผ่ดๅ้ข Split ไธญ่ฐ็จๆฅ้ใไนๅๆๅฐ่ฟไธ็ปๅฝๆฐ็ๅๆฐๆนไธบไธ่ดๆ็ผ่ฏ้่ฟใ
TASK #2.A - B+TREE DATA STRUCTURE (INSERTION & POINT SEARCH)
FindLeafPage ่ฟไธชๅฝๆฐๆฏๆฅๆพใๆๅ
ฅใๅ ้คๆไฝ็ๅบ็ก๏ผๅฎๆฏๆพๅฐ key ๆๅจ็ๅถๅญ่็น๏ผleftMost = true ๆถ่กจ็คบ่ฟๅ B+ ๆ ไธญๆๅทฆ่พน็ๅถๅญ่็น
ๅจ InsertIntoLeaf ๅฝๆฐไธญ๏ผๅฆๆๆๅ
ฅๅ๏ผๅถๅญ็ป็นๅ
ๅซ็ <K, V> ไธชๆฐ็ญไบ GetMaxSize()๏ผๆญคๆถๅฐฑ่ฆ่ฟ่กๅ่ฃ
ๅจ InsertIntoParent ๅฝๆฐไธญ๏ผๆๅ
ฅๅ็ไธญ้ด็ป็นๅ
ๅซ็ <K, V> ไธชๆฐๅคงไบ GetMaxSize() ๆ่ฟ่กๅ่ฃ
CHECKPOINT #2
TASK #3 - INDEX ITERATOR
่ฟญไปฃๅจ็ๅฎ็ฐไธป่ฆๆฏๆณจๆไปไนๆถๅ็ปๆ๏ผ๏ผๅฐ่พพๆๅณ่พนๅถๅญ่็น็ๆๅไธไธช slot๏ผไปฅๅๅฎ็ฐ ++ ๆไฝๆถ๏ผๅค็ไธไธไธชๅถๅญ่็น็ๆ
ๅตใ
TASK #4 - CONCURRENT INDEX
coalesce ๆ่
redistribute ๆไฝๆถ้่ฆ่ทๅพ sibling ็ W Latch
ไธบไบไฟๆค root_page_id_๏ผ้็จไบ่ๆ้กต v_root_page๏ผๅไธไธช mutex_
/**
* ๅจ b_plus_tree class ้ๅฎไนไธไธชๆๅๅ้ Page v_root_page ๅ std::mutex mutex_
* ๆฏๆฌก FindLeafPage ็ๆถๅๅ
ไฝฟ็จ mutex_๏ผๅๆ &v_root_page ๅ ่ฟ transaction->page_set_
* mutex_ ็้ๆพๅๅณไบ root page ๆฏๅฆๅฎๅ
จ
*/
Crabbing Locking๏ผ่งฃ้้กบๅบๅๅ ้้กบๅบ่ฆไธ่ด๏ผ
/**
* 1. ๅฆๆ op = search๏ผ้ฃไน่ทๅๅฐๅญ่็น็ RLatch ๅ๏ผๅบ่ฏฅ้ๆพไนๅๆทปๅ ๅฐ page_set_ ็้กต้ข
* 2. ๅฆๆ op = insert๏ผ้ฃไน่ทๅๅฐๅญ่็น็ WLatch ๅ๏ผๆฃๆฅ่ฏฅ page ๆฏๅฆๅฎๅ
จ(size < max_size_)๏ผๆฏ็่ฏ้ๆพไนๅๆๆ้กต้ข
* 3. ๅฆๆ op = delete๏ผ้ฃไน่ทๅๅฐๅญ่็น็ WLatch ๅ๏ผๆฃๆฅ่ฏฅ page ๆฏๅฆๅฎๅ
จ(size > min_size_)๏ผๆฏ็่ฏ้ๆพไนๅๆๆ้กต้ข
* ๆๅๆทปๅ ่ฏฅ้กตๅฐ page_set_
*/
INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::LockThisPage(int op, Page *page, Transaction *transaction) {}
/**
* 1. ้ๆพ page_set_ ไธญ็ R/W Latch
* 2. ๅ ้คไฟๅญ็ delete_page_set_ ไธญ็้กต้ข๏ผ็ถๅๆธ
็ฉบ delete_page_set_
*/
INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::UnlockPrevPage(int op, Transaction *transaction, bool is_dirty) {}
ๆต่ฏ/้ช่ฏ/ๆๅ
cd build
make b_plus_tree_insert_test
./test/b_plus_tree_insert_test
make b_plus_tree_delete_test
./test/b_plus_tree_delete_test
make b_plus_tree_concurrent_test
./test/b_plus_tree_concurrent_test
make format
make check-lint
make check-clang-tidy
zip project2-submission.zip src/include/buffer/lru_replacer.h src/buffer/lru_replacer.cpp \
src/include/buffer/buffer_pool_manager.h src/buffer/buffer_pool_manager.cpp \
src/include/storage/page/b_plus_tree_page.h src/storage/page/b_plus_tree_page.cpp \
src/include/storage/page/b_plus_tree_internal_page.h src/storage/page/b_plus_tree_internal_page.cpp \
src/include/storage/page/b_plus_tree_leaf_page.h src/storage/page/b_plus_tree_leaf_page.cpp \
src/include/storage/index/b_plus_tree.h src/storage/index/b_plus_tree.cpp \
src/include/storage/index/index_iterator.h src/storage/index/index_iterator.cpp
็ถๅๅๅพ https://www.gradescope.com ๆไบคไปฃ็