How do I create a table best suited for storing address information I have to create an address table in Oracle. Table is expected to hold millions of row. I created a table looking like this

 Table Address
    ID | Address Line1 | Address Line2 | Address Line3| City | Zip | ..|


The queries that I expect from my client may contain AddressLine1 and Zip or AddressLine1, Zip and City in which case the above table structure would not the most ideal. I don't want to have to scan the entire table for every query. I know for sure that the client queries will at least contain zip or city, am thinking that I have to create and indices on Zip and City. Should I consider anything else in my design?

I considered partitioning the table, but am going to start with a blank database and rows get added over a period of time, am not sure if I can dynamically create those partitions based on City or zip. 

Also my expectations is that the database has to be optimized for reads more than writes

Any ideas?
I would analyze the data and seriously consider scalability.

-Do you need to retain an old address for prior billing?
-Do you need to know when a client changed addresses?
-Are other countries currently involved now?
-Will other countries be involved?

3 address lines may not be enough.

You will likely need a total of:

-5 address lines
-City
-State
-Zip
-country
-Province ?
-CreateDate
-Expiredate
-Region  (I would consider this a way to group Zip codes 90000 series is Southern California, etc).  You could adjust later as needed.
-AcctType (billing, sales mailings, main office)