Как переписать структуру таблиц или запросы, чтобы работал индекс для моих выборок?
Для начала объясню почему индексы в вашем случае не работают и не могут работать.
> OR links.domain LIKE CONCAT(sites.domain, '.%')
CONCAT - это функция, и вы работаете с результатом функции.
Т.е. получается что в вашем запросу нужно:
1. выбрать все строки из links 
2. подсодеденить к каждой строке по sites.domain  или sites.domain результат фунции.
=> нужно посчитать каждую строку каждый раз.
Это очень много.
что я бы сделал:
1. создал таблицу доменов
в ней:id | main_id |domain
1 | 1 | com.youtube
2. | 1 |com.youtube.www
3. | 1 |com.youtube.subdomain
Во всех таблицах - перешёл бы на этот ключ. 
2. тогда ваша выборка сокращается до:SELECT links.id, links.url, sites.id AS site_id, sites.description 
FROM links
LEFT JOIN domains ON links.domainId = domains.id
LEFT JOIN sites ON sites.id = domains.main_id
(смутно понимаю что вы хотели в этом запросе, поэтому уж не обессудьте :) )
Т.е. основной посыл:
переходите на int- ключи
PS: Так же это называется нормализация базы данных. Хранить много одинаковых строк - это плохо.
3НФ будет выглядеть такdomain_zone:
  parent = ForeignKey(domain_zone)
  name = Text

site_page
  domain_zone = ForeignKey(domain_zone)  
  url = URL
Суть такова: есть корневая доменная зона "." точка. 
Есть доменная зона com, у нее parent точка
У сайта bbc.com parent будет указывать на com
Вобщем делаем аналогично DNS