For categories and sub-categories to any level, along with products belonging to multiple categories, I would start with:
Categories:
category_id
parent_category_id foreign key (Categories.category_id)
... other category information ...
primary key (category_id)
Products:
product_id
... other product information ...
primary key (product_id_id)
ProductCategories:
product_id foreign key (Products.product_id)
category_id foreign key (Categories.category_id)
primary key (category_id,product_id)
index (product_id)
This way you can reach your goal of a hierarchy of categories as well as achieving a many-to-many relationship between products and categories.
You can select a product ID belonging to multiple categories (e.g., 3 and 4) with a query like:
select a.product_id
from Products a, Products b
where a.product_id = b.product_id
and a.category_id = 3
and b.category_id = 4