Quale struttura di dati scegliere per il sito web del social network?

Il mio primo istinto qui è che la lista di amici è una struttura di dati che si legge spesso e si scrive raramente, specialmente per utenti consolidati con grandi liste di amici. È anche abbastanza comune per il server tenere molte liste di amici in memoria simultaneamente per scopi di analisi e grafici ("trova tutti gli amici degli amici"), quindi la compattezza è importante.

Assegnerei ad ogni utente/entità un ID intero globalmente unico (potresti cavartela con 32 bit, ma 64 bit è probabilmente a prova di futuro), e implementerei la lista di amici come un array ordinato di interi a 64 bit. Se n=il numero di amici dell'utente, allora la ricerca è O(log-n), l'inserimento e la rimozione è O(n), e il comportamento della cache è eccellente.

Questa struttura è molto semplice da scrivere, usare e fare il debug. I lookup sono probabilmente molto più veloci di un albero binario a causa della localizzazione nella cache. Aggiungere e rimuovere amici sarà probabilmente più lento una volta che la lista di amici raggiunge una certa dimensione, ma il mio sospetto è che la velocità complessiva del sistema sarà effettivamente più veloce, specialmente se c'è un limite ragionevole al numero di amici.

Se aggiungere e rimuovere amici diventa il collo di bottiglia, è possibile passare ad un albero rosso-nero in futuro; assicuratevi di astrarre l'interfaccia in modo appropriato in modo che tale passaggio sia facile da fare.