I would have one column in the database for each field that the user might start entering. So, if someone is going to start by typing in a ZIP, have an indexed column with just ZIPs in it.
Then when someone is typing in the street address, you'll do queries like "SELECT * FROM addresses WHERE ZIP='50443' AND address LIKE '123 mai%' LIMIT 10", returning the matching rows results quickly to the web interface.
If you get the data separated with columns for number, street, city... then your queries will have some "OR" clauses in them.
And mind the inevitability of differences between "st", "st.", "street"... and spelling variations like "St. Mary Blvd N" and "Saint Mary Boulevard North". The canonical address you return in the autocompletion response will depend entirely on how the data is formatted.
good indexing and optimizing your queries is crucial for a fast response. You do not want any queries that require a scan of the entire table.
If you're using a pre-built autocompletion gadget, look to see how it triggers those AJAX requests. You do NOT want an AJAX request on every keyup event. The gadget should at least use some kind of throttling, but the best ones use a method called "debouncing" -- read about it here:
If the input field is a "mixed" text entry field, ie people would type "123 main street 50324 anytown KY" then you've got quite a challenge. Autocomplete may not be appropriate - or feasible - for that kind of input.
btw, I have no idea where you'd get the data. ZIP databases are easy to find, but I've never sought one with granular street addresses. Maybe the US government has something in the public domain.