Второй вариант с реляционной структурой вполне жизнеспособен. Хорошо индексированная таблица будет работать без проблем и на больших объемах. Вы можете и заранее это проверить, создав структуру и наполнив её большим количеством тестовых данных.
Насчет NoSQL решайте сами, материалов полно, например,
вот и
вот.