今までカラムにインデックスを盲目的に貼っているだけだったが、ひょんなことからその仕組みが気になったのでまとめた
インデックスとは
ググってみて出てきたもの
インデックスとは、データの検索速度を向上させるために、どの行がどこにあるかを示した索引のこと
うーん😔 わかりにくい
実際に何やってるの？？
あるカラムに対して、辞書順、数値順にデータを整理している
整理前のDB
整理後のDB(nameにインデックスを貼った)
nameが辞書順になっている！
気になったこと
辞書順になっててももし極端な話zから始まるものを探そうとしたらO(N)かかってしまい、Nによってはパフォーマンスが悪くなるのでは？？
気になったことへの解決
結論 インデックスを貼られたカラムのデータ構造はBTree もしくはB+Tree構造になっており、探索にかかる計算量はO(logN)になりかなり計算スピードが抑えられる！！
Btreeとは？？
このような木の構造をしているデータ構造のこと 木構造についてはこちら
探索の際にまず中央の数字を見て、その数より検索対象の数が大きければ右の木に、小さければ左の木にとどんどん検索対象を小さくできる。よってデータ構造をBTreeやB+Treeにしておけば、計算量がO(logN)とかなり抑えられ、非常に効率的に探索できるようになるというわけ
補足 BtreeとB+Treeの違い
-
B+Treeは末端の場所（リーフノードと言います）に全ての要素が集結している。ので範囲検索が早い
-
また、リーフノード以外のノードはデータの実態を持っておらず実際のデータを持っているのは末端のリーフノードのみという違いがある。
MongoDBはBtreeを採用しており、MySQLのinnnerDBはB+Treeを採用しているという違いもある