Q:

How to design a MySQL database for zipcode based service? 

I'm trying to design a MySQL database to store user zipcode preferences for providing a particular service.  For example, user A who is a plumber is willing to travel to x,y, and z zipcodes to provide his service. 
I've been thinking about the various ways of implementing this, and scalability is very important.  Also, I would like to have a mapping between the zip code and the city name(s). 
One way of designing this is to create a huge table with each column representing a zip code and each row will store a user entry with the zip code preferences.  But as I add zip codes and say millions of users, how will this scale?  I don't think it will scale well, but it's simple to implement. 
Another way is to make this hierarchial by having a primary table and a bunch of secondary tables.  The secondary tables hold lets say zip codes for a county, and the primary table acts as the key to the secondary.  I think this would scale better as the tables can be distributed, but I may have minor redundancy because a user can be stored in several tables.  
Anyway, I would appreciate any thoughts, ideas, or alternative designs that could help me with this.  The question really comes down to, how should I design this and why? 
Update:
I have a separate table with user info.  I'm trying to design table(s) for the user's zip code preferences. 

A:

I'd advise a slight enhancement to your current approach. 
Use a database that supports the indexing of Geospatial data, e.g. PostgreSQL with Postgis.  Then, in addition to zip codes, store the coordinates of the zip code. 
Thus, when asking your plumber which zip codes he wants to serve, you'll be able to pull out the nearby zip codes.  Likewise, you'll be able to pull out plumbers in the nearby areas when users are querying your database.