How does Facebook maintain a list of friends for each user? Does it maintain a separate table for each user?

I do not work for Facebook, however I can tell you that it’s rare that you would maintain a table per [anything], as that’s pretty much the opposite of using a database properly.

For the purposes of answering this question, I opened up MySQL Workbench and have modeled out a very basic set of tables to help you visualize how you might maintain this information.

First, you need a table that represents a person. For the purposes of this example, we’ll keep it simple: First Name and Last Name. We also need a unique identifier that we’ll let the database autocreate. At this point we have a pretty basic table structure:

There are a lot of things (or attributes) that make up a person, and we really do want to capture that information. For example, it’s pretty helpful to know what their Gender is. However, since we don’t want to allow them to type in just any old gender, what we really should do is create a table that has a list of all acceptable genders. You might think this is as simple as Male/Female, but it’s not. Facebook understands this and recently expanded their gender list to quite a few options. Anyway, at this point we now have two tables: one with a list of people, and one with a list of genders:

 

This doesn’t help us though, because we still have no way of knowing what gender John and Mary are. So now we need to define a relationship between the tables. In this case, a person can only have at most one gender, but there can be many people of the same gender. This means we need a 1:m* or One to Many relationship, which may look like this:

*the symbols where the lines connect to the tables are known as „Crows Feet” notation. In this case, we’re showing on the left that a person may have „1 or no gender”, and on the right we’re showing that a gender may have „1 or many persons”.

Once we establish this relationship and add the genderId column to the person table, all we have to do is save the correct genderId and then we know what gender each person is:

But that doesn’t really answer the question about how we establish friendships, does it? Well, let’s get into that.

First, we know that a person can have many friends, and that many of those friends may be friends with each other. We also might want to keep track of when they became friends, right? Although it might initially make sense to have a table where we store all of Mary’s friends, what we really need is a way to store ALL friendships in a single table. In this case, a Many to Many relationship is what we’re looking for. That might look like this:

This looks like of strange, but what we’ve done is created a „friendship” table that stores the following: A reference to a person, a reference to another person, and a date. So by populating a single row, we can establish a friendship between John and Mary:

Let’s populate a few more people into our social network and establish a few more friendships:

 

Finally, we have a structure we can use if we want to determine who is friends with who.

So for example, if I’d like to know who John Smith is friends with, I’d do something like this:

What if I want Mary’s friends list? I do this instead:

What if I want to know what friends John and Mary have in common? I can do something like this:

*Note: I have not made any effort to optimize these queries – there are most likely several better ways to try and do a MySQL INTERSECT.

What about John and Richard?

What about Mary and Richard?

What about John and Kari?

John and Kari have no friends in common.

You can also gather or filter by some additional information by joining in other tables…for example, let’s add in the Gender of all the friends that Mary and Richard have in common:

As I hinted a few screenshots ago, this is not optimized, but hopefully it gives you an idea as to how a single table can store a relationship between two people, and even store metadata about it (such as when it was established and perhaps even the type of relationship it is).