プライマリキーとインデックスの違い

DBのインデックスへの混乱

インデックスを作ると、検索が早くなる。
つまりWHEREの条件にインデックスを作ったカラム名を書くと早くなるというのは
知っていたのだが、プライマリキーだけ作って、インデックスは作らないときなどが
あったのでどういうこと？と思って調べてみた。

プライマリキーとインデックスの違い

参考

http://oshiete1.watch.impress.co.jp/qa4401156.html
ずばりここに書かれており、
DB全般でほぼ同じような仕組みになっていると思われる。

引用1

SQL Serverに限らず、RDBMS全般として回答します。

主キーやuniqueキーを表定義で指定すると、「内部的に重複禁止のインデクスが作成」されます。
これは、RDBMS側で重複チェックする上で、重複禁止のインデクスがないと、母体の全件サーチが必要になるからです。

インデクスは、重複チェック以外に、以下の用途でも利用されます。
（create indexで定義する「重複可のインデクス」の場合もです）

(1)検索条件で絞り込む
(2)集合（集計と呼ぶ場合もあり）関数などでデータを見に行かずにインデクス上で値を得る
(3)order by、group by、distinctなどソートを伴う処理で、作業メモリや作業ファイルを用いたソートを発生させない

なお、参照（整合性）制約の外部キーには、自動的にインデクスは作成されないため、
「外部キーにインデクスを定義すべき」と説明しているRDBMSが多いです。

引用2

主キーというのは、主キー制約という制約の一種です。だからそれだけでは本来はインデックスとは関係がないのですが、
SQL Serverの場合(また他のDBMSでも）、主キー制約をつけると、その列には自動的にユニークインデックスが作成されます。
SQL Server Management Studioで、テーブルの中の「インデックス」の中を見てみると、主キーをつけたテーブルには
自動的に「PK_(テーブル名)」というものができているはずです。

インデックスは索引簿のようなもので、検索効率向上のためにつけるものです。
しかし、ほぼ主キー以外での検索を行わないテーブルであれば、すでにインデックスがついていますので、別途インデックスをつける必要はありません。
もし、テーブルの件数が多く、主キー以外の検索条件で検索することが多いテーブルで、その主キー以外の列を検索条件に指定することで
対象件数の絞り込みの効果が大きい場合、その列に別途インデックスを作成することが多いです

なるほど、重複禁止のためのインデクスが作られている。
そしてそのインデクスは重複チェックだけに使われるのではなく、
検索時や集合関数（SUMとか）の使用時にも使われるみたいですね。

結論

プライマリーキーとインデックスは別もの

プリマリーキーとインデックスは別物だけど、
一意キー制約用のインデックスは作られており、それは一意キー制約以外で使われるということは
わかった。プライマリキーは一意だから、プライマリキーを検索条件に入れた場合はO(1)になるのかな？

インデックスはO(1)とは全然限らない

プライマリキーは一意だからO(1)になると勝手になると仮定して話を進めるとする。
でもインデックスってのは自由にカラムに付けれる。
これはB*木というアルゴリズムで管理されることになるみたい。
で、インデックスをプライマリキーとは別に自分でつくるときはたぶんこの
B*木の速度で検索されることと思われる。

じゃあindexを作る時に気をつけることはなんなんだろう？

ソーシャルゲーム開発者なら知っておきたい MySQL INDEX + EXPLAIN入門 | 株式会社インフィニットループ技術ブログ
ここに書かれてあるみたい。