io farei un vettore con tutte le lettere dell'alfabeto e poi un ciclo (for, foreach,while quello che ti è più congeniale) su ognuno di esse facendo un query sul db del tipo:
codice:
....
where nome_record LIKE '%$LETTERA_CORRENTE%'
ORDER BY nome_record asc
...
ogni volta poi stampi

Lettera $LETTERA_CORRENTE
record1, record2, etc