Зачем Вам искать по ссылкам? Может стоит из ссылки выделить ту информацию, по которой будет происходить поиск, и хранить в отдельном поле с индексом по этому полю?
Первое что надо сделать для такого объема — это порезать таблицу по какому-либо признаку, потому что 500К записей в день — это много. Помнится была таблица с 4 млрд. записями, то всякие операции с этой таблицей были очень тормозные
Второе, вы не объяснили что именно за данные содержаться в поле DATA. Может сделать fulltext (укажите show create table). Если данные достаточно большие, то как указали в первом ответе, то сфинкс
My<cod/>.net
