Would I use an EXPLAIN statement or INDEX?
EXPLAIN is used to obtain a query execution plan (that is, an explanation of how MySQL would execute a query)
INDEX is used to find rows with specific column values quickly. Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows.
Now from this pull your own conclusion!
If your search is using as it's predicate the column postal code
then and index should be created on this column in order to improve performance. Other wise with no index for it to use a full table scan will be used.