How To Design Database To Search Faster From 1 Million Customer's

I intend to develop a web based application, which uses SQL server 2005 at back end and Visual studio 2.0 as front end.

Application serves two functionalities



Requirement1: It carryout a search (In SQL server) for a particular name entered from front end .net application against a huge DataBase of size about 1 million records.



Scenario: The above requirement can be complemented by following example

Consider we have a bank database which has its existing customer DataBase having containing attributes like Name, Age, and Profession e.t.c.

Now if some new customer want to open a new account in bank, then bank officials want to know whether the

new customer is one of the existing customer or not(without asking to customer itself).

System should be able to detect the combination of name also i.e if we enter "Jhon" from front end .net interface

then application should be able generate all list of all customer having "Jhon" as part of their name at any location(firstname, middlename, lastname).



Requirement 2: If some time change is detected in bank's extisting customer's DataBase then each record of this DataBase is searched against a external dataBase(having almost 2 -3 million records).

Scenario: The above requirement can be complemented by following example

If new user is added to bank's existing customer database(database change) then this new updated database's every record is serarched against another bank's database.



I would like to hear experts voice for database design of such application for optimal performance,and types of searches I should look for application.