Хешированный индекс. Если вы используете числовой уникальный идентификатор пользователя, вы можете предполагать несколько коллизий (если они настроены правильно), и хеш-индексы - ваш лучший выбор.
http://en.wikipedia.org/wiki/Hash_table
И да, они используют базы данных. Обычно несколько серверов с балансировкой нагрузки. Посмотрите этот вопрос для идей по балансировке нагрузки для сервера SQL, так как существует несколько подходов:
https://stackoverflow.com/questions/761502/sql-server-load-balancing
Один из популярных способов балансировки нагрузки называется Microsoft «объединение», но он в значительной степени распространяет запрос и позволяет обслуживать его нескольким серверам (afaik).