Non conta quanto è grosso, ma saperlo usare ( )
Cosa significa 120 milioni di record?
Una singola tabella?
Tante tabelle?
Relazionate tra di loro, oppure no?
E che campi usi (varchar? blob?)

E soprattutto: che tipo di interrogazioni vuoi fare?
E gli inserimenti come sono? (frequenti, infrequente, concorrenti, ogni tot)

Da quanto sto studiando il problema si pone quando gli indici diventano più grandi della memoria RAM del computer, perchè finiscono per essere letti "a pezzi".
Se invece ci stanno allora anche un database molto grande (con relazioni però del tipo che con EXPLAIN vedi usare gli indici) non pone particolari problemi