Expand
Project 2
1. ๅฎ้ชไป็ป
็ฌฌไธไธชๆๅ็น---ๅฎ็ฐb+ๆ ็ๅบๆฌ็ปๆใๆๅ ฅใๆ็ดขๆไฝ
ๆณจๆ่ฟ้ๆฒกๆ่่ๆๅ็น2็ๅนถๅ้ฎ้ข๏ผๆไปฅๅฏนไบๅ ้ใ่งฃ้ๅไบ็ฉ้ฝๆฒกๆ่่ใ
็ฌฌไบไธชๆๅ็น--ๅฎ็ฐb+ๆ ็ๅ ้คๆไฝใ็ดขๅผ่ฟญไปฃๅจๅๅฏนๅนถๅ่ฎฟ้ฎ็ๆฏๆ
Task 1 B+TREE PAGES#
ๆจ้่ฆๅฎ็ฐไธไธช้กต้ข็ฑปๆฅๅญๅจB+ๆ ็ๆฐๆฎใ
B+ Tree Parent Page
B+ Tree Internal Page
B+ Tree Leaf Page
1. B+ Tree Parent Page
่ฟๆฏๅ
้จ้กตๅๅถ้กต้ฝ็ปงๆฟ็็ถ็ฑป๏ผๅฎๅชๅ
ๅซไธคไธชๅญ็ฑปๅ
ฑไบซ็ไฟกๆฏใ็ถ้กต้ข่ขซๅๅไธบๅฆไธ่กจๆ็คบ็ๅ ไธชๅญๆฎตใ
*B+Tree Parent Page Content
page_type_
4
Page Type (internal or leaf)
lsn_
4
Log sequence number (Used in Project 4)
size_
4
Number of Key & Value pairs in page
max_size_
4
Max number of Key & Value pairs in page
parent_page_id_
4
Parent Page Id
page_id_
4
Self Page Id
ๅฟ
้กปๅจๆๅฎ็ๆไปถไธญๅฎ็ฐ็ถ้กตใๅช่ฝไฟฎๆนๅคดๆไปถ(src/include/storage/page/b_plus_tree_page.h) ๅๅ
ถๅฏนๅบ็ๆบๆไปถ (src/storage/page/b_plus_tree_page.cpp).
่ฟ้้ฝๆฏไธไบ็ฎๅ็setใgetๅฐฑไธๅๅบๆฅไบ
IsRootPageๅฝๆฐๆ นๆฎparent_id_ๆฏๅฆๆฏINVALID_PAGE_ID่ฟๅtrueๆ่falseGetMinSize()๏ผ้่ฆๅบๅ 1๏ผๆ น็ป็นไธไธบๅถๅญ็ป็น 2๏ผๆ น็ป็น 3๏ผๅ ถไป
2. B+TREE INTERNAL PAGE
ๅ ้จ้กตไธๅญๅจไปปไฝๅฎ้ ๆฐๆฎ๏ผ่ๆฏๅญๅจๆๅบ็mไธช้ฎๆก็ฎๅm + 1ไธชๆ้๏ผไน็งฐไธบpage_id๏ผใ
็ฑไบๆ้็ๆฐ้ไธ็ญไบ้ฎ็ๆฐ้๏ผๅ ๆญคๅฐ็ฌฌไธไธช้ฎ่ฎพ็ฝฎไธบๆ ๆ๏ผๅนถไธๆฅๆพๆนๆณๅบๅง็ปไป็ฌฌไบไธช้ฎๅผๅงใ
ไปปไฝๆถๅ๏ผๆฏไธชๅ ้จ้กต้ข่ณๅฐๆไธๅๅทฒๆปกใ ๅจๅ ้คๆ้ด๏ผๅฏไปฅๅฐไธคไธชๅๆปก้กต้ขๅๅนถไธบๅๆณ้กต้ข๏ผๆ่ ๅฏไปฅๅฐๅ ถ้ๆฐๅ้ ไปฅ้ฟๅ ๅๅนถ๏ผ่ๅจๆๅ ฅๆ้ด๏ผๅฏไปฅๅฐไธไธชๅฎๆด้กต้ขๅไธบไธค้จๅใ
ไฝ ๅช่ฝไฟฎๆนๅคดๆไปถ(src/include/storage/page/b_plus_tree_internal_page.h) ๅๅฏนๅบ็ๆบๆไปถ(src/page/b_plus_tree_internal_page.cpp).
3. B+TREE LEAF PAGE
ๅถๅญ้กตๅญๅจๆๅบ็mไธช้ฎๆก็ฎ(key)ๅmไธชๅผๆก็ฎ(value)ใ
ๅฎ็ฐไธญ๏ผๅผๅช่ฝๆฏ็จไบๅฎไฝๅฎ้
ๅ
็ปๅญๅจไฝ็ฝฎ็64ไฝrecord_id๏ผ่ฏทๅ้
src / include / common / rid.hไธญๅฎไน็RID็ฑปใ
ๅถๅญ้กตไธๅ ้จ้กตๅจ้ฎ/ๅผๅฏน็ๆฐ้ไธๅ ทๆ็ธๅ็้ๅถ๏ผๅนถไธๅบ่ฏฅ้ตๅพช็ธๅ็ๅๅนถ๏ผ้ๆฐๅ้ ๅๆๅๆไฝใ
ๅฟ
้กปๅจๆๅฎ็ๆไปถไธญๅฎ็ฐๅ
้จ้กตใ ไป
ๅ
่ฎธไฟฎๆนๅคดๆไปถ๏ผsrc / include / storage / page / b_plus_tree_leaf_page.h๏ผๅๅ
ถ็ธๅบ็ๆบๆไปถ๏ผsrc / storage / page / b_plus_tree_leaf_page.cpp๏ผใ
โผ๏ธ ้่ฆ็KeyIndexๅฝๆฐ
่ฟไธชๅฝๆฐๅฏไปฅ่ฟๅ็ฌฌไธไธช>=ๅฝๅkeyๅผ็็ผๅทใ่ฟไธชๅจๆๅ
ฅ็ๆถๅ็ปๅธธไผ็จๅฐ๏ผ่ฟๆ ทๅฐฑๅฏไปฅ่ฎฉไปฃ็ ้ๅคๅฉ็จ๏ผๅจLevelDBไธญไนๆ็ฑปไผผ็ๆไฝใ
้่ฆๆ็คบ๏ผๅฐฝ็ฎกๅถๅญ้กตๅๅ ้จ้กตๅ ๅซ็ธๅ็ฑปๅ็้ฎ๏ผไฝๅฎไปฌๅฏ่ฝๅ ทๆไธๅ็ฑปๅ็ๅผ๏ผๅ ๆญคๅถๅญ้กตๅๅ ้จ้กต็ๆๅคงๅคงๅฐๅฏ่ฝไธๅใ
ๆฏไธชB + Treeๅถๅญ/ๅ
้จ้กต้ขๅฏนๅบไป็ผๅฒๆฑ ่ทๅ็ๅญๅจ้กต้ข็ๅ
ๅฎน๏ผๅณdata_้จๅ๏ผใ ๅ ๆญค๏ผๆฏๆฌกๅฐ่ฏ่ฏปๅๆๅๅ
ฅๅถๅญ/ๅ
้จ้กต้ขๆถ๏ผ้ฝ้่ฆ้ฆๅ
ไฝฟ็จๅ
ถๅฏไธ็page_idไป็ผๅฒๆฑ ไธญๆๅ้กต้ข๏ผ็ถๅๅฐๅ
ถ้ๆฐ่งฃ้ไธบๅถๅญๆๅ
้จ้กต้ข๏ผๅนถๅจๅๅ
ฅๆๅ ้คๅๆง่กunpinๆไฝใ
Task 2.A - B+TREE DATA STRUCTURE (INSERTION & POINT SEARCH)
ๅ ถๅฎๅฐฑๆฏๅฎ็ฐ
b_plus_tree.cpp/InsertIntoLeafๅฝๆฐๆๆถๅๅฐ็็ธๅ ณๅฝๆฐใ
่ฟ้ B +ๆ ็ดขๅผๅช่ฝๆฏๆๅฏไธ้ฎใ ไนๅฐฑๆฏ่ฏด๏ผๅฝๆจๅฐ่ฏๅฐๅ
ทๆ้ๅค้ฎ็้ฎๅผๅฏนๆๅ
ฅ็ดขๅผๆถ๏ผๅฎๅบ่ฏฅ่ฟๅfalseใ
ๅฏนไบcheckpoint1๏ผไป
้่ฆB + Tree็ดขๅผๆฏๆๆๅ
ฅ๏ผInsert๏ผๅ็นๆ็ดข๏ผGetValue๏ผใ ๆไปฌไธ้่ฆๅฎ็ฐๅ ้คๆไฝใ
ๆๅ
ฅๅๅฆๆๅฝๅ้ฎ/ๅผๅฏน็ๆฐ้็ญไบmax_size๏ผๅๅบ่ฏฅๆญฃ็กฎๆง่กๅๅฒใ ็ฑไบไปปไฝๅๆไฝ้ฝๅฏ่ฝๅฏผ่ดB + Tree็ดขๅผไธญ็root_page_idๅ็ๆดๆน๏ผๅ ๆญค่ฆๆดๆฐ๏ผsrc / include / storage / page / header_page.h๏ผไธญ็root_page_id๏ผไปฅ็กฎไฟ็ดขๅผๅจ็ฃ็ไธๅ
ทๆๆไน
ๆง ใ ๅจBPlusTree็ฑปไธญ๏ผๆไปฌๅทฒ็ปไธบๆจๅฎ็ฐไบไธไธชๅไธบUpdateRootPageId็ๅฝๆฐใ ๆจ้่ฆๅ็ๅฐฑๆฏๅจB + Tree็ดขๅผ็root_page_idๆดๆนๆถ่ฐ็จๆญคๅฝๆฐใ
ๆจ็B + Treeๅฎ็ฐๅฟ ้กป้่key/value็ญ็่ฏฆ็ปไฟกๆฏ๏ผๅปบ่ฎฎไฝฟ็จๅฆไธ็ปๆ๏ผ
่ฟไบ็ฑปๅซๅทฒ็ปไธบไฝ ๅฎ็ฐไบ
KeyType: The type of each key in the index. This will only beGenericKey, the actual size ofGenericKeyis specified and instantiated with a template argument and depends on the data type of indexed attribute.ValueType: The type of each value in the index. This will only be 64-bit RID.KeyComparator: The class used to compare whether twoKeyTypeinstances are less/greater-than each other. These will be included in theKeyTypeimplementation files.
ไฝ ๅฟ ้กปไฝฟ็จไผ ๅ ฅ็transaction๏ผๆๅทฒ็ปๅ ้็้กต้ขไฟๅญ่ตทๆฅใ
ๆไปฌๆไพไบ่ฏปๅ้ๅญๅจ็ๅฎ็ฐ๏ผ
src / include / common / rwlatch.h๏ผใ ๅนถไธๅทฒ็ปๅจ้กต้ขๅคดๆไปถไธๆทปๅ ไบ่พ ๅฉๅฝๆฐๆฅ่ทๅๅ้ๆพLatch้๏ผsrc / include / storage / page / page.h๏ผใ
้ฆๅ ้ไธไนฆไธ็b+ๆ ๆๅ ฅ็ฎๆณ
ๅฏนไธ้ขๅ ็งๆ ๅต็ๅๆ
1. ๅฆๆๅฝๅไธบ็ฉบๆ ๅๅๅปบไธไธชๅถๅญ็ป็นๅนถไธไนๆฏๆ น่็น
่ฟ้ๆฏ
leaf็ป็นๆไปฅ่ฟ้้่ฆ็จๅฐleaf pageๅ ็ๅฝๆฐๆณจๆ่ฟ้้่ฆ็จlab1ๅฎ็ฐ็bufferๆฑ ็ฎก็ๅจๆฅ่ทๅพpageใ ่ฟ้่ฎฐๅพๅๅปบๅฎๆฐ็็ป็นไนๅ่ฆunpin
่ฟ่กๆๅ ฅ็ๆถๅ็จไบๅๆๅ ฅๆฅ่ฟ่กไผๅ
1. ๅๅปบๆฐ็ป็น
2. insertๅฝๆฐ#
่ฟ้็insertๅฝๆฐๅฏไปฅ็ดๆฅ็จไนๅ็KeyIndexๅฝๆฐ
2. ๅฆๅๅฏปๆพๅฐๆๅ
ฅๅ
็ด ๅบ่ฏฅๅจ็ๅถๅญ็ป็น๏ผๅนถๆๅ
ฅ(ไธๅ่ฃ)
้ฆๅ ๆพๅฐๅถๅญ็ป็น
ๅฆๆๅถๅญ็ป็นๅ ็ๅ ็ด ไธชๆฐๅฐไบๆๅคงๅผๅ็ดๆฅๆๅ ฅ
ๅฆๅ้่ฆ่ฟ่กๅ่ฃใไบง็ไธคไธชๆฐ็็ป็นใๆๅ ็ด ไธๆ
ๅฆๆๆๅฐ็ถไบฒ็ป็น๏ผ็ถ็ป็นไป้่ฆๅ่ฃใๅ้ๅฝ่ฟ่กๅ่ฃๅฆๅ็ปๆ
ๅฆๆๅถๅญ็ป็นๅ ็ๅ ณ้ฎๅญๅฐไบm-1,ๅ็ดๆฅๆๅ ฅๅฐๅถๅญ็ป็น
1. LookUpๅฝๆฐๅฎ็ฐ
Lookupๅฝๆฐ็จๆฅๅฏปๆพๅ ๅซ่พๅ ฅ"key"็children pointer(ๅ ถๅฎๅฐฑๆฏpage_id)
2. findLeafPage#
็ฑไบ่ฆๆพๅฐๅบ่ฏฅๆๅ
ฅ็LeafPageๆไปฅ่ฟไธชๅฝๆฐ็ ็ ้่ฆใไฝๆฏ่ฟ้ๆฏ้ๅนถๅไธๆๅ
ฅ๏ผๅจ่ฟ้็จfindLeafPage่ฟ่กๅฏนๆๅ
ฅ็ฎๆณ็ๆต่ฏใๅ้ขๅฏนไบๅนถๅๆ
ๅตไผๆๆไฟฎๆนใ
ไปๆดไธชb+ๆ ็ๆ น่็นๅผๅงใไธ็ดๅไธๆพๅฐๅถๅญ็ป็น
ๅ ไธบb+ๆ ๆฏๅค่ทฏๆ็ดขๆ ๏ผๆไปฅๆดไธชๅไธๆ็ดขๅฐฑๆฏ้่ฟkeyๅผ่ฟ่กๆฏ่พ
ๅ ถไธญๅ ้จ็ป็นๅไธๆ็ดข็่ฟ็จๅฉ็จไบไธ้ขๆๅฐ็
lookupๅฝๆฐ
3. ๆ ๅ่ฃ็ดๆฅๆๅ ฅ
3. ๅ่ฃ็ๆ
ๅต
InsertLeafไธปๅฝๆฐๆฅไธๆใ
1. ่ฐ็จsplitๅฝๆฐๅฏนๅถๅญ็ป็น่ฟ่กๅๅฒ
split็ๆถๅไผไบง็ไธไธชๅซๆm-m/2ไธชๅ ณ้ฎๅญ็ๆฐ็ป็นใๆณจๆๆไธคไธชๅถๅญ็ป็น่ฟๆฅ่ตทๆฅใ
่ฟ้ๆณจๆsplitๅฝๆฐ่ฆๅบๅๅถๅญ็ป็นๅๅ ้จ็ป็นใๅ ไธบๅถๅญ็ป็น้่ฆๆดๆฐๅๅ้พ่กจ
่ฟ้ๆถๅๅฐไบMoveHalfToๅฝๆฐ็ฎๅ็้ไธไธไธ๏ผ่ฟไธช้ๅธธ็ฎๅ
2. InsertIntoParentๅฝๆฐๅฎ็ฐ
่ฟไธชๅฝๆฐ็ๅฎ็ฐๅ ็ไธไธไนฆไธ็ปๅบ็็ฎๆณ
ๅฆๆ
old_nodeๅฐฑๆฏๆ น่็น๏ผ้ฃไนๅฐฑ่ฆๅๅปบไธไธชๆฐ็่็นRๅฝไฝๆ น่็นใ็ถๅๅkey็ๅผๅฝไฝๆ น่็น็ๅผใไฟฎๆนold_nodeๅnew_node็็ถๆ้ใไปฅๅๆ น่็น็ๅญฉๅญๆ้
ๆพๅฐๅ่ฃ็ๅถๅญ็ป็น็็ถไบฒ่็น้ๅ่ฟ่กๅคๆญ
a. ๅฆๆๅฏไปฅ็ดๆฅๆๅ ฅๅ็ดๆฅๆๅ ฅ
b. ๅฆๅ้่ฆๅฏน็ถ็ป็นๅจ่ฟ่กๅ่ฃ๏ผๅณ้ๅฝ่ฐ็จใ
ๅฅฝไบ็ฌฌไธ้จๅ็ๆต่ฏๅฐฑ้่ฟไบ
้ไธไธไธชpass็ๆชๅพๅฎๆ็ฌฌไธ้จๅโ ๅฆๆๆไปฌๆๅ ฅ1ใ2ใ3ใ4ใ5้ฃไนๆไปฌ็จ็จๅบๅพๅฐ็็ปๆๅฆไธ๏ผ
ๅฏไปฅๅ็ฐๆฏๅฎๅ จๆญฃ็กฎ็ ๐
3. โ ๏ธไธไบ็ป่
1. ๅ
ณไบๅ
้จ็ป็นๅๅถๅญ็ป็น็ๅบๅซ
1.1 ๅคงๅฐไธไธๆ ท
ๅ ้จ็ป็น็ๆๅคง็ป็นไธชๆฐๆฏๆฏๅถๅญ็ป็นๅคไธ
ไพๅฆm = 3, ้ฃไนๅ ้จ็ป็น็ไธชๆฐๅฐฑๅฏไปฅๆฏ3ใ่ๅถๅญ็ป็นๅๆๅคๆฏ2๏ผไฝๆฏๅ ้จ็ป็น็array[0]ๅฎ้ ไธๅฐฑๆฏไธชๅญๅฐๅ็ใๅฎ็keyๅจๆไปฌ็Draw็ปๆๅพไธญ้ฝไธๆพ็คบใ
1.2 ๅจSplit็ๆถๅๆๅบๅซ
ๅจๅถๅญ็ป็นsplit็ๆถๅ้่ฆ่ฟ่กๅๅ้พ่กจ็็ปดๆค
่ๅจๅ ้จ็ป็นๅไธ้่ฆ
ๅ ฑๆๆไฝ้ฝๆฏ่ทๅพไธไธชๆฐ้กต--> ็ฑปๅ่ฝฌๆข ---> MoveHalfTo
2. upin็pin็ๆณจๆไบ้กน
ๅฝไฝ ๅฉ็จ
FetchPageๆฟๅฐไธไธชpage็ๆถๅไปๅฐฑๆฏpinedๅฝไฝ ไฝฟ็จๅฎไนๅ่ฎฐๅพ่ฆ
unpin่ฟๅพ้่ฆ
3. debug็ไธไบๅฐๆๅทง
ๅฉ็จๅฏ่งๅ็ฝ็ซๅไปฃ็ ไธญ็ป็
b_plus_print_test่ฟไธชๆต่ฏ๏ผๆ่พๅ ฅๅพๆๅฐๆxxx.dot็ถๅๅคๅถ้้ข็ๅ ๅฎนๅจhttp://dreampuf.github.io/GraphvizOnline/ๆพ็คบ่ฟ่กๅฏนๆฏใๅฏนไบ
Mac็ณป็ปๅฉ็จClionๅฏไปฅ็ดๆฅๅฏนๆต่ฏๆไปถdebugใ่ฟๆฏ้ๅธธ็ฝ็ใๅ ถไธญlldb็ๅฉ็จ้ๅธธ้่ฆใ
4. maxSize็ๅซไน
่ฟ้่ฆๆณจๆๅจ่ฟ่กB+ๆ ๅๅงๅๆถๅ็ป็
internal_max_sizeๅฏไปฅ่ฎคไธบๆ็ๆฏๆ้ๆฐใไนๅฐฑๆฏ่ฏดๅ่ฎพๆไปฌๆm = 3็b+ๆ
inter_max_size = 3 ๆฏๅฏไปฅๆไธไธชkeyใไฝๆฏ leaf_max_size = 2 ๅฐฑๅช่ฝๅ ๅซไธไธชkeyใ่ฟไธชๅจๆต่ฏ็จไพ่ขซๅกๆๅ็ฐ็ใ
ๆไปฅmaxSize()ๅฝๆฐๅฏไปฅ่ฟๆ ทๅฎ็ฐ
Last updated
