mysql encuentra la identificación más pequeña + única disponible

Puede obtener el ID mínimo disponible mediante esta consulta:

SELECT MIN(t1.ID + 1) AS nextID
FROM tablename t1
   LEFT JOIN tablename t2
       ON t1.ID + 1 = t2.ID
WHERE t2.ID IS NULL

Lo que hace es que une la tabla consigo misma y comprueba si el min+1 ID es null o no. Si es nulo, entonces ese ID está disponible. Suponga que tiene la tabla donde ID son:
1
2
5
6

Entonces, esta consulta le dará un resultado como 3 que es lo que quieres.