Si quieres que guarde todos los videos que ha visto un usuario, a mi parecer sería más correcto usar la base de datos.
Ahora bien, ¿quieres que el historial de videos dure siempre?
Sí es así, puedes crear una tabla donde guarde los videos que ha visto el usuario. Cada vez que el usuario vea un video se guarda de nuevo en esa tabla.
Pero... creo que será más recomendable que el historial tenga una fecha de caducidad.
Puedes coger, crear una tabla para ir insertando los videos que ve el usuario y seguir dos caminos:
1 - Cuando el usuario cierre sesión eliminar los videos que ha visto el usuario
2 - Al pasar X tiempo, hacer que los videos más antiguos del usuario se eliminen.
Lo de tener muchos usuarios no es problema y lo de realizar muchas consultas depende de como construyas las tablas. Debes de hacerlas lo mas optimizadas posibles. Pero vamos, que MySQL es muy potente así que con crear tablas en condiciones no debes de preocuparte
Saludos,
PD: Estoy hablando de guardar las direcciones de los videos en la base de datos, no los videos en sí. De ser así ni se te ocurra! xD