Para las consultas que estas planteando el índice sobre el id no sirve absolutamente de nada. Es la PK y por definición tendrá un índice asociado pero para las consultas que planteas no sirven de nada ni el índice ni la PK auto incremental en si misma. Ni siquiera sirve para que no tengas apellidos repetidos, nada impediría ingresar Pérez con id=1 y seguidamente Pérez con id=2.
Antes de hacer todo ese preproceso, que te servirá en algunos casos y en otros no yo de ti leería un poco de teoría sobre índices y para empezar crearía un índice UNIQUE sobre apellido, con este ya te aseguraras que no haya repeticiones.
Con el índice sobre apellido la mayoría de casos en que supones que se va a recorrer toda la tabla ya no se hará.
También afirmas que con los campos calculados que estas proponiendo evitaras recorridos completos sobre la tabla, pues si esos campos no están a su vez indexados el recorrido se producirá igualmente.
Teoria general
http://es.wikipedia.org/wiki/%C3%8Dn...se_de_datos%29
Más concretamente en el caso de MySQL
http://dev.mysql.com/doc/refman/5.0/...l-indexes.html
Decidiendo por el motor, como forzar el uso de un indice
http://dev.mysql.com/doc/refman/5.1/en/index-hints.html
Funciones que te serviran para leer partes de un apellido
http://dev.mysql.com/doc/refman/5.0/...functions.html