Address Book Search - Which Data structure i should use when large data

I want to design Address book with following fields

UID Name PhoneNumber1 PhoneNumber2

UID is to identify the name uniquely. Lets say i want to save 2 million records. Now i want to structure how to save this records, so that it can be searchable by both Name and phoneNumber.

Which data structure and search technique i should go with.

Thanks in advance