La 2da opción, aunque depende de: cantidades de búsquedas^cantidad de paginas^(cuanto quieras afinar los resultados+relevancia+complejidad del parser+etc), sobre todo los etc que son siempre los complejos :P.
Mira, este un proyecto bastante avanzado, pero para que te des una idea de como indexa por ejemplo:
http://www.phpdig.net/