Что происходит, когда в БД накапливается более 100+млн записей?

Стало интересно, а что происходит, когда в БД (MySQL) накапливается более 100+млн записей?

Это называется HighLoad и распределение нагрузки. Если брать саму суть вашего вопроса, то для сокращения времени обращения к данным (при очень большом их количестве) большие таблицы разделяются на несколько частей (шардов, сам процесс называется шардинг).

Далее реализуется логика обращения к этим шардам, т.к. держать ее в самом коде приложения не лучшее решение. Например, в VK это реализовано в виде сервисов. К нужному сервису пишется REST-запрос, сервис выполняет поиск данных по шардам и выдает результат в ответе.

Также имеет смысл использовать NoSQL-решения или распределенные базы данных (например, Cassandra от Facebook), но конкретная реализация сильно зависит от самих данных. Плюс не забываем про репликацию, бэкапы и отказоустойчивость.

Если же у вас всего один сервер и в него не влезает база, либо не справляется с нагрузкой, то:

1. Для начала вынесите БД на отдельный сервер с большим количеством оперативной памяти.
2. Если этого недостаточно, то имеет смысл отделить наиболее нагруженные таблицы и выносить их на отдельные сервера. Также можно попробовать разбить большие таблицы на несколько частей по типам данных (данные, которые запрашиваются редко и по ним не идет никакого поиска и сортировки - переносим в отдельные таблицы).
3. Снизить нагрузку на базу поможет кэширование данных. Используйте тот же Memcached. Даже один правильно настроенный кэшируюший сервер способен уменьшить нагрузку на базу в разы (конечно, при условии, что используется кэширование подходящих запросов, которые часто запрашиваются и не слишком быстро вымываются из кэша).
4. Шардинг для небольших проектов - это крайняя мера, обычно к ней прибегают, когда уже физически невозможно хранить или проводить операции над одной таблицей. Имейте ввиду, что это на порядок усложняет логику обращения к базе.