Para responder diretamente à sua pergunta:sim, você pode indexar à esquerda (zip, 5).
alter table tblName add index (zip(5));
E se você quiser que a consulta possa usar o índice para pesquisar todas as colunas:
alter table tblName add index (cat_id, subcat_id, zip(5));
