From a terminal window:
sudo mdutil -avE
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”.