[JTF2021] 結局インデックスってなんなんですか？/lets-learn-about-b-tree-index

݁ہΠϯσοΫεͬͯͳΜͳΜͰ͔͢ʁ 1PTUHSF42-ͷ࢓૊Έ͔ΒΠϯσοΫεͷཧղΛਂΊΔ +VMZ5FDI'FTUB !IBTTBLV

4QFBLFS IBTTBLV $PSQPSBUF&OHJOFFSBU4FSWFSXPSLT$P -UE   5XJUUFS!IBTTBLV@ (JU)VCIBTTBLV

4QFBLFS w 4UFQ'VODUJPOT -BNCEB w 4FSWFSMFTT'SBNFXPSL w 1ZUIPO w 4BMFTGPSDF
w ۀ຿ϑϩʔվળʢόοΫΦϑΟεܥத৺ʣ

ͳͥɺࠓ೔͜͜ʹ͍Δͷ͔ w ʮશવΘ͔Βͳ͍ɻԶͨͪ͸งғؾͰʢུʣʯঢ়ଶΛগ͠Ͱ΋୤͍ͨ͠ w ֓ཁ͘Β͍͸஌ͬͯΔͭ΋ΓͰ͍Δ͚ΕͲʜ w ೔ৗۀ຿Ͱ3%#ͱͷ઀఺͕গͳ͍ w ࣗ෼ࣗ਎͕ʮࠓ͞Βฉ͚ͳ͍ʯͱࢥͬͯΔωλΛΞ΢τϓοτ͔ͨͬͨ͠ w
ಉؔ͡৺Λ࣋ͭਓ͕Կਓ͔͸͍ΔͷͰ͸ʁ w ͋ΘΑ͘͹ποίϛΛ௖ଷ͍ͨ͠ w ৲ʹՐΛ͚ͭͳ͍ͱษڧ͕ਐ·ͳ͍ʜ

͓࿩͢͠Δ͜ͱʗ͠ͳ͍͜ͱ w ࿩͢͜ͱ w ΠϯσοΫεΛར༻͢ΔϞνϕͷ͓͞Β͍ͱɺ#5SFFͷجຊݪཧ w ΠϯσοΫε͕ػೳ͠ͳ͍έʔε w 1PTUHSF42-ͷΠϯσοΫεʗςʔϒϧͷϑΝΠϧߏ଄ w
࿩͞ͳ͍͜ͱ w #5SFFҎ֎ͷΠϯσοΫε w ෳ߹ΠϯσοΫε w +PJO͕བྷΉΫΤϦ w ΫΤϦΦϓςΟϚΠβ

ΠϯσοΫεͷجຊ

ͳͥΠϯσοΫεΛ࢖͏ͷ͔ ʮૣ͘ʯσʔλʹΞΫηε͢Δ

ͳͥΠϯσοΫεΛ࢖͏ͷ͔ ʮૣ͘ʯσʔλʹΞΫηε͢Δ w Կͱൺ΂ͯʁ w Ͳ͏ͯ͠ૣ͘ͳΔʁ

ͳͥΠϯσοΫεΛ࢖͏ͷ͔ ʮૣ͘ʯσʔλʹΞΫηε͢Δ w Կͱൺ΂ͯʁɹˠɹϑϧεΩϟϯ w Ͳ͏ͯ͠ૣ͘ͳΔʁɹˠɹΞΫηεͷํ๏

ʮૣ͘ʯͳΔݪཧ JE OBNF BHF TFY BMJDF GFNBMF
CPC GFNBMF DIBSMJF NBMF [PF GFNBMF

ʮૣ͘ʯͳΔݪཧ &YBNQMF6TFDBTF   ೚ҙͷϢʔβʔΛJEOBNFͰݕࡧ͍ͨ͠ &YBNQMF6TFDBTF   ೥ྸ͕/ࡀະຬͷϢʔβʔΛநग़͍ͨ͠ JE
OBNF BHF TFY BMJDF GFNBMF CPC GFNBMF DIBSMJF NBMF [PF GFNBMF

ʮૣ͘ʯͳΔݪཧ ϑΝΠϧ಺ͷ୯७૸ࠪ ɾ݅ಡΈࠐΜͰɺݕࡧ৚݅ͱর߹  ɾϨίʔυͷ݅਺෼͚ͩ܁Γฦ͢ JE OBNF BHF TFY
BMJDF GFNBMF CPC GFNBMF DIBSMJF NBMF [PF GFNBMF

ʮૣ͘ʯͳΔݪཧ ϑΝΠϧ಺ͷ୯७૸ࠪ ɾ݅ಡΈࠐΜͰɺݕࡧ৚݅ͱর߹  ɾϨίʔυͷ݅਺෼͚ͩ܁Γฦ͢ JE OBNF BHF TFY
BMJDF GFNBMF CPC GFNBMF DIBSMJF NBMF [PF GFNBMF ܭࢉίετ ɾݕࡧɿϨίʔυ਺/ʹൺྫ͢Δ  ɾσʔλ௥ՃɿϑΝΠϧͷ຤ඌʹ෇͚଍͢

ʮૣ͘ʯͳΔݪཧ ࡧҾͷಇ͖Λ͢Δϝλσʔλͷಋೖ ɾݕࡧଐੑͰιʔτࡁΈͷσʔλߏ଄  ɾ࣮σʔλʹର͢ΔϙΠϯλʢϑΝΠϧ಺ʹ͓͚Δ ϨίʔυͷόΠτҐஔͷσʔλΛ࣋ͭʣ  ɾϝλσʔλ಺Λ্Լ͔ΒڬΈܸͪͯ͠ݕࡧ  ɹɾڬΈܸͪͷൣғ಺ʹͳͬͨྻͷCZUFP⒎TFU  ɹɹΛࢀর࣮ͯ͠σʔλΛݟʹߦ͘ JE
OBNF BHF TFY BMJDF GFNBMF CPC GFNBMF DIBSMJF NBMF [PF GFNBMF BHF CZUFP⒎TFU P⒎TFUPG JE ʜ ʜ ʜ

ʮૣ͘ʯͳΔݪཧ JE OBNF BHF TFY BMJDF GFNBMF
CPC GFNBMF DIBSMJF NBMF [PF GFNBMF ܭࢉίετ ɾݕࡧ  ɹɾϨίʔυ݅਺/ʹൺྫʢϑϧεΩϟϯΑΓ͸Ϛγʣ  ɹɾϚον͢ΔϨίʔυ͕ଟ͍৔߹͸ɾɾɾʁ  ɾσʔλ௥Ճɿ  ɹɾ࣮σʔλͷϑΝΠϧ͸຤ඌ௥ه  ɹɾϝλσʔλͷ௥هίετ͸ɾɾɾʁ BHF CZUFP⒎TFU P⒎TFUPG JE ʜ ʜ ʜ

ʮૣ͘ʯͳΔݪཧ BHF CZUFP⒎TFU P⒎TFUPG JE ʜ
ʜ ʜ P⒎TFUYYY BHFͷσʔλ͕௥Ճ

ʜ ʜ P⒎TFUYYY BHFͱͳΔߦΛ୳͢ BHFͷσʔλ͕௥Ճ

ʜ ʜ P⒎TFUYYY BHFͱͳΔߦΛ୳͢ BHFͷσʔλ͕௥Ճ σʔλΛૠೖ

ʜ ʜ P⒎TFUYYY BHFͱͳΔߦΛ୳͢ BHFͷσʔλ͕௥Ճ σʔλΛૠೖ ॱ൪ʹʮ୳͠ʯͨΒޮ཰ѱ͘ͳ͍ʁ ݕࡧʗߋ৽ͷͲͪΒʹ΋Өڹ͕ग़Δ

ʜ ʜ P⒎TFUYYY ͍͔ͭ͘ͷϨϯδʹ෼ׂ͢Δ͜ͱͰݕࡧΛޮ཰Խ͢Δ ɾݕࡧ஋͕ʮͲͷϨϯδʹॴଐ͢Δ͔ʯΛௐ΂Δ  ɹɾॴଐ͍ͯ͠ͳ͍Ϩϯδͷ૸ࠪΛলུͰ͖Δ  ɹɾϨίʔυ਺ΑΓɺϨϯδͷݸ਺ͷํ͕͸Δ͔ʹখ͍͞   FYBNQMF  ԯ݅ͷϨίʔυΛԯͣͭݸͷϨϯδʹ෼ׂɻ  ୯Ұͷ஋ͰҰகʢ͋Δ͍͸ൣғʣݕࡧ͢Δ৔߹  ˠݸͷϨϯδΛௐ΂Δॲཧ ԯϨίʔυΛௐ΂Δ Ϩϯδ Ϩϯδ Ϩϯδ

ʮૣ͘ʯͳΔݪཧ ͍͔ͭ͘ͷϨϯδʹ෼ׂ͢Δ͜ͱͰݕࡧΛޮ཰Խ͢Δ ɾݕࡧ஋͕ʮͲͷϨϯδʹॴଐ͢Δ͔ʯΛௐ΂Δ  ɹɾॴଐ͍ͯ͠ͳ͍Ϩϯδͷ૸ࠪΛলུͰ͖Δ  ɹɾϨίʔυ਺ΑΓɺϨϯδͷݸ਺ͷํ͕͸Δ͔ʹখ͍͞   FYBNQMF  ԯ݅ͷϨίʔυΛԯͣͭݸͷϨϯδʹ෼ׂɻ  ୯Ұͷ஋ͰҰகʢ͋Δ͍͸ൣғʣݕࡧ͢Δ৔߹  ˠݸͷϨϯδΛௐ΂Δॲཧ
ԯϨίʔυΛௐ΂Δ Ϩϯδ Ϩϯδ Ϩϯδ ஋ ஋ ɾ ɾ ɾ ɾ ɾ ɾ Ϩϯδ ɾ ɾ ɾ ɾ ɾ ɾ

ԯϨίʔυΛௐ΂Δ Ϩϯδ Ϩϯδ Ϩϯδ ɾ ɾ ɾ ɾ ɾ ɾ Ϩϯδ Ϩϯδ Ϩϯδ ɾ ɾ ɾ ɾ ɾ ɾ

ԯϨίʔυΛௐ΂Δ Ϩϯδ Ϩϯδ Ϩϯδ ɾ ɾ ɾ ɾ ɾ ɾ Ϩϯδ Ϩϯδ Ϩϯδ ਌Ϩϯδ ɾ ɾ ɾ ɾ ɾ ɾ

ԯϨίʔυΛௐ΂Δ Ϩϯδ Ϩϯδ Ϩϯδ ɾ ɾ ɾ ɾ ɾ ɾ Ϩϯδ Ϩϯδ Ϩϯδ ਌Ϩϯδ Ϩϯδ෼ׂͯ͠ɺଟ਺ͷ஋͔Β ޮ཰Α͘ݕࡧͰ͖Δ໦ߏ଄ ˠ#5SFF ɾ ɾ ɾ ɾ ɾ ɾ

খٳࢭ w ϑϧεΩϟϯͰݕࡧ͢ΔͱɺϨίʔυ਺ʹൺྫ͢Δݕࡧίετ͕͔͔Δʢγʔέ ϯγϟϧΞΫηεʣ w ݕࡧ༻ͷʮϝλσʔλʯΛಋೖ͠ɺ࣮σʔλͷݕࡧޮ཰Λ޲্͢Δ w ݕࡧଐੑͰιʔτࡁΈͰɺରԠ͢Δ࣮σʔλ΁ͷϙΠϯλΛ࣋ͭσʔλߏ଄ w ϥϯμϜΞΫηεΛޮ͔ͤΔ͜ͱͰݕࡧޮ཰Λվળ͢Δ
w ϝλσʔλʢΠϯσοΫεʣࣗ਎ͷݕࡧ΋ޮ཰Խ͢Δඞཁ͕͋Δ w Ϩϯδ෼ׂͯ͠ɺ໦ߏ଄ͷσʔλͱͯ͠ѻ͏ͱݕࡧޮ཰͕ྑ͍ˠ#5SFF

ʮૣ͘ʯͳΔݪཧʢ࠶ʣ JE OBNF BHF TFY BMJDF GFNBMF
CPC GFNBMF DIBSMJF NBMF [PF GFNBMF ܭࢉίετ ɾݕࡧ  ɹɾϨίʔυ݅਺/ʹൺྫʢϑϧεΩϟϯΑΓ͸Ϛγʣ  ɹɾϚον͢ΔϨίʔυ͕ଟ͍৔߹͸ɾɾɾʁ  ɾσʔλ௥Ճɿ  ɹɾ࣮σʔλͷϑΝΠϧ͸຤ඌ௥ه  ɹɾϝλσʔλͷํ͸ɾɾɾʁ BHF CZUFP⒎TFU P⒎TFUPG JE ʜ ʜ ʜ

ΠϯσοΫεΞΫηε JE OBNF BHF TFY BMJDF GFNBMF
CPC GFNBMF DIBSMJF NBMF [PF GFNBMF BHF CZUFP⒎TFU P⒎TFUPG JE P⒎TFUPG JE 2VFSZ lBHFz ΠϯσοΫεϑΝΠϧ σʔλϑΝΠϧ ʢ࣮σʔλʣ

CPC GFNBMF DIBSMJF NBMF [PF GFNBMF BHF CZUFP⒎TFU P⒎TFUPG JE P⒎TFUPG JE 2VFSZ lBHFz #USFFJOEFYΛݕࡧ

CPC GFNBMF DIBSMJF NBMF [PF GFNBMF BHF CZUFP⒎TFU P⒎TFUPG JE P⒎TFUPG JE 2VFSZ lBHFz #USFFJOEFYΛݕࡧ ΠϯσοΫε͕ࢦ͢ΦϑηοτͰ ࣮σʔλͷσʔλϑΝΠϧΛࢀর

ΠϯσοΫεΞΫηεϚον͢Δ݁Ռ͕ଟ͍৔߹ JE OBNF BHF TFY BMJDF GFNBMF
CPC GFNBMF DIBSMJF NBMF [PF GFNBMF BHF CZUFP⒎TFU P⒎TFUPG JE P⒎TFUPG JE 2VFSZ lBHFz

CPC GFNBMF DIBSMJF NBMF [PF GFNBMF BHF CZUFP⒎TFU P⒎TFUPG JE P⒎TFUPG JE 2VFSZ lBHFz #USFFJOEFYΛݕࡧ

CPC GFNBMF DIBSMJF NBMF [PF GFNBMF BHF CZUFP⒎TFU P⒎TFUPG JE P⒎TFUPG JE 2VFSZ lBHFz #USFFJOEFYΛݕࡧ ɾ ɾ ɾ ΠϯσοΫε͕ࢦ͢ΦϑηοτͰ ࣮σʔλͷσʔλϑΝΠϧΛࢀর ʢϚονͨ͠ճ਺͚ͩϥϯμϜΞΫηεʣ

CPC GFNBMF DIBSMJF NBMF [PF GFNBMF BHF CZUFP⒎TFU P⒎TFUPG JE P⒎TFUPG JE 2VFSZ lBHFz #USFFJOEFYΛݕࡧ ɾ ɾ ɾ ΠϯσοΫε͕ࢦ͢ΦϑηοτͰ ࣮σʔλͷσʔλϑΝΠϧΛࢀর ʢϚονͨ͠ճ਺͚ͩϥϯμϜΞΫηεʣ ɹϑϧεΩϟϯΑΓޮ཰ѱ͘ͳ͍ʁ🤔🤔 ɹ

CPC GFNBMF DIBSMJF NBMF [PF GFNBMF BHF CZUFP⒎TFU P⒎TFUPG JE P⒎TFUPG JE 2VFSZ lBHFz #USFFJOEFYΛݕࡧ ɾ ɾ ɾ ΠϯσοΫε͕ࢦ͢ΦϑηοτͰ ࣮σʔλͷσʔλϑΝΠϧΛࢀর ʢϚονͨ͠ճ਺͚ͩϥϯμϜΞΫηεʣ ɹϑϧεΩϟϯΑΓޮ཰ѱ͘ͳ͍ʁ🤔🤔 ɹΠϯσοΫεܦ༝Ͱݟʹߦ͘෼͚ͩɺΉ͠Ζखؒ૿͑ͯΔ

ࡶͳΠϯσοΫεͱΫΤϦʹҙຯແ͠ɺͱ͍͏࿩ ݕࡧ৚݅Ͱ΄ͱΜͲσʔλΛߜΕ͍ͯͳ͍৔߹͸ޮՌ͕ͳ͍ w ؇͍৚݅ͷΫΤϦ͹͔Γ࢖ΘΕ͍ͯΔʗσʔλͦͷ΋ͷͷ෼෍͕ภ͍ͬͯΔέʔε w ʮΧʔσΟφϦςΟʯͬͯɺ͜ͷ΁Μͷ࿩ w ෼෍ͷภΓʹؔͯ͠͸ɺ෦෼ΠϯσοΫεͷར༻ͰղফͰ͖Δ৔߹΋͋Δ  ʢFHײછ঱ͷཅੑױऀͷݕࡧΛ͍ͨ͠ˠCPPMܕΧϥϜͷཅੑଆͷ஋ʹ෦෼Πϯ σοΫεΛద༻͢Δʣ
w ࣮ࡍʹ͸ΫΤϦΦϓςΟϚΠβ͕ʢΠϯσοΫεΞΫηε͸ίετ͕ߴ͍ͱ൑அͯ͠ʣϑ ϧεΩϟϯʹ੾Γସ͑ͨΓ͢Δ

ࡶͳΠϯσοΫεͱΫΤϦʹҙຯແ͠ɺͱ͍͏࿩ w ΠϯσοΫεΛ࡞Ε͹࡞Δ͚ͩɺߋ৽࣌ͷίετ͕૿͑Δ w ໦ߏ଄ͷϊʔυʹ৽͍͠σʔλΛૠೖ͢Δ w ʢϨίʔυ਺͕૿͑ͯʣ໦ͷ֊૚Λ૿΍ͨ͘͠ͳͬͨʜ w ۭ͖ྖҬͷ૟আʢ7"$66.ʣ

1PTUHSF42-ͷΠϯσοΫεͱ  σʔλϑΝΠϧͷߏ଄

🙇🙇🙇ؒʹ߹͍·ͤΜͰͨ͠ ʢ༧ఆͯͨ͠΋ͷʣ w ςʔϒϧɺΠϯσοΫεͷ0*%Λௐ΂Δ w 1(%"5"CBTFͷԼΛ୳ݕ w ΠϯσοΫεͷ0*%Λ࣋ͭϑΝΠϧΛIFYEVNQ w ϧʔτϖʔδΛEVNQͯ͠L#ͷϖʔδΛோΊΔ

·ͱΊ

·ͱΊ w ΠϯσοΫεʢ#5SFFʣͷΞΠσΞ͸ɺࡧҾͱͳΔϝλσʔλΛ௥Ճ͢Δ͜ͱͰσʔλϑΝΠ ϧ΁ͷϥϯμϜΞΫηεΛఏڙ͢Δ͜ͱ w ͘͝গྔͷσʔλΛ୳͠ग़͢৔߹͸#5SFFΛ༻͍ͨϥϯμϜΞΫηε͕༗ޮʹػೳ͢Δ w औΓग़͢σʔλ͕େྔʹ͋Δ৔߹ͳͲ͸ɺΉ͠ΖϑϧεΩϟϯʢγʔέϯγϟϧΞΫηεʣ ͷํ͕ޮ཰͕ྑ͍ w
ϝλσʔλࣗ਎ͷݕࡧ΍ߋ৽͕௥Ճίετͱͯ͠ൃੜ͢Δ w ιʔτࡁΈͷ஋Λ໦ߏ଄Ͱදݱ͢Δ͜ͱͰੑೳվળ w ར༻ऀଆͰ΋ɺޮՌͷͳ͍ΠϯσοΫεɺҙਤͷͳ͍ΠϯσοΫεΛͳΜͱͳ͘௥Ճ͠ͳ͍ ͜ͱ

ࢀߟจݙ

w (JU)VCQPTUHSFTRMQPTUHSFTRM UBH3&-@@ w 1PTUHSF42-ٕज़จॻ w ಺෦ߏ଄͔ΒֶͿ1PTUHSF42-ઃܭɾӡ༻ܭըͷమଇ4PGUXBSF %FTJHOQMVT

[JTF2021] 結局インデックスってなんなんですか？/lets-learn-about-b...

[JTF2021] 結局インデックスってなんなんですか？/lets-learn-about-b-tree-index

More Decks by hassaku63

Other Decks in Technology

Featured

Transcript