Имеется в виду не PRIMARY KEY, а обычный INDEX.
Как его добавить в таблицу и какой он бывает (уникальный и неуникальный) описывать не надо - знаю.
Вопрос в том, для чего он нужен? Может ли он ускорить сортировку и поиск? Для каких столбцов его логично применять.
Например, есть таблица новостей (примитивный пример):

В этой таблице будет производиться поиск по полям title, abstract, html и сортировка по createDate. Каким образом расставить индексы, чтобы ускорить поиск и сортировку? Какие у индексов будут плюсы и минусы?

поиск - да, сортировку - нет.
я бы тут сделал FULLTEXT индекс на поля title, abstract и html.

Для этого собственно индексы и нужны. Грубо говоря индекс - это те же данные, только отсортированные.

Для тех, которые птинимают участие в "WHERE" части запроса.

Индексы ускоряют поиск, хотя мы делали на практической работе в Универе с индексами. Они показали максимальную скорость поиска при работе с числовыми данными, с текстовыми ситуация осталась таже. Хрень такая и причем у всех.