How To implement Facebook friends module in Database?

I am developing a facebook type application for my institute.

and I am stuck at the friends module. i.e. How to know if the particular users are one's friends.

开发者_StackOverflow中文版I googled a lot but didn't get any satisfactory answers. What I got is : there will be many friends of a person and implementing users and their friends in seperate table will only increase redundancy and large DB size.

I thought of using a graph with vertices as users and edges as connection .

But how to implement something like that in db.

Or How Facebook handles such huge amount of relationships?

Personally, I would have a dedicated table for it:

You could have a table with just two columns: userID and friendID

Since the relationships between users in the db will be many-to-many, normalizing it requires a link table which breaks it into many-to-one-to-many

http://dev.mysql.com/tech-resources/articles/intro-to-normalization.html#03

This kind of problems are usually solved by using a different type of database. For a social network, a graph database should make sense, as nodes and relationships are first class citizens in it. There's a social network example for the Neo4j graph database, the full source code of the example is included in the standard dowload package. I've also written a blog post on this theme, with another example as starting point.