ネクストキーロックとは

ANSI/ISO SQL では、並列トランザクションにおける正常ではないリード現象【Read phenomena】として以下の３つを定義しています。

ダーティリード【Dirty Reads】
並列実行中の他のトランザクションが書き込んだ未コミットのデータを読み込んでしまう。

ノンリピータブルリード【Non-repeatable Reads】
並列実行中の他のトランザクションが更新しコミットしたデータを読み込んでしまうため、以前読み込んだデータを再度読み込むと異なる値となる。

ファントムリード【Phantom Reads】
並列実行中の他のトランザクションが挿入しコミットしたレコードを読み込んでしまうため、以前存在しなかった行データが読めてしまう。

トランザクション分離レベル【Isolation levels】は、これらのリード現象が発生するかしないかによって表すことができます。

分離レベル	ダーティリード	ノンリピータブルリード	ファントムリード
Read uncommitted	○	○	○
Read committed	×	○	○
Repeatable read	×	×	○
Serializable	×	×	×

MySQL InnoDB のデフォルトの分離レベルは Repeatable read ですが、ファントムリードが発生しないよう工夫が施されています。
この仕組みがネクストキーロックと呼ばれるアルゴリズムです。

ネクストキーロックとは
WHERE 句で指定した範囲内で他のトランザクションから INSERT（あるいは DELETE）ができないように、実レコードが存在しないインデックスの隙間（ギャップ）をロックします（ギャップロック）。
さらに指定範囲を超えた直近の実レコードもロックします（レコードロック）。
このギャップロックとレコードロックの組み合わせがネクストキーロックです。
ネクストキーロックは SELECT（for update）の他、UPDATE、DELETE でも設定されます。

PostgreSQL のファントムリード対応

ちなみに PostgreSQL の Repeatable read では、後続のトランザクションがエラー復帰するという形でファントムリードが発生しないようにしています。
このため PostgreSQL では、エラーを受け取って再度トランザクション全体を始めからやり直すという実装が必要になります。

どのようにロックがかかるか

説明のために１つのテーブルを用意しました。

pkey	value
10	10
20	20
30	30

pkeyがプライマリキーで、pkey=10, 20, 30 のレコードにデータが格納されています。

a）WHERE 条件で範囲を指定した場合

b）WHERE 条件の範囲の境界に実レコードが存在する場合

c）一意な WHERE 条件が空振りした場合はギャップロックのみ

d）INSERT はギャップロックがかからない

さて、上図を眺めていると、なぜネクストキーをロックするのか、なぜギャップをすべて埋めてしまうのか、なぜ b) のパターンは次のギャップまでロックをかけてしまうのか、などなどの疑問が沸いてくると思います。

これは恐らくギャップロックという仕組みの実装の都合上、仕方なくこのようになっているだけだと思われます。
性能面やアルゴリズムのシンプルさを考慮しての結果なのでしょう。
明らかに MySQL 側の都合でしかありませんので、この辺りなぜそうなのかを突き詰めて考えず、こうなるのだと単純に覚えておくだけに留めておいた方が良いかと思います。
個人的には、このギャップロックの仕組みは性能面と機能面を考慮した、なかなかバランスの良い設計だなと思っています。

どのようにロックの競合が起きるか

大まかに以下の２つの法則を覚えておくと良いでしょう。

・ギャップロック同士は競合しない
・ギャップロックとレコードロックは競合する（もちろんレコードロック同士も競合する）

A）ギャップロック同士は競合しない