Ogromna baza danych Facebooka
PYTANIE: Zakładam, że każda osoba na Facebooku jest reprezentowana jako węzeł (wykresu) na Facebooku, a związek / przyjaźń między każdą osobą (węzłem) jest reprezentowany jako krawędź między zaangażowanymi węzłami. Biorąc pod uwagę, że na Facebooku są miliony ludzi, w jaki sposób jest przechowywany Wykres?
ODPOWIEDŹ: Dziwne, jak się wydaje, wykresy i bazy danych wykresów są zazwyczaj implementowane jako listy połączone. Jak wspomniano tutaj, nawet najpopularniejsza baza danych grafów (neo4j), potajemnie używa czegoś podobnego do podwójnie powiązanej listy. Reprezentowanie wykresu w ten sposób ma wiele znaczących zalet, ale ma także kilka wad. Po pierwsze, przedstawienie wykresu w ten sposób oznacza, że możesz wstawiać krawędzie w niemal stałym czasie. Po drugie, oznacza to, że przemierzanie wykresu może nastąpić niezwykle szybko, jeśli chcemy tylko zwiększyć lub zmniejszyć listę połączoną. Największa wada tego wynika jednak z czegoś, co czasami nazywa się efektem Justina Biebera, w którym węzły z dużą liczbą połączeń są bardzo powolne w ocenie. Wyobraź sobie, że musisz przemierzać milion pół redundantnych linków za każdym razem, gdy ktoś jest powiązany z Justinem Bieberem. Wiem, że wspaniali ludzie z Neo4j pracują nad drugim problemem, ale nie jestem pewien, jak sobie z tym poradzą ani jaki sukces odnieśli.
Trochę pracując z danymi na Facebooku (zebranymi od użytkowników Facebooka), zapisaliśmy je jako parę wartości: USER_ID, FRIEND_USER_ID. Ale myślę, że twoje pytania są nieco głębsze? Możesz przechowywać go na różne sposoby, w zależności od pytania badawczego. Jedną interesującą opcją są na przykład triady