Gracias a todos muchachos, y gracias RONPABLO por el link al otro post, muy ilustrativo. Por lo que leí no le afecta a la búsqueda que el campo llave sea alfanumerico y grande. Para el campo llave he decidido concatenar algunas cadenas de la siguiente manera:
- Primeras dos letras del nombre.
- Primeras dos letras del apellido paterno
- Primeras dos letras del apellido materno. Si no tiene apellido materno (aquí en México hay casos) se ponen dos "x" en su lugar.
- Fecha de nacimiento con formato ddmmyyyy
- Una letra del alfabeto empezando por la letra "A" (caracter extra para evitar duplicados). Si esta combinación ya existe el caracter extra se va incrementando de acuerdo al alfabeto.
De esta forma el campo llave quedaría como una cadena alfanumerica de 15 caracteres.