Index for VARCHAR column has low efficiency
Would you try this and let me know if this improves your performance:

SELECT links.location_id FROM links 
WHERE NOT Exists( 
select location_id from locations);