Hola @jorge98,
asumiendo que el "revisado" de tu tabla sea una marca para indicar que el usuario leyó la notificación, entonces sí te hace falta un registro por cada notificación enviada.
Podría reducirse el almacenamiento almacenando la notificación en sí por un lado y la notificación por otro, pero tendrías el mismo millón de notificaciones de manera más eficiente.
Llegados a este punto, la conclusión sería que para un sistema tan grande (si 1 usuario puede tener 1 millón de segidores, salvo que todos sigan solo a uno, debería esperarse que en total haya varios millones de usuarior) una base de datos relacional no es la mejor elección, sino que habría que pensar en otro tipo de almacenamiento distribuido, como MongoDB, CouchDB, Casandra o alguna otra NoSQL.
Una RDBMS actual y potente como PostgreSQL se maneja bien con tablas de algunos millones de registros (si están bien diseñadas), pero un sistema tan intensivo de usuarios y notificaciones la sobrepasaría en el corto plazo.
Saludos cordiales!
PD: la estructura de la tabla que ponés "huele raro"... pareciera que hay campos que describen campos para hacer querys, y eso sería un error de diseño del almacenamiento.