In row-level locking, InnoDB uses an algorithm called next-key locking. InnoDB performs the row-level locking in such a way that when it searches or scans an index of a table, it sets shared or exclusive locks on the index records it encounters. Thus, the row-level locks are actually index record locks.

In addition, the next-key lock that InnoDB sets on an index record affects the “gap” before that index record. If a user has a shared or exclusive lock on record R in an index, another user cannot insert a new index record immediately before R in the index order. (A gap lock refers to a lock that locks only a gap before some index record.)

When InnoDB scans an index, it can also lock the gap after the last record in the index.

This next-key locking of gaps is done to prevent the so-called “phantom problem.” Suppose that you want to read and lock all children from the child table having an identifier value greater than 100, with the intention of updating some column in the selected rows later:

SELECT * FROM child WHERE id > 100 FOR UPDATE;

Suppose that there is an index on the id column and the table contains row with id values of 90 and 102. The query scans that index starting from the first record where id is bigger than 100. If the locks set on the index records would not lock out inserts made in the gaps (in this case, the gap between 90 and 102), another session might insert a new row into the table with an id of 101. If you were to execute the same SELECT within the same transaction, you would see a new row with an id of 101 in the result set returned by the query. This is contrary to the isolation principle of transactions: A transaction should be able to run so that the data it has read does not change during the transaction. If we regard a set of rows as a data item, the new “phantom” child would violate this isolation principle.

As previously mentioned, InnoDB can also lock the gap after the last record in the index. Just that happens in the previous example: The locks set by InnoDB prevent any insert into the table where id would be bigger than 100.

You can use next-key locking to implement a uniqueness check in your application: If you read your data in share mode and do not see a duplicate for a row you are going to insert, then you can safely insert your row and know that the next-key lock set on the successor of your row during the read prevents anyone meanwhile inserting a duplicate for your row. Thus, the next-key locking allows you to “lock” the non-existence of something in your table.

In MySQL 5.1, if the READ COMMITTED isolation level is used or the innodb_locks_unsafe_for_binlog system variable is enabled, there is no InnoDB gap locking except for foreign-key constraint checking and duplicate-key checking. Also, record locks for non-matching rows are released after MySQL has evaluated the WHERE condition.