Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
インデックスのパフォーマンス調べてみた
Search
matumoto
October 15, 2022
Technology
130
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
インデックスのパフォーマンス調べてみた
2022/10月に行われた大LTでの発表資料です
イベントページはこちら
https://zli.connpass.com/event/261496/
matumoto
October 15, 2022
Transcript
21 slides
インデックスの パフォーマンス 調べてみた matumoto
自己紹介 • ハンドルネーム:matumoto • 本名:松本響輝 • 学年:28期 • 趣味:イカᔦꙬᔨ •
やってきた技術: ◦ ゲーム作り ◦ フロントエンド ◦ AtCoder 水💧 • Twitter:@matumoto_1234
インデックスについて
インデックスとは? • インデックスとは、データの検索速度を向上させるために、どの行がどこにあるかを示した索引のこ と (https://www.techscore.com/tech/sql/15_01 より引用) • DBのテーブルに適切にインデックスを作ることで、パフォーマンス向上につながる • MySQLなどではCREATE
TABLEなどの文でインデックスを指定できる • 例. CREATE TABLE people ( id INT, name VARCHAR(512), age INT, INDEX name_INDEX (name) )
インデックスがどう使われるのか? • クエリに対応して、インデックスが自動で使われる • 例. ◦ peopleという名前の、こんなテーブルがあったとする id name age
1 matumoto 20 2 Aizu Taro 256 • SELECT id FROM people WHERE name = 'matumoto' というような、nameカラムに対しての検索クエリが きたとき、name_INDEXが使われる • SELECT idFROM people WHERE age = 20 というような、ageカラムに対しての検索クエリがきたらイン デックスは使われず、テーブル全体がそのまま読み込まれる
インデックスのパフォーマンス • インデックスは基本的に、ユニーク(重複がない)なもののほうがパフォーマンスが良い ◦ 例. PRIMARY KEYに基づくインデックスやUNIQUE制約のついたインデックスなど →なぜパフォーマンスが良いのか?(本題) →後述
インデックスの内部構造
インデックスを作るとどうなるか • インデックスを作ってもテーブル自体に変更が加わるわけではない • テーブルとは別にインデックス用の領域が取られ、まずはそこにアクセスする テーブル インデックス クエリ ソートとかはされていない! テーブルの場所が効率よく検索で
きるように保存されている
インデックスはどうなっているか • B-treeというようなデータ構造がよく使われている ◦ 厳密にはB+treeや、B*treeという改良版が使われることが多い
B-treeとは? • B-treeは平衡探索木の一種 ◦ よくある、平衡二分探索木とかとは違って多分木 ◦ BはBinaryではなく、Balanceの略 ◦ よくデータベース管理システムや、ファイルシステムで使用される 5
70 2 1 3 8 6 20 82 91 71 85 97
B-treeの特徴 • B-treeの特徴 ◦ 完全に平衡になっている(根から任意の葉までのパスの長さが一定 ) ◦ ノードにいくつかの値を持つ ◦ 一つのノードにm個以下の枝があるものをオーダー
mのB-treeと呼ぶ ◦ これはオーダー3のB-tree 5 70 2 1 3 8 6 20 82 91 71 85 97
挿入操作でB-treeの平衡はどうやって保っているの? • A. 気合い http://wwwa.pikara.ne.jp/okojisan/t23-java/index.html より図を引用
削除操作でB-treeの平衡はどうやって保っているの? • A. もちろん気合い http://wwwa.pikara.ne.jp/okojisan/t23-java/index.html より図を引用
B-treeの計算量 • B-treeの計算量 ◦ nを要素数とする ◦ 挿入:O(log n) ◦ 削除:O(log
n) ◦ 検索:O(log n) • AVL木や、赤黒木といった平衡二分探索木より速い? ◦ そんなことはなくて、遅い ◦ オーダーmのB-treeのノードを辿るときにO(m)回の値比較を行うので遅い ◦ データベース管理システムなどで使われるのは、「枝を辿るコスト」 >「値比較のコスト」な ため
B-treeの亜種 • B+treeというのが存在する ◦ 葉ノードがつながっており、範囲クエリに強い ◦ 葉ノードに実際のレコードが全て存在している ◦ MySQL/InnoDBなどで使われている https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
より図を引用
インデックスの パフォーマンス
インデックスのパフォーマンス • SQLクエリをEXPLAINすると表示される「type」 • 主なものとしては、以下がある ◦ const:PRIMARY KEYのインデックスやUNIQUEインデックスを使う。最速 ◦ eq_ref:JOINのときにPRIMARY
KEYのインデックスやUNIQUEインデックスを使う ◦ ref:ユニークでないインデックスを使ったときの等価検索など ◦ range:インデックスを用いた範囲検索 (0 <= key <= 10を満たすkeyを検索するなど) ◦ index:フルインデックススキャン。インデックス全体を見る ◦ all:フルテーブルスキャン。インデックスが使用されていない • なぜユニークだと早くなる傾向にあるのか?
インデックスのパフォーマンス • 検索で遅くなるのは葉ノードの走査が大きな原因の一つとしてある • 検索対象がユニークなら、見つけ次第終了できるが、ユニークでない場合は他の 葉ノードを見る必要がある • 例. 20を見つけたとしても、20が他にあるかもしれないので葉ノードを辿る必要があ る
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html より図を引用
まとめ
まとめ • インデックスの内部構造はB-treeがベースになっていることが多くて、計算量は だ いたい O(log n) ◦ 範囲クエリでk個の要素がみつかるときは、 O(log
n + k) 程度
ご静聴ありがとうございました
More Decks by matumoto
See All by matumoto
Go標準パッケージのI/O処理をながめる
matumoto
0
550
testingを眺める
matumoto
1
230
sync/v2 プロポーザルの 背景と sync.Pool について
matumoto
0
860
Goトランザクション処理
matumoto
1
100
いまいちどスライスの 挙動を見直してみる
matumoto
0
440
Go1.22のリリース予定の機能を見る
matumoto
0
110
GoのUnderlying typeについて
matumoto
0
250
Typed-nilについて
matumoto
0
410
GoのType Setsという概念
matumoto
0
73
Other Decks in Technology
See All in Technology
異夢同船〜異なる夢でも同じ船でなんとかする〜
fortegp05
1
560
PHPで家庭用ゲーム機の専用コントローラーをMIDIデバイスとして扱ってみる
wind111
0
170
市販IoT機器や自作IoT機器とHomeAssistantを駆使して家の電気代をできる限り見える化する方法の考案
harutiro
0
400
OWASP AI Agentic Top10に準拠するクラウドネイティブなガードレールの実践(CNDW 2026)
keitah
1
370
Terraform 0 to 100:100個以上のリポジトリを常に最新にし続けるための自動化
sue445
2
1.2k
サーバーラックは作る時代! 3Dプリンターで作る10インチラックのススメ
jacopen
2
490
SORACOM × AWS IoT Core でSREする
butadora
0
120
個人ASを取得して、自宅Kubernetes上のVMをグローバルIPで公開した話
munenick
0
210
共通基盤の実装に Kotlin - Quarkus を選定した理由と採用したアーキテクチャ
nealle
1
150
From vibe coding to reliable (agentic) development
jcabot
0
130
マネージャーをエスパーにしない マネジメントされる側から始める、働きやすい現場づくり
comi190327
1
830
おうち環境でも「なるべく止めたくない!」 ― おうち環境の機器冗長化の理想と現実
yuutosi
1
620
Featured
See All Featured
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
123
22k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
254
23k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
10
1.4k
Speed Design
sergeychernyshev
33
2.2k
From Legacy to Launchpad: Building Startup-Ready Communities
dugsong
0
380
How to Grow Your eCommerce with AI & Automation
katarinadahlin
PRO
2
350
Bootstrapping a Software Product
garrettdimon
PRO
306
120k
RailsConf 2023
tenderlove
30
1.6k
技術選定の審美眼(2025年版) / Understanding the Spiral of Technologies 2025 edition
twada
PRO
121
130k
Why Your Marketing Sucks and What You Can Do About It - Sophie Logan
marketingsoph
0
470
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
35
2.6k
Utilizing Notion as your number one productivity tool
mfonobong
4
650