This will attract subjective answers but if you want to use cloud services, you can definitely store the actual photos/videos on the cloud itself. And as you mentioned just store the link the database
The word you might want to research is CDN, Amazon has one service called Amazon S3
Edit, quick Google showed that Instagram is using Amazon S3. You can read here
2
solved Creating Application To Hold Photos and Videos [closed]