Современные БД изначально спроектированы под работу с миллионами записей, они работают с ними достаточно хорошо.
Если ты планируешь выход на сотни миллионов записей - можешь думать о разделении сразу.
Тут лучше основную (самую нагруженную) таблицу разносить на различные сервера (например, пользователи от А до Ж на одном сервере, пользователи от З до Т на другом сервере, пользователи от У до Я на третьем сервере, если у тебя основной является таблица пользователей, если ты будешь там всех жителей Европы хранить.
С другой стороны, есть нагрузка по записи и по чтению.
С третьей стороны - если делать не только БД, а и сервера, обрабатывающие данные, то все еще круче будет.
Делать на одном сервере - смысла нет никакого, лишние заморочки.