Оба конца должны быть с индексами.
Один хвост проверяется при вставке и изменении таблицы, чтобы поле ссылка вело куда-нибудь.
Обратная проверка выполняется при изменении/удалении из таблицы справочника, чтобы не удалить случайно строку на которую кто-то ещё ссылается.
innodb требует, чтобы индекс на referenced (на которую ссылаемся) табличке уже был. Индекс на табличке которой alter table делаем будет неявно создан если отсутствовал. Таким образом innodb требует наличие индексов на обоих концах FK.
