Indexes are the way to go because it only searches through 4 levels instead of the entire table. You want to add indexes to fields like phone numbers. You don't want to index a city unless there a a good number of cities ie. if everyone was from New York it would be pointless.
If I'm not mistaken, SQL Server will update the indexes automatically when records change.