๐Pre: B & B+
1 Bๆ
ๅจไป็ปB+ๆ ไนๅ๏ผ ๅ ็ฎๅ็ไป็ปไธไธBๆ ๏ผ่ฟไธค็งๆฐๆฎ็ปๆๆขๆ็ธไผผไนๅค๏ผไนๆไปไปฌ็ๅบๅซ๏ผๆๅ๏ผๆไปฌไนไผๅฏนๆฏไธไธ่ฟไธค็งๆฐๆฎ็ปๆ็ๅบๅซใ
1.1 Bๆ ๆฆๅฟต
Bๆ ไน็งฐB-ๆ ,ๅฎๆฏไธ้ขๅค่ทฏๅนณ่กกๆฅๆพๆ ใไบๅๆ ๆๆณๅคงๅฎถ้ฝไธ้็๏ผๅ ถๅฎ๏ผBๆ ๅๅ้ข่ฎฒๅฐ็B+ๆ ไนๆฏไปๆ็ฎๅ็ไบๅๆ ๅๆข่ๆฅ็๏ผๅนถๆฒกๆไปไน็ฅ็ง็ๅฐๆน๏ผไธ้ขๆไปฌๆฅ็็Bๆ ็ๅฎไนใ
ๆฏไธช่็นๆๅคๆm-1ไธชๅ ณ้ฎๅญ๏ผๅฏไปฅๅญๆ็้ฎๅผๅฏน๏ผใ
ๆ น่็นๆๅฐๅฏไปฅๅชๆ1ไธชๅ ณ้ฎๅญใ
้ๆ น่็น่ณๅฐๆm/2ไธชๅ ณ้ฎๅญใ
ๆฏไธช่็นไธญ็ๅ ณ้ฎๅญ้ฝๆ็ งไปๅฐๅฐๅคง็้กบๅบๆๅ๏ผๆฏไธชๅ ณ้ฎๅญ็ๅทฆๅญๆ ไธญ็ๆๆๅ ณ้ฎๅญ้ฝๅฐไบๅฎ๏ผ่ๅณๅญๆ ไธญ็ๆๆๅ ณ้ฎๅญ้ฝๅคงไบๅฎใ
ๆๆๅถๅญ่็น้ฝไฝไบๅไธๅฑ๏ผๆ่ ่ฏดๆ น่็นๅฐๆฏไธชๅถๅญ่็น็้ฟๅบฆ้ฝ็ธๅใ
ๆฏไธช่็น้ฝๅญๆ็ดขๅผๅๆฐๆฎ๏ผไนๅฐฑๆฏๅฏนๅบ็keyๅvalueใ
ๆไปฅ๏ผๆ น่็น็ๅ
ณ้ฎๅญๆฐ้่ๅด๏ผ1 <= k <= m-1๏ผ้ๆ น่็น็ๅ
ณ้ฎๅญๆฐ้่ๅด๏ผm/2 <= k <= m-1ใ
ๅฆๅค๏ผๆไปฌ้่ฆๆณจๆไธไธชๆฆๅฟต๏ผๆ่ฟฐไธ้ขBๆ ๆถ้่ฆๆๅฎๅฎ็้ถๆฐ๏ผ้ถๆฐ่กจ็คบไบไธไธช่็นๆๅคๆๅคๅฐไธชๅญฉๅญ่็น๏ผไธ่ฌ็จๅญๆฏm่กจ็คบ้ถๆฐใ
ๆไปฌๅไธพไธชไพๅญๆฅ่ฏดๆไธไธไธ้ข็ๆฆๅฟต๏ผๆฏๅฆ่ฟ้ๆไธไธช5้ถ็Bๆ ๏ผๆ น่็นๆฐ้่ๅด๏ผ1 <= k <= 4๏ผ้ๆ น่็นๆฐ้่ๅด๏ผ2 <= k <= 4ใ
ไธ้ข๏ผๆไปฌ้่ฟไธไธชๆๅ ฅ็ไพๅญ๏ผ่ฎฒ่งฃไธไธBๆ ็ๆๅ ฅ่ฟ็จ๏ผๆฅ็๏ผๅ่ฎฒ่งฃไธไธๅ ้คๅ ณ้ฎๅญ็่ฟ็จใ
1.2 Bๆ ๆๅ ฅ
ๆๅ ฅ็ๆถๅ๏ผๆไปฌ้่ฆ่ฎฐไฝไธไธช่งๅ๏ผๅคๆญๅฝๅ็ป็นkey็ไธชๆฐๆฏๅฆๅฐไบ็ญไบm-1๏ผๅฆๆๆปก่ถณ๏ผ็ดๆฅๆๅ ฅๅณๅฏ๏ผๅฆๆไธๆปก่ถณ๏ผๅฐ่็น็ไธญ้ด็keyๅฐ่ฟไธช่็นๅไธบๅทฆๅณไธค้จๅ๏ผไธญ้ด็่็นๆพๅฐ็ถ่็นไธญๅณๅฏใ
ไพๅญ๏ผๅจ5้ถBๆ ไธญ๏ผ็ป็นๆๅคๆ4ไธชkey,ๆๅฐๆ2ไธชkey๏ผๆณจๆ๏ผไธ้ข็่็น็ปไธ็จไธไธช่็น่กจ็คบkeyๅvalue๏ผใ
ๆๅ ฅ18๏ผ70๏ผ50,40
ๆๅ ฅ22
ๆๅ ฅ22ๆถ๏ผๅ็ฐ่ฟไธช่็น็ๅ ณ้ฎๅญๅทฒ็ปๅคงไบ4ไบ๏ผๆไปฅ้่ฆ่ฟ่กๅ่ฃ๏ผๅ่ฃ็่งๅๅจไธ้ขๅทฒ็ป่ฎฒไบ๏ผๅ่ฃไนๅ๏ผๅฆไธใ
ๆฅ็ๆๅ ฅ23๏ผ25๏ผ39
ๅ่ฃ๏ผๅพๅฐไธ้ข็ใ
ๆด่ฟ็ๆๅ ฅ็่ฟ็จๅฐฑไธๅคไป็ปไบ๏ผ็ธไฟกๆ่ฟไธชไพๅญไฝ ๅทฒ็ป็ฅ้ๆไน่ฟ่กๆๅ ฅๆไฝไบใ
1.3 Bๆ ็ๅ ้คๆไฝ
Bๆ ็ๅ ้คๆไฝ็ธๅฏนไบๆๅ ฅๆไฝๆฏ็ธๅฏนๅคๆไธไบ็๏ผไฝๆฏ๏ผไฝ ็ฅ้่ฎฐไฝๅ ็งๆ ๅต๏ผไธๆ ทๅฏไปฅๅพ่ฝปๆพ็ๆๆก็ใ
็ฐๅจๆไธไธชๅๅง็ถๆๆฏไธ้ข่ฟๆ ท็Bๆ ๏ผ็ถๅ่ฟ่กๅ ้คๆไฝใ
ๅ ้ค15๏ผ่ฟ็งๆ ๅตๆฏๅ ้คๅถๅญ่็น็ๅ ็ด ๏ผๅฆๆๅ ้คไนๅ๏ผ่็นๆฐ่ฟๆฏๅคงไบ
m/2๏ผ่ฟ็งๆ ๅตๅช่ฆ็ดๆฅๅ ้คๅณๅฏใ
ๆฅ็๏ผๆไปฌๆ22ๅ ้ค๏ผ่ฟ็งๆ ๅต็่งๅ๏ผ22ๆฏ้ๅถๅญ่็น๏ผๅฏนไบ้ๅถๅญ่็น็ๅ ้ค๏ผๆไปฌ้่ฆ็จๅ็ปงkey๏ผๅ ็ด ๏ผ่ฆ็่ฆๅ ้ค็key๏ผ็ถๅๅจๅ็ปงkeyๆๅจ็ๅญๆฏไธญๅ ้ค่ฏฅๅ็ปงkeyใๅฏนไบๅ ้ค22๏ผ้่ฆๅฐๅ็ปงๅ ็ด 24็งปๅฐ่ขซๅ ้ค็22ๆๅจ็่็นใ
ๆญคๆถๅ็ฐ26ๆๅจ็่็นๅชๆไธไธชๅ ็ด ๏ผๅฐไบ2ไธช๏ผm/2๏ผ๏ผ่ฟไธช่็นไธ็ฌฆๅ่ฆๆฑ๏ผ่ฟๆถๅ็่งๅ๏ผๅๅ ๅผ่็นๅๅ ็ด ๏ผ๏ผๅฆๆๅ ้คๅถๅญ่็น๏ผๅฆๆๅ ้คๅ ็ด ๅๅ ็ด ไธชๆฐๅฐไบ๏ผm/2๏ผ๏ผๅนถไธๅฎ็ๅ ๅผ่็น็ๅ ็ด ๅคงไบ๏ผm/2๏ผ๏ผไนๅฐฑๆฏ่ฏดๅ ๅผ่็น็ๅ ็ด ๆฏๆๅฐๅผm/2่ฟๅค๏ผๅฐๅ ๅฐ็ถ่็น็ๅ ็ด ็งปๅฐ่ฏฅ่็น๏ผ็ถๅๅฐๅ ๅผ่็น็ๅ ็ด ๅ็งปๅจๅฐ็ถ่็นใ่ฟๆ ทๅฐฑๆปก่ถณ่ฆๆฑไบใ
ๆไปฌ็็ๆไฝ่ฟ็จๅฐฑๆดๅ ๆ็ฝไบใ
ๆฅ็ๅ ้ค28๏ผๅ ้คๅถๅญ่็น๏ผๅ ้คๅไธๆปก่ถณ่ฆๆฑ๏ผๆไปฅ๏ผๆไปฌ้่ฆ่่ๅๅ ๅผ่็นๅๅ ็ด ๏ผไฝๆฏ๏ผๅ ๅผ่็นไนๆฒกๆๅค็่็น๏ผ2ไธช๏ผ๏ผๅไธไบ๏ผๆไนๅๅข๏ผๅฆๆ้ๅฐ่ฟ็งๆ ๅต๏ผ้ฆๅ ๏ผ่ฟๆฏๅฐๅ ๅฐ็ถ่็น็ๅ ็ด ็งปๅฐ่ฏฅ่็น๏ผ็ถๅ๏ผๅฐๅฝๅ่็นๅๅฎ็ๅ ๅผ่็นไธญ็keyๅๅนถ๏ผๅฝขๆไธไธชๆฐ็่็นใ
็งปๅจไนๅ๏ผ่ทๅ ๅผ่็นๅๅนถใ
ๅ ้คๅฐฑๅชๆไธ้ข็ๅ ็งๆ ๅต๏ผๆ นๆฎไธๅ็ๆ ๅต่ฟ่กๅ ้คๅณๅฏใ
ไธ้ข็่ฟไบไป็ป๏ผ็ธไฟกๅฏนไบBๆ ๅทฒ็ปๆไธๅฎ็ไบ่งฃไบ๏ผๆฅไธๆฅ็ไธ้จๅ๏ผๆไปฌๆฅ็่ฎฒ่งฃB+ๆ ๏ผๆ็ธไฟกๅ ไธB+ๆ ็ๅฏนๆฏ๏ผๅฐฑๆดๅ ๆธ ๆฐๆไบไบใ
2 B+ๆ
2.1 B+ๆ ๆฆ่ฟฐ
B+ๆ ๅ ถๅฎๅBๆ ๆฏ้ๅธธ็ธไผผ็๏ผๆไปฌ้ฆๅ ็็็ธๅ็นใ
ๆ น่็น่ณๅฐไธไธชๅ ็ด
้ๆ น่็นๅ ็ด ่ๅด๏ผm/2 <= k <= m-1
ไธๅ็นใ
B+ๆ ๆไธค็ง็ฑปๅ็่็น๏ผๅ ้จ็ป็น๏ผไน็งฐ็ดขๅผ็ป็น๏ผๅๅถๅญ็ป็นใๅ ้จ่็นๅฐฑๆฏ้ๅถๅญ่็น๏ผๅ ้จ่็นไธๅญๅจๆฐๆฎ๏ผๅชๅญๅจ็ดขๅผ๏ผๆฐๆฎ้ฝๅญๅจๅจๅถๅญ่็นใ
ๅ ้จ็ป็นไธญ็key้ฝๆ็ งไปๅฐๅฐๅคง็้กบๅบๆๅ๏ผๅฏนไบๅ ้จ็ป็นไธญ็ไธไธชkey๏ผๅทฆๆ ไธญ็ๆๆkey้ฝๅฐไบๅฎ๏ผๅณๅญๆ ไธญ็key้ฝๅคงไบ็ญไบๅฎใๅถๅญ็ป็นไธญ็่ฎฐๅฝไนๆ็ งkey็ๅคงๅฐๆๅใ
ๆฏไธชๅถๅญ็ป็น้ฝๅญๆ็ธ้ปๅถๅญ็ป็น็ๆ้๏ผๅถๅญ็ป็นๆฌ่บซไพๅ ณ้ฎๅญ็ๅคงๅฐ่ชๅฐ่ๅคง้กบๅบ้พๆฅใ
็ถ่็นๅญๆๅณๅญฉๅญ็็ฌฌไธไธชๅ ็ด ็็ดขๅผใ
ไธ้ขๆไปฌ็ไธไธชB+ๆ ็ไพๅญ๏ผๆๅๆๅๅฎๅง๏ผ
2.2 ๆๅ ฅๆไฝ
ๅฏนไบๆๅ ฅๆไฝๅพ็ฎๅ๏ผๅช้่ฆ่ฎฐไฝไธไธชๆๅทงๅณๅฏ๏ผๅฝ่็นๅ ็ด ๆฐ้ๅคงไบm-1็ๆถๅ๏ผๆไธญ้ดๅ ็ด ๅ่ฃๆๅทฆๅณไธค้จๅ๏ผไธญ้ดๅ ็ด ๅ่ฃๅฐ็ถ่็นๅฝๅ็ดขๅผๅญๅจ๏ผไฝๆฏ๏ผๆฌ่บซไธญ้ดๅ ็ด ่ฟๆฏๅ่ฃๅณ่พน่ฟไธ้จๅ็ใ
ไธ้ขไปฅไธ้ข5้ถB+ๆ ็ๆๅ ฅ่ฟ็จไธบไพ๏ผ5้ถB+ๆ ็่็นๆๅฐ2ไธชๅ ็ด ๏ผๆๅค4ไธชๅ ็ด ใ
ๆๅ ฅ5๏ผ10๏ผ15๏ผ20
ๆๅ ฅ25๏ผๆญคๆถๅ ็ด ๆฐ้ๅคงไบ4ไธชไบ๏ผๅ่ฃ
ๆฅ็ๆๅ ฅ26๏ผ30๏ผ็ปง็ปญๅ่ฃ
ๆไบ่ฟๅ ไธชไพๅญ๏ผ็ธไฟกๆๅ ฅๆไฝๆฒกไปไน้ฎ้ขไบ๏ผไธ้ขๆฅ็็็ๅ ้คๆไฝใ
2.3 ๅ ้คๆไฝ
ๅฏนไบๅ ้คๆไฝๆฏๆฏBๆ ็ฎๅไธไบ็๏ผๅ ไธบๅถๅญ่็นๆๆ้็ๅญๅจ๏ผๅๅ ๅผ่็นๅๅ ็ด ๆถ๏ผไธ้่ฆ้่ฟ็ถ่็นไบ๏ผ่ๆฏๅฏไปฅ็ดๆฅ้่ฟๅ ๅผ่็งปๅจๅณๅฏ๏ผๅๆๆฏๅ ๅผ่็น็ๅ ็ด ๅคงไบm/2๏ผ๏ผ็ถๅๆดๆฐ็ถ่็น็็ดขๅผ๏ผๅฆๆๅ ๅผ่็น็ๅ ็ด ไธๅคงไบm/2๏ผๅ ๅผ่็นไนๆฒกๆๅคไฝ็ๅ ็ด ๏ผ๏ผๅๅฐๅฝๅ่็นๅๅ ๅผ่็นๅๅนถ๏ผๅนถไธๅ ้ค็ถ่็นไธญ็key๏ผไธ้ขๆไปฌ็็ๅ ทไฝ็ๅฎไพใ
ๅๅง็ถๆ
ๅ ้ค10๏ผๅ ้คๅ๏ผไธๆปก่ถณ่ฆๆฑ๏ผๅ็ฐๅทฆ่พนๅ ๅผ่็นๆๅคไฝ็ๅ ็ด ๏ผๆไปฅๅปๅๅ ็ด ๏ผๆๅ๏ผไฟฎๆน็ถ่็น็ดขๅผ
ๅ ้คๅ ็ด 5๏ผๅ็ฐไธๆปก่ถณ่ฆๆฑ๏ผๅนถไธๅ็ฐๅทฆๅณๅ ๅผ่็น้ฝๆฒกๆๅคไฝ็ๅ ็ด ๏ผๆไปฅ๏ผๅฏไปฅ้ๆฉๅๅ ๅผ่็นๅๅนถ๏ผๆๅไฟฎๆน็ถ่็น็ดขๅผ
ๅ็ฐ็ถ่็น็ดขๅผไนไธๆปก่ถณๆกไปถ๏ผๆไปฅ๏ผ้่ฆๅ่ทไธ้ขไธๆญฅไธๆ ท็ๆไฝ
่ฟๆ ท๏ผB+ๆ ็ๅ ้คๆไฝไนๅฐฑๅฎๆไบ๏ผๆฏไธๆฏ็ๅฎไนๅ๏ผ่งๅพ้ๅธธ็ฎๅ๏ผ
3 Bๆ ๅB+ๆ ๆป็ป
B+ๆ ็ธๅฏนไบBๆ ๆไธไบ่ชๅทฑ็ไผๅฟ๏ผๅฏไปฅๅฝ็ปไธบไธ้ขๅ ็นใ
ๅไธ่็นๅญๅจ็ๅ ็ด ๆดๅค๏ผไฝฟๅพๆฅ่ฏข็IOๆฌกๆฐๆดๅฐ๏ผๆไปฅไนๅฐฑไฝฟๅพๅฎๆด้ๅๅไธบๆฐๆฎๅบMySQL็ๅบๅฑๆฐๆฎ็ปๆไบใ
ๆๆ็ๆฅ่ฏข้ฝ่ฆๆฅๆพๅฐๅถๅญ่็น๏ผๆฅ่ฏขๆง่ฝๆฏ็จณๅฎ็๏ผ่Bๆ ๏ผๆฏไธช่็น้ฝๅฏไปฅๆฅๆพๅฐๆฐๆฎ๏ผๆไปฅไธ็จณๅฎใ
ๆๆ็ๅถๅญ่็นๅฝขๆไบไธไธชๆๅบ้พ่กจ๏ผๆดๅ ไพฟไบๆฅๆพใ
Last updated