Советую глянуть в сторону NoSQL решений, например MongoDB.
А по поводу mysql щас подумаю, чуть позже отпишу.
** подумал..
4 таблицы:
items - товары
categories - список категорий (под-категории не учитываю для простоты изъяснения)
options - характеристики товаров (связь один ко многим)
items_categories - категории товаров (связь один ко многим)
Суть вот в чем, у каждого товара может быть ноль или много характеристик. Характеристики имеют ключ и значение, значение может быть типа integer или varchar. В этом заключается проблема, не знаю как её можно решить изящно. Как вариант делать два поля string_value и int_value с соответствующим типом. А при поиске выбирать поле по типу искомого.
items_categories содержит в себе поля category_id и item_id, таким образом список категорий того или иного товара достигается элементарным запросом с inner join
Пример выборки категорий товара
SELECT `categories`.* FROM `categories` INNER JOIN `items_categories` ON `categories`.`id` = `items_categories`.`category_id` WHERE `items_categories`.`item_id` = 123
Пример выборки товара с его характеристиками
SELECT `items`.* , `options`.* FROM `items`, `options` WHERE `items`.`id` = 123 AND `options`.`item_id` = `items`.`id`
В общем как-то так..
