Структура базы данных магазина/каталога для SQL. Как лучше хранить атрибуты и их значения в БД?
Неверно в корне.
Вы нарисовали по сути EAV (есть такая готовая схема данных под эту задачу - погуглите, примеров много).
Плюсы:
Удобно ложиться в реляционную модель, удобно программируется (если вам удобно работать с реляционной моделью), на первый взгляд хорошо подходит под любую реляционную СУБД (MySQL, PostgreSQL, Oracle).
Минусы:
Неоправдано малоэффективно по производительности.
Есть решения на порядок более быстрые.
Впрочем, если у вас каких то жестких требований на производительность или на минимизацию затрат на сервер - годится.
По мне так EAV удобен как средство редактирования (ну и хранения первичной информации).
А вот собственно сам поиск гораздо эффективнее осуществляется на full-text search engines, например:
SphinxSearch (или его клон Мантикора), ElasticSearch и т.п.
И чем по большему количеству фильтров идет поиск - тем больше этот разрыв (хотя он и по одному фильтру уже весьма заметен).
В наиболее развитых full-text search engine поиск по свойствам является "дешевой" операцией, совершенно совместимой с основным полнотекстовый поиском. 
Более того, работа с множественными фильтрами по свойствам в этих движках даже проще полнотекстового поиска (так как фильтры не нужно разбивать на слова, прогонять через алгоритм стемминга с его возможными косяками - они уже "готовы к употреблению" сразу).
Бонусом практически "бесплатно" получаете т.н. "фасеточные итоги", отвечающие на вопрос "сколько у нас товаров с таким то свойством" (это часто используется в отображении фильтров на сайтах).
====================
Вывод:
Если вам принципиально на MySQL - просто см. описание схемы данных EAV. Она как раз именно что для этого.
Если вам нужно чтобы все летало - см. SphinxSearch (он крайне быстр и нетребователен к ресурсам).
P.S.:
SphinxSearch
Умеет выдирать данные из MySQL. На их основании строит уже свой собственный узкоспециализированный но очень быстрый поиск для выборок, в вашем случае, по названию и по свойствам товаров.
Я в подобной ситуации, использовал поле с типом JSON. Т.е. содержимое такого поля у одного товара может быть таким: [ "color" : black, "size" : 42, "gender" : "male", "season" : "winter"], а у другого следующим : [ "color" : black, "size" : 42,  "kind" : "mountain", "sole" : "vibram"]. Нынешний MySQL позволяет по таким полям осуществлять поиск, а в ЯП имеются функции по раскодировке JSON в обычный массив.