The first thing to consider is that a graph cannot be mapped in a maximally consistent way with the underlying hardware (the von Neumann architecture represents

The first thing to consider is that a graph cannot be mapped in a maximally consistent way with the underlying hardware (the von Neumann architecture represents data in a sequential manner and it is much faster to access it this way rather than randomly). With that out of the way, there are generally two families in the graph database world: those which use underlying traditional tables of nodes and many-to-many edges; and index-free adjacency which just means each node in the graph knows the memory address of its connections (other side of the edges). Distributed graphs necessarily end up using the former because it’s difficult if not impossible for a node to know the memory address of its connection when that crosses a physical boundary. So typically index-free adjacency graphs have a master-slave setup with multiple read replicas but a single one to write to. So with a “native graph” you don’t rely on potentially expensive join operations to find neighbors of neighbors and can traverse complex paths easily. Here’s how Facebook approached the task of scaling a graph representation to mind boggling heights (spoiler: lots of mysql servers and a plethora of caches) https://engineering.fb.com/2013/06/25/core-data/tao-the-power-of-the-graph/ https://engineering.fb.com/2013/06/25/core-data/tao-the-powe...