Qual a estrutura de dados a escolher para o site da rede social?

O meu primeiro instinto aqui é que a lista de amigos é uma estrutura de dados de leitura-frequente, raramente escrita, especialmente para usuários estabelecidos com grandes listas de amigos. É também bastante comum que o servidor tenha muitas listas de amigos na memória simultaneamente para fins de análise e gráficos ("find all friends-of-friends"), portanto a compactação é importante.

Daria a cada usuário/entidade um ID inteiro globalmente único (você poderia escapar com 32 bits, mas 64 bits é provavelmente à prova de futuro), e implementaria a lista de amigos como um array ordenado de 64 bits inteiros. Se n=o usuário's friend count, então lookup é O(log-n), inserção e remoção é O(n), e o comportamento do cache é excelente.

Esta estrutura é muito simples de escrever, usar, e depurar. Os lookups são provavelmente muito mais rápidos do que uma árvore binária seria devido à localização do cache. Adicionar e remover amigos será provavelmente mais lento quando a lista de amigos atingir um certo tamanho, mas minha suspeita é de que a velocidade geral do sistema será realmente mais rápida, especialmente se houver um limite razoável no número de amigos.

Se adicionar e remover amigos se tornar o gargalo de gargalo, você pode mudar para uma árvore preto-avermelhada no futuro; certifique-se de abstrair a interface corretamente para que tal mudança seja fácil de fazer.