eu am facut o chestie de genu pentru un site si functioneaza impecabil pe destul de multe inregistrari cu multe tipuri de interogari.

tabela useri : id, .....
tabela relatii : id, id_user,id_friend,status
(folosesc campul status pentru a marca o prietenie "confirmata" sau nu) initial cand iti "cer prietenia" se insereaza cu id_user=id-ul meu, id_friend=id_ul tau si status=0 iar tu poti accepta sau nu si de asemenea daca ma vrei si tu in lista ta de prieteni (gen YM) si atunci se face status=1 si se mai insereaza o inregistrare cu id-urile inversate.
Daca iti faci si indecsi pe o astfel de tabela o poti folosi pana la adanci batraneti.