Creo que no tienes ni idea que es una PRIMARY KEY, este, es una columna (s) que te permiten NO REPETIR los registros en tu tabla, ademas de que te sirven para realizar el constrain de liga vs otras tablas (DRI).
Nada que ver con la eficiencia o no de las busquedas.
Para declarar la PK debe tomarse en cuenta que las columnas que la conforman, no deberan sufrir modificacion alguna.
Lee este articulo de Carlos Sacristan:
http://www.helpdna.net/sqlserver_cla...tificiales.htm