Mysql — как оптимизировать связь Many To Many?
Индексы строятся только под запросы. Если запросов, использующих этот индекс нет - то индекс только мешает работе.
Констрейты (fk и unique) - ставятся в зависимости от требования к данным, при этом мешают программисту делать глупости. Потому их лучше всегда ставить, пока не будет сделан обоснованный вывод, что их надо убрать.
По схемам - вторая будет оптимальнее. Меньше объём рабочего набора - меньше i/o. В большинстве случаев, судя по всему, будет поиск по первичному ключу - ещё меньше i/o, т.к. в innodb данные кластеризованы по первичному ключу.
И скорей всего забыли указать unsigned, это ведь наверняка ссылки на автоинкременты.
По индексам в MySQL есть хорошая статься тут.
Как пишут выше - внешние ключи нужны для сохранения связей между таблицей и предотвращения разрыва связей объектов. Если кто-то удали строчку из одной таблицы, а id о ней останется в другой - у вас будет бедлам и хаос, куча мусора и с разрастанием таблиц - просидание производительности.  Про это можно прочитать тут.
Первую схему забудьте для связей многие-ко-многим.