Index MySQL sur la première partie de la chaîne

Pour répondre directement à votre question :oui, vous pouvez indexer à gauche (zip, 5).

alter table tblName add index (zip(5));

Et si vous souhaitez que la requête puisse utiliser l'index pour rechercher toutes les colonnes :

alter table tblName add index (cat_id, subcat_id, zip(5));