To answer your question, you wont have to re-index when you insert a row, the index will maintain that itself.
I could be wrong, but since you do not compare your if statement to a condition, your if will return true whether it finds a row or not.
To up your performance you could do a couple of things. Having million of rows is what mysql was designed for, so if it's lagging there is something wrong.
I dont konw enought about your database or program to figure out what, but something I could suggest is set link to a primary unique key if it has to be unique in the table, That way you dont have to reduntantly chekc and then insert a link, just tyr to insert the link and it will return error on match, saving you 1 query, but in your 2 query process that makes your program x2 as fast already.