Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
これでわかるB-treeアルゴリズム / B-tree algorithm
Search
ハトネコエ
December 06, 2018
Technology
12
9.7k
これでわかるB-treeアルゴリズム / B-tree algorithm
・二分探索木 (binary search tree)
・AVL tree
・B-tree
・B+ tree
について順を追いながら説明。
流れを細かく書いたので、わかりやすいと思います。
ハトネコエ
December 06, 2018
Tweet
Share
More Decks by ハトネコエ
See All by ハトネコエ
Godot 4.3 と学ぶインタラクティブミュージック / Interactive Music Basics with Godot 4.3
nekonenene
0
33
Developer Consoleを使い倒そう / Use Web Browser DevTools
nekonenene
0
4
まだまだマイナー?! 未踏事業について教えます / Introduction of Mitou Project
nekonenene
1
89
Docker for Windows/macOS
nekonenene
0
5
技術的負債を防ぐには / What is the Technical Debt
nekonenene
0
290
画像処理の基礎の基礎 / Ultra Basic of Image Processing
nekonenene
0
21
伝わる文章を書こう講座 / Write the Kind Japanese Message
nekonenene
2
140
Unity で Android 自動ビルドしたかった話 / I tried Android build of Unity using Docker, but...
nekonenene
0
2.1k
なぜ社内勉強会をするのか
nekonenene
0
140
Other Decks in Technology
See All in Technology
DynamoDB でスロットリングが発生したとき_大盛りver/when_throttling_occurs_in_dynamodb_long
emiki
1
430
SSMRunbook作成の勘所_20241120
koichiotomo
3
160
複雑なState管理からの脱却
sansantech
PRO
1
150
OS 標準のデザインシステムを超えて - より柔軟な Flutter テーマ管理 | FlutterKaigi 2024
ronnnnn
0
200
TypeScriptの次なる大進化なるか!? 条件型を返り値とする関数の型推論
uhyo
2
1.7k
New Relicを活用したSREの最初のステップ / NRUG OKINAWA VOL.3
isaoshimizu
3
620
Application Development WG Intro at AppDeveloperCon
salaboy
0
190
初心者向けAWS Securityの勉強会mini Security-JAWSを9ヶ月ぐらい実施してきての近況
cmusudakeisuke
0
130
組織成長を加速させるオンボーディングの取り組み
sudoakiy
2
200
オープンソースAIとは何か? --「オープンソースAIの定義 v1.0」詳細解説
shujisado
9
1.1k
テストコード品質を高めるためにMutation Testingライブラリ・Strykerを実戦導入してみた話
ysknsid25
7
2.7k
これまでの計測・開発・デプロイ方法全部見せます! / Findy ISUCON 2024-11-14
tohutohu
3
370
Featured
See All Featured
KATA
mclloyd
29
14k
Practical Orchestrator
shlominoach
186
10k
Learning to Love Humans: Emotional Interface Design
aarron
273
40k
How GitHub (no longer) Works
holman
310
140k
GitHub's CSS Performance
jonrohan
1030
460k
Building a Modern Day E-commerce SEO Strategy
aleyda
38
6.9k
Embracing the Ebb and Flow
colly
84
4.5k
Six Lessons from altMBA
skipperchong
27
3.5k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
126
18k
Java REST API Framework Comparison - PWX 2021
mraible
PRO
28
8.2k
Writing Fast Ruby
sferik
627
61k
Product Roadmaps are Hard
iamctodd
PRO
49
11k
Transcript
͜ΕͰΘ͔Δ(?) B-tree ΞϧΰϦζϜ 2018/12/06 ࣾษڧձ ϋτωίΤ
ϋτωίΤ @nekonenene ࢲॳԻϛΫͰ͢ ͝ଘ͋ͷํ
• BͱݺΕΔ • σʔλߏͷҰछͰ͋ΔߏͷҰछ • ϧʔτ͔Βͷߴ͕͞Ұఆͷฏߧʢ͍͜͏͗ʣͷҰछ • Mongo DBͳͲͷσʔλϕʔεͷ΄͔ɺ WindowsͷϑΝΠϧγεςϜNTFS
MacͷϑΝΠϧγεςϜAPFS ͳͲͰΘΕ͍ͯΔ B-tree
• MySQLͷσʔλϕʔεΤϯδϯ InnoDB Ͱɺ ॱʑʹΞΫηε͢ΔੑೳΛ্͛ͨ B+ tree ͕ΘΕ͍ͯΔ • Oracle
Database MacͷϑΝΠϧγεςϜͩͬͨHFS+ Ͱ B* tree ͕ΘΕ͍ͯΔʢࠓճѻ͍·ͤΜʣ B-tree ѥछ
Χϯλϯͳͷ͔Β ࢝Ί͍ͯ͜͏
• ͬͱ୯७ͳߏ • খ͍͞ΛࠨԼʹɺେ͖͍ΛӈԼʹ͚͍ͭͯ͘ ೋ୳ࡧ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ ೋ୳ࡧɿྫ 10 5
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ ೋ୳ࡧɿྫ 10 5 ϊʔυ ࢠϊʔυ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ ೋ୳ࡧɿྫ 10 5 3 2
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ ೋ୳ࡧɿྫ 10 5 3 2 8
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ ೋ୳ࡧɿྫ 10 5 3 2 8 4
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ ೋ୳ࡧɿྫ 10 5 3 2 1 8 4
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ ೋ୳ࡧɿྫ 10 5 3 2 1 8 4 6
• ͷόϥϯε͕ۉʹ͍ͬͯΕɺ ཁૉ n ʹରͯ͠୳ࡧʹ͔͔Δ࠷ѱܭࢉྔ O (log n) ʹͰ͖Δ •
ͭ·Γɺσʔλ͕૿͑ͯݕࡧͷ͕࣌ؒ૿͑ͳ͍ ೋ୳ࡧͷར 10 5 2 8 16 12 20 ཁૉ n ܭࢉྔ
• ࠨԼͷਤͷΑ͏ͳภͬͨߏͷ࠷ѱͷ߹Λߟ͑Δ • ཁૉ͕ଟ͍΄ͲൺֱΛ͓͜ͳ͏ͷͰ࠷ѱܭࢉྔ O (n) ೋ୳ࡧͷܽ ཁૉ n ܭࢉྔ
10 5 3 2
ͦΕͳΒͬͨ ߏʹ͠Α͏ʂ
• ߟҊऀͷ2ਓͷ໊લ͕༝དྷʢAdelson-Velskii and Landis' treeʣ • ࠨ෦ͷߴ͞ͱӈ෦ͷߴ͕͞1ΑΓେ͖͘ͳͬͨΒ ʮͷճసʯʹΑΓ࠶ߏ͠ɺฏߧΛอͭ AVL
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 10 5
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 10 5 3 ʮ10ʯ͔Βݟͯ ࠨߴ͞ 2 ӈߴ͞ 0 ʹͳͬͯ͠·͏ ͦ͜Ͱɺͷճసʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 10 5 3 த৺ʹ͍ͨ ʮ5ʯΛʹͯ͠ ଞΛࢠʹ͢Δ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 10 5 3 2
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 10 5 3 2 8
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 10 5 3 2 8 4
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 10 5 3 2 8 4 1
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 10 5 3 2 8 4 1 ͭͳ͛ΒΕΔՕॴͷߴ͞ͷ͕ࠩ2 ͜Εͷճస͕ى͜Δʁ ? ?
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 10 5 3 2 8 4 1 ʮ5ʯ͔Βݟͯ ࠨͷߴ͞ 3 ӈͷߴ͞ 2 ʮ3ʯ͔Βݟͯ ࠨͷߴ͞ 2 ӈͷߴ͞ 1 ࠨ෦ͱӈ෦ͷߴ͞ͷࠩΛ ݟΔͷͰɺ·ͩ͑·͢
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 10 5 3 2 8 4 1 6 ʮ10ʯ͔Βݟͯ ࠨͷߴ͞ 2 ӈͷߴ͞ 0 ͷճసνϟϯεʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 10 5 3 2 8 4 1 6 த৺ʹ͍Δ ʮ8ʯΛʹ͠ɺ ଞ2ͭࢠʹ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ AVLɿྫ 8 5 3 2 6 4 1 10 ʂ
• ࠷ѱܭࢉྔ͕େ͖͘ͳΒͳ͍Α͏ɺ ͷճసΛ༻͍ɺͰ͖Δ͚ͩภΓͷͳ͍Λ࡞͍ͬͯͬͨ • ͜ͷΑ͏ͳฏୱʹ͚ۙΔߏΛ ฏߧʢ͍͜͏͗ʣͱݺͿ AVL ͓͞Β͍
• ͷߴ͕͞ߴ͘ͳΓ͍͢ • ݁Ռɺσʔλྔ͕ͱͯଟ͍߹ɺݕࡧʹ͕͔͔࣌ؒΔ • → ͦ͜Ͱ B-tree ʂ AVLͷܽ
• ֤ϊʔυʹ࣋ͨͤΔΛ1ͭͰͳ͘ෳʹ͠ɺͷߴ͞Λ͑Δ • ࠓ·ͰͷϊʔυXΑΓখ͍͔ͦ͞ΕҎ্͔ɺͷ 2ຊͷࢬ͔͍࣋ͬͯ͠ͳ͔͕ͬͨɺB-treeͰΑΓଟ͘ͷࢬΛ࣋ͭ • ྫ͑ X ͱ Y
ͷ 2 ͭͷΛϊʔυʹͭͱܾΊͨ߹ɺ Xະຬ / XҎ্ͰYະຬ / YҎ্ ͷ3ຊͷࢬΛϊʔυ࠷େͰ࣋ͭʢΦʔμʔ3ʣ ͦ͜Ͱ B-tree
• ϊʔυ͕࠷େͰ࣋ͭࢬͷʹԠͯ͡ɺ ʮΦʔμʔ m ͷB-treeʯͱ͍͏ݴ͍ํΛ͢Δ • Φʔμʔ 3 ʙ 5
͕Α͋͘ΔΒ͍͠ • ࠓճɺΦʔμʔ 3 ͷ B-tree ʢͭ·Γϊʔυʹ2ͭͷΛ࣋ͭʣ ʹ͍ͭͯྫΛݟ͍ͯ͘ɻ ࢠϊʔυΛ2ʙ3࣋ͭ͜ͱ͔Βɺ2-3 tree ͱݺΕΔ Φʔμʔ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 5 10 ϊʔυʹ2ͭͷ Λͭ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 5 10 ϊʔυʹ 3ͭͷ͕…… 3 த৺ͷϊʔυʹҠಈʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 5 10 3
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 5 10 2 3
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 5 8 2 3 10
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 5 8 2 3 10 4
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 5 8 2 3 10 4 த৺ͷ ϊʔυʹҠಈʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 5 8 2 3 10 4 Զ͕ϊʔυͩʂ த৺ͷ ϊʔυʹҠಈʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 3 8 2 10 4 5
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 3 8 1 10 4 5 2
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 3 6 1 8 4 5 2 10 த৺ͷ ϊʔυʹҠಈʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 3 6 1 8 4 5 2 10 ͋Ε……͓अຐʁ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 3 6 1 8 4 5 2 10 த৺ͷ ϊʔυʹҠಈʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B-treeɿྫ 3 6 1 8 4 5 2 10 ߴ͞Ξοϓʂ ˍʂ
• جຊͷΞϧΰϦζϜ B-tree • ࠷ԼͷϊʔυΛϙΠϯλͰͭͳ͗߹Θͤͨ͜ͱͰɺ খ͞ͳ͔Βେ͖ͳॱʑʹΞΫηε͍ͯ͘͠ ͱ͍͏ڍಈͷύϑΥʔϚϯεΛ্͛Δ͜ͱʹޭ • ઌ΄Ͳಉ༷ɺΦʔμʔ 3
ʢϊʔυ͕࠷େͰ࣋ͭࢬ͕3ຊʣͷ B+ tree ʹ͍ͭͯݟ͍ͯ͘ B+ tree
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 10
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 10 ϊʔυʹ 3ͭͷ͕…… 3 த৺ͷϊʔυʹҠಈʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 3 10 ϊʔυҠಈͭͭ͠… ͱͷ͢ʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 3 10 ࠷Լಉ࢜Λ ϙΠϯλͰͭͳ͙ʂ ͜Ε͕ B+ tree ͷ Ұ൪ͷಛʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 3 10
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 2 10 3
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 2 8 3 10 த৺ͷ ϊʔυʹҠಈʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 2 8 3 10 8 ͱͷ͢
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 2 8 3 10 8 4 த৺ͷ ϊʔυʹҠಈʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 2 8 3 10 8 4 3 ͱͷ͢
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 8 3 10 8 4 3 3ͭʹͳͬͯ͠·ͬͨ…… 2
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 8 3 10 8 4 3 2 த৺ͷ ϊʔυʹҠಈʂ 3ͭʹͳͬͯ͠·ͬͨ……
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 3 8 5 Θ͔Γ͍͢Α͏ ্෦͚ͩߟ͑Δ ৽͍͠ύύͩΑ ͱͷ͢
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 3 8 5 Θ͔Γ͍͢Α͏ ্෦͚ͩߟ͑Δ 5ະຬ 5Ҏ্
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 8 3 10 8 4 3 2 ͳͷͰಉ༷ʹ……
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 8 3 10 8 4 3 2 5 ͜͏ͳΔʂ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 8 3 10 8 4 3 2 5 ʢҙʣ ͜͏ͳΒͳ͍ Φʔμʔ 3 ͷ BͰ ࠷ 2 ͭͷ ࢠϊʔυΛ࣋ͭ
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 8 3 10 8 4 3 2 5 Λͯ࣍͠…
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 8 3 10 8 4 3 1 5 2
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 8 3 10 8 4 3 1 5 2 6
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 8 3 10 8 4 3 1 5 2 6 ʂ
• ࠷Լͷϊʔυ͕ϙΠϯλͰͭͳ͕͍ͬͯΔͨΊɺ খ͞ͳ͔Βେ͖ͳॱʑʹΞΫηε͍͖͍ͯͨ͠߹ʹɺ ຖճݕࡧͷखؒΛڬ·ͳͯ͘ࡁΉ • ͳ͓ɺ͜ͷ࠷ԼͷϊʔυΛ ʮϦʔϑϊʔυʢleaf nodesʣʯͱݴ͍·͢ B+ tree
͓͞Β͍
• 10 → 5 → 3 → 2 → 8
→ 4 → 1 → 6 ͷॱʹೖΕ͍͖ͯ·͢ B+ treeɿྫ 5 5 8 3 10 8 4 3 1 5 2 6 Ϧʔϑϊʔυ
• ΧϥϜʹΠϯσοΫεΛషΔ͜ͱͰɺ B+ tree ͷߏ͕࡞ΒΕɺॱʑʹͳ͍ͬͯΔͷͰ ൣғݕࡧ͕εϐʔυग़͍͢͠ • ͳ͓ɺInno DB ͰϦʔϑϊʔυؒͷϙΠϯλ͕
ҰํͰͳ͘ํʹͳ͍ͬͯΔ Inno DB ʹ͓͍ͯ 5 8 10 4 3 1 2 6
• AVL https://www.cs.usfca.edu/~galles/visualization/AVLtree.html • B-tree https://www.cs.usfca.edu/~galles/visualization/BTree.html • B+ tree https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
• ͦͷଞ https://www.cs.usfca.edu/~galles/visualization/Algorithms.html ศརͳγϛϡϨʔλʔ