[面接質問】DB Indexとは？

データベーステーブルの検索速度を向上させるためのデータ構造

インデックス使用のメリット

• テーブル参照速度の向上によるパフォーマンス改善

• システム負荷を減らせる

インデックス使用のデメリット

• DB インデックス用に追加の保存領域が必要になる

• DB 管理のための追加作業とオーバーヘッドが発生する

インデックスの管理

インデックスは常に最新の整列状態を保ってこそ目的の値を素早く探索できるため、データが頻繁に更新される属性にインデックスを張ると、逆にオーバーヘッドによる性能低下を招くことがある。

• INSERT: 挿入時に挿入されたデータのインデックスを追加

• DELETE: 削除されたデータのインデックスを「未使用」として処理する

• UPDATE: 既存インデックスを未使用化 + 更新後データのインデックスを追加

使用するデータ構造

• B+ Tree

B Tree の改良版

• リーフノードのみにデータを格納

• リーフノード同士は連結リストの形を持つ

• Hash Table

Key - Value のペアでデータを格納 非常に短時間でデータを探索できる 不等号比較に不向きなのであまり使わない (整列されないため)

インデックスの分類

1. Key による分類

• 主インデックス: 主キーを含む (Key の順序 = レコードの順序)

• 補助インデックス: 主キーを含まない (Key の順序 != レコードの順序)

2. ファイル組織による分類

• 集中インデックス

• 非集中インデックス

3. データ範囲による分類

• 密インデックス

• 疎インデックス

参考

brunchstory by Nathan