Encuentre filas en A que no tengan una fila asociada en B, ¿dónde está el FK en B?

Estás buscando NOT EXISTS :

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

Tener un índice en b.a_id ayuda al rendimiento de esta consulta.