Trouver des lignes dans A qui n'ont pas de ligne associée dans B, où le FK est sur B ?

Vous recherchez NOT EXISTS :

SELECT 
  * 
FROM 
  a
WHERE
  NOT EXISTS (SELECT 1 FROM b WHERE a_id = a.id)

Avoir un index sur b.a_id améliore les performances de cette requête.