DB関連まとめ(index, transaction, foreign key, 正規化など) - Qiita

indexの仕組み。なんで早くなるのか？ B-treeにより、データをフルスキャンしなくて済むようになるため [補足] indexを貼らないと、大量のレコードが入っているテーブルから1行のレコードを検索するのに頭から順番に検索する→時間がかかる indexを貼る事によって二分探索木→AVL木の良い点を引っ張ってきて改良された B-treeというAVL木が一般化され、かつ多分岐の平行木構造を持ったものが使われ、並び替えを行う事が無くなるため処理が高速になります。 普通は 1 ~ 10まである中で8を検索したい際に 1-2-3-4-5-6-7-8と発見されるが 二分探索を使うと のように（10までしかないので少ないが), 8は6より大きい→9へ 9より小さい→8へ という感じで2回で見つけることができる たった10個でここまで見つける回数が減るので、データの量が増えれば増えるほど効果が出てくる