่ฟ้ๅฐฑๆฏ้่ฆๅฎ็ฐ่ฟญไปฃๅจ็ไธไบๆไฝ,ๆฏๅฆbeginใendใisend็ญ็ญ
ไธ้ขๆฏๅฏนไบIndexIterator็ๆ้ ๅฝๆฐ
ๅ
ถไธญidx่กจ็คบๅฝๅpageไธญ็็ฌฌๅ ไธชtuple
Copy INDEXITERATOR_TYPE :: IndexIterator ( LeafPage * leftmost_leaf , int idx , BufferPoolManager * buffer_pool_manager )
: curr_page ( leftmost_leaf ), curr_index ( idx ), bpm ( buffer_pool_manager ) {} ๅฉ็จkeyๅผๆพๅฐๅถๅญ็ป็น
็ถๅ่ทๅๅฝๅkeyๅผ็indexๅฐฑๆฏbegin็ไฝ็ฝฎ
Copy Page * page = FindLeafPage ( KeyType{} , true ); // leftmost_leaf pinned
LeafPage * leftmost_leaf = reinterpret_cast < LeafPage *> ( page -> GetData ());
buffer_pool_manager_ -> UnpinPage ( leftmost_leaf -> GetPageId (), false );
return INDEXITERATOR_TYPE ( leftmost_leaf , 0 , buffer_pool_manager_ ); ็ถๅไธ็ดๅๅ้ๅ็ดๅฐnextPageId=-1็ปๆ
่ฟ้ๆณจๆ้่ฆ้่ฝฝ!=ๅ==
endๅฝๆฐ
==ๅ !=ๅฝๆฐ
่ฟ้ๆณจๆๅจ๏ผ= ้ฃ้ไธ่ฝๅๆitr != *this
3. ้่ฝฝ++ๅ*(่งฃๅผ็จ็ฌฆๅท)
็ฎๅ็index++็ถๅ่ฎพ็ฝฎnextPageIdๅณๅฏ
return array[index]ๅณๅฏ
5. ๅนถๅๆบๅถ็ๅฎ็ฐ
0. ้ฆๅ
ๅคไน ไธไธ่ฏปๅ๐ๆบๅถ
่ฏปๆไฝๆฏๅฏไปฅๅคไธช่ฟ็จไน้ดๅ
ฑไบซlatch็่ๅๆไฝๅๅฟ
้กปไบๆฅ
ๅ ๅ
ฅMaxReaderๆฐๅฐฑๆฏไธบไบ้ฒๆญข็ญๅพ
็โ๏ธๅ่ฟ็จ้ฅฅ้ฅฟ
้ฆๅ
ๆฅ็ๅฆๆๆฒกๆ๐ๆบๅถๅค็บฟ็จไผๅ็ไปไน้ฎ้ข
็บฟ็จT1ๆณ่ฆๅ ้ค44ใ
ๅ่ฎพT2ๅจๆง่กๅฐDไฝ็ฝฎ็ๆถๅๅๅๆขๅฐ็บฟ็จT1
่ฟไธชๆถๅT1่ฟ่ก้ๆฐๅ้
๏ผไผๆ41ๅๅฐI็ป็นไธ
T1ๆง่กๅฎๆๅๆขๅT2่ฟๆถๅT2ๅๅปๅๆฅ็ๆง่กๅฏปๆพ41ๅฐฑไผๆพไธๅฐ
ๅฐฑไผๅบ็ฐไธ้ข็ๆ
ๅตใโ
็ฑๆญคๆไปฌ้่ฆ่ฏปๅ๐็ๅญๅจ
็ฑไบๆไปฌๆฏๅช่ฏปๆไฝ๏ผๆไปฅๆไปฌๅฐไธไธไธช็ป็น็ๆถๅๅฐฑๅฏไปฅ้ๆพไธไธไธช็ป็น็Latch
ๅฉไธ็ๆไฝ้ฝๆฏไธๆ ท็
ๅฏนไบdeleteๅไธไธๆ ท
ๅ ไธบๆไปฌ้่ฆๅๆไฝ
่ฟ้ๆไปฌไธ่ฝ้ๆพ็ป็นA็Latchใๅ ไธบๆไปฌ็ๅ ้คๆไฝๅฏ่ฝไผๅๅนถๆ น่็นใ
ๅฐD็ๆถๅใๆไปฌไผๅ็ฐDไธญ็38ๅ ้คไนๅไธ้่ฆ่ฟ่กๅๅนถ๏ผๆไปฅๅฏนไบAๅB็ๅWriteๆฏๅฏไปฅๅฎๅ
จ้ๆพไบ
ๅฏนไบInsertๆไฝ
่ฟ้ๆไปฌๅฐฑๅฏไปฅๅฎๅ
จ็้ๆพๆA็้ใๅ ไธบBไธญ่ฟๆ็ฉบไฝ๏ผๆไปฌๆๅ
ฅๆฏไธไผๅฏนA้ ๆๅฝฑๅ็
ๅฝๆไปฌๆง่กๅฐD่ฟ้ๅ็ฐDไธญๅทฒ็ปๆปกไบใๆไปฅๆญคๆถๆไปฌไธไผ้ๆพB็้๏ผๅ ไธบๆไปฌไผๅฏนB่ฟ่กๅๆไฝ
ไธ้ข็็ฎๆณ่ฝ็ถๆฏๆญฃ็กฎ็ไฝๆฏๆ็ถ้ข้ฎ้ขใ็ฑไบๅชๆไธไธช็บฟ็จๅฏไปฅ่ทๅพๅLatchใ่ๆๅ
ฅๅๅ ้ค็ๆถๅ้ฝ้่ฆๅฏนๅคด็ป็นๅ ๅLatchใๆไปฅๅค็บฟ็จๅจๆ่ฎธๅคไธชๆๅ
ฅๆ่
ๅ ้คๆไฝ็ๆถๅ๏ผๆง่ฝๅฐฑไผๅคงๆๆๆฃ
่ฟ้่ฆๅผๅ
ฅไน่ง๐
ไน่ง็ๅ่ฎพๅคง้จๅๆไฝๆฏไธ้่ฆ่ฟ่กๅๅนถๅๅ่ฃ็ใๅ ๆญคๅจๆไปฌๅไธ็ๆถๅ้ฝๆฏ่ฏปLatch่ไธๆฏๅLatchใๅชๆๅจๅถๅญ็ป็นๆๆฏwrite Latch
ไปไธๅฐไธ้ฝๆฏ่ฏปLatchใ่ไธ้ๆญฅ้ๆพ
ๅฐๅถๅญ็ป็น้่ฆไฟฎๆน็ๆถๅๆไธบๅLatchใ่ฟไธชๅ ้คๆฏๅฎๅ
จ็ๆไปฅ็ดๆฅ็ปๆ
ๅฝๆไปฌๅฐๆๅไธๆญฅๅ็ฐไธๅฎๅ
จ็ๆถๅใๅ้่ฆๅไธ้ขๆไปฌๆฒกๆๅผๅ
ฅไน่ง๐็ๆถๅไธๆ ทใ้ๆฐๆง่กไธ้
B-Link Tree็ฎไป
ๅปถ่ฟๆดๆฐ็ถ็ป็น
่ฟ้็จไธไธช๐ๆฅๆ ่ฎฐ่ฟ้้่ฆ่ขซๆดๆฐไฝๆฏ่ฟๆฒกๆๆง่ก
่ฟไธชๆถๅๆไปฌๆง่กๅ
ถไปๆไฝไนๆฏๆญฃ็กฎ็ๆฏๅฆๆฅๆพ31
่ฟ้ๆไปฌๆง่กinsert 33
ๅฝๆง่กๅฐ็ป็นC็ๆถๅใๅ ไธบ่ฟไธชๆถๅๆๅฆไธไธช็บฟ็จๆๆไบwrite Latchใๆไปฅ่ฟไธชๆถๅ๐ๆไฝ่ฆๆง่กใ้ๅๅจๆๅ
ฅ33
ๆๅไธ็น่กฅๅ
ๅ
ณไบๆซๆๆไฝ็
็บฟ็จ1ๅจC็ป็นไธๆๆwrite Latch
็บฟ็จ2ๅทฒ็ปๆซๆๅฎไบ็ป็นBๆณ่ฆ่ทๅพ็ป็นC็read Latch
่ฟๆถๅไผๅ็้ฎ้ข๏ผๅ ไธบ็บฟ็จ2ๆ ๆณๆฟๅฐread Latch
่ฟ้ๆๅ ็ง่งฃๅณๆนๆณ
ๅฏไปฅ็ญๅฐT1็ๅๆไฝๅฎๆ
ๅฏไปฅ็ดๆฅ่ฎฉ็บฟ็จT2ๅๆญขๆขๅพ่ฟไธชLatchใ
ๆณจๆ่ฟ้็LatchๅLockๅนถไธไธๆ ท
6. ่พ
ๅฉๅฝๆฐๅๆ
1. ่พ
ๅฉๅฝๆฐUnlockUnpinPages็ๅฎ็ฐ
ๅฆๆๆฏ่ฏปๆไฝๅ้ๆพread้
ๅไธช่ชๅธฆ็่งฃ้ๅไธ้ๆไฝ
่ฟ้็rwlatchๆฏ่ชๅทฑๅฎ็ฐ็่ฏปๅ้็ฑปไธ้ขๆฅๆข็ฉถไธไธ่ฟไธช็ฑป
็ฑไบc++ ๅนถๅ็ผ็จๆ็ฐๅจ่ฟไธๅคชไผใใใๆไปฅๅฐฑ็ฎๅ็ไธไธๅฆๅ้ขๅญฆๅฎๅนถๅ็ผ็จๅ่กฅๅ
WLockๅฝๆฐ
็จไธไธช่ฎฐๅทwriter_entered่กจ็คบๆฏๅฆๆๅๆไฝ
ๅฆๆไนๅๅทฒ็ปๆไบ็ฐๅจ็ๆไฝๅฐฑ้่ฆ็ญ(่ฟไธช็บฟ็จๅคไบ้ปๅก็ถๆ)
ๅฝๅๅฆๆๆๅ
ถไป็บฟ็จๆง่ก่ฏปๆไฝใๅไป้่ฆ้ปๅก(ๅซไบบ่ฏป็ๆถๅไฝ ไธ่ฝๅ)
WunLockๅฝๆฐ
็ถๅ้็ฅๆๆ็็บฟ็จ
RLockๅฝๆฐ
ๅฆๆๅฝๅๆไบบๅจๅๆ่
ๅทฒ็ปๆๆๅค็ไบบ่ฏปไบๅ้ปๅก
ๅฆๅๅช้่ฆ่ฎฉ่ฏป็่ฎกๆฐ++
ๅ ไธบๆฏๅ
่ฎธๅคไธช็บฟ็จไธ่ตท่ฏป่ฟๆ ทๅนถไธไผๅบ้
RUnLatchๅฝๆฐ
ๅฆๆๅฝๅๆไบบๅจๅๅนถไธๆ ไบบ่ฏป็่ฏ้่ฆ้็ฅๆๆๅ
ถไป็บฟ็จ
ๅฆๆๅจ่ฎกๆฐ--ไนๅ่พพๅฐไบๆๅคง่ฏปๆฐ๏ผ้ๆพ่ฟไธช้ไนๅ้่ฆ้็ฅๅ
ถไป็บฟ็จ๏ผ็ฐๅจๅๅฏไปฅ่ฏปไบใ
7. ๅนถๅ็ดขๅผๅฎ็ฐ
1. FindLeafPageRW็ๅฎ็ฐ
1. 1 ๆดไฝๆ่ทฏ
ๅฏนไบๅนถๅๆงๅถ็ๅฎ็ฐ๏ผ้็จๆ็ฎๅ็latch crabingๆนๆณๅฎ็ฐ๏ผไนๅฐฑๆฏไธ้ข่ฎฒ็้ฃ็งๆนๆณ๏ผ ่ฟ็งๆนๆณ้่ฆๅจๆพๅถๅญ็ป็น็ๆถๅ๏ผไปๆ น่็นๅฐๅถๅญ็ป็น็่ฟ็จ้่ฆ้ๆญฅๅ ้๏ผ็ถๅๆฃๆตๆฏๅฆ่ฝๅค้ๆพใ็ฑไบๆไปฌ็ๆๅ
ฅๅๅ ้คๆไฝ้ฝ้่ฆๅ
ๆพๅฐๅถๅญ็ป็น๏ผๆไปฅไนๅไฝฟ็จ็ๆ ้็ๆฌ็FindLeafPageๅฝๆฐๅจๅนถๅๆกไปถไธๅฐฑๅนถไธ้็จไบใๅ ๆญค่ฟ้้่ฆๅฎ็ฐไธไธช้ๆญฅๅ ้ + ้ๆญฅ้ๆพ ็ๆฐๅฝๆฐ
ๆดไฝๆ่ทฏๅไนๅ็findLeafPageๅ ไนไธๆ ท๏ผๅชๆฏๅคไบๅ ๆฌกๅคๆญ
ๅฆๆๆฏ่ฏปๆไฝ๏ผ้ฃๅ็ดๆฅๅ ้๏ผ็ถๅๅฏนไธไธๅฑ้ๆพ้
ๅฆๆๆฏๅๆไฝ๏ผ้ๆพ้ไนๅๅ่ฆๅคๆญไธไธๆฏๅฆๅฎๅ
จใ
ๅฆๆๆฏๆๅ
ฅๆไฝ๏ผๅๅช่ฆๅฝๅnode็sizeๅคไบๅฎๅ
จ็ถๆๅณ + 1 ไนๅไธไผไบง็ๅ่ฃ๏ผๅไธบๅฎๅ
จ
ๅฆๆๆฏๅ ้ค็ถๆใๅๅช่ฆๅฝๅnode็size - 1 ไนๅไธไผ้ๅ้
ๆ่
ๅๅนถ๏ผๅไธบๅฎๅ
จ
ๅฏนไบๆ น่็น้่ฆ่ฟ่ก็นๆฎๅคๆญ๏ผๅฆๆ่ฟไธชๆ น่็นๆฏๅถๅญ็ป็นๅไธบๅฎๅ
จ๏ผ่ฟ็งๆ
ๅต้ไพฟๅ ๏ผใๅฆๅๆ น่็น็ๅคงๅฐๅฟ
้กปๅคงไบ2(ๅ ไธบๅฆๆ็ญไบ2 ๏ผๅๅป1ไนๅ่ฟๆฏ1ใๅๆฏไธไธชๆฒกๆๆๆkeyๅผ็็ป็น๏ผไธๅฎๅ
จ)
่ฟไธคไธชๆ้ฝ่ฆๅฏนpageๅ๏ผไธๅ
ถๅคๅๅ ่กไธๅฆๅไธชๅฝๆฐ็ปไปๅๅนถๅจไธ่ตทๅใ
transaction->GetPageSet(); ๅฐฑๆฏไนๅ่ฎฟ้ฎ่ฟ็page้ๅ
2. ๆฏๆๅนถๅ็่ฏปๅๆไฝ
ๅ
ถๅฎๅช้่ฆไนๅๅๅฎข1ใ2็้ๅนถๅ็ๆฌไธๅไธไบๅฐๅฐ็ๆนๅจ
2.1 ๆฏๆๅนถๅ่ฏป
2.2 ๆฏๆๅนถๅๅ
่ฟ้่ฆๆฏๆๆๅ
ฅๅๅ ้คไธค็งๅๆไฝ
ๆ นๆฎๅฎ้ชๆ็คบ๏ผ้ฆๅ
้่ฆ่ทๅๅฏนไบๆ น่็น็้ใๆไธชไบบ่ฎคไธบๆฏไธบไบ้ฒๆญขไธ้ข่ฟ็งๆ
ๅตๅ็
ๅฆๆ็่งฃ็ๆ้ฎ้ข๏ผๆฌข่ฟๅคงๅฎถๆๅบ๏ผไบ็ธ่ฎจ่ฎบ
consider the following case
txn A read "A" from tree but not hold mutex (if "A" not in the tree)
before A crab page0 latch , txnB crab page0 and insert "A" into the tree then unlatch page0
txnA crab page0 get false result
็จFindLeafRWๆฟๆขไนๅ็FindLeafๅฝๆฐๅณๅฏ
็จUnLatchAndPinๆฟๆขไนๅ็ฎๅ็unpinๆไฝใ
ๅฎๆดไปฃ็ ๅฐฑไธ่ดดไบ๏ผๅจไนๅ็insertไธๆนไธไธๅฐฑ่กไบ
ๅฏนไบๅ ้ค้ฆๅ
่ฆๅจremoveไธๅๅinsertไธๆ ท็ๅค็
ๅจๆ ธๅฟๅฝๆฐCoalesceOrRedistributeไธญๅฏนๅ
ๅผ็ป็นๅไฟฎๆนไนๅ๏ผๅ
ๅ ๅ้็ปๆไนๅ้ๆพๅ้ๅฐฑok
