From a terminal window:
sudo mdutil -avE
That is, sudo (because you have to have admin rights to run this), mdutil (the program that does the work for you) -a for “work on all volumes”, -v for “be verbose in telling me what you’re doing”, and -E for “erase the data store and rebuild it”.