How Neo4j Works: the Property Graph, Nodes, Relationships and Index-Free Traversal

← Back to the section

Neo4j stores data as a graph: a set of objects and the connections between them. This is not a metaphor or a way to draw a diagram — it is literally how the data sits and how queries walk over it.

The property graph: four building blocks

Neo4j's model is called a property graph and consists of four elements:

• Node — an entity: a person, a product, an account, a document. The equivalent of a table row, but without a fixed schema.
• Relationship — a connection between two nodes: FRIENDS_WITH, BOUGHT, TRANSFERRED. It has exactly one type and a direction — from one node to another.
• Properties — key-value pairs on nodes and on relationships: a person has name and age, a "works at" relationship has position and since. In a relational database, data on a connection would need a table of its own.
• Labels — tags on nodes: :Person, :Company. A node may carry several labels; a label tells Neo4j where to look, and an index is attached to it.

Labels belong to nodes only, a type belongs to a relationship only. The schema is not rigid either: a new kind of connection is relationships with a new type, with no migrations and no reshaping of tables. That is the model's main strength — it is easy to evolve.

Index-free adjacency: why traversal is cheap

The key difference from a relational database is how connections are stored. In SQL, to go from an order to its items, the database takes order_id, goes into the index of the items table and searches there for matching rows. An index lookup is fast, but not free, and it repeats at every step of the chain.

In Neo4j a connection is a direct reference: the node record holds references to its relationships, and the relationship record holds references to the nodes at its ends. To reach the neighbours the database searches no index, it follows a reference, like a pointer in a data structure. That is index-free adjacency: the cost of a traversal equals the number of relationships walked, not the size of the database. The friends of someone's friends are found equally fast in a graph of a thousand nodes and in one of a billion — as long as that person does not have many neighbours.

The same count in plain Java — adjacency lists against a sorted table of connections:

live example

import java.util.*;

public class FriendsOfFriends {
    static int hops, compares;

    static List<String> byLink(Map<String, List<String>> graph, String who) {
        List<String> next = graph.getOrDefault(who, List.of());
        hops += next.size();
        return next;
    }

    static List<String> byIndex(List<String[]> rows, String who) {
        int lo = 0, hi = rows.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            compares++;
            if (rows.get(mid)[0].compareTo(who) < 0) lo = mid + 1; else hi = mid - 1;
        }
        List<String> next = new ArrayList<>();
        while (lo < rows.size() && rows.get(lo)[0].equals(who)) next.add(rows.get(lo++)[1]);
        return next;
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = Map.of("Ivan", List.of("Peter", "Anna"),
                "Peter", List.of("Olga", "Leo"), "Anna", List.of("Dan"));
        List<String[]> rows = new ArrayList<>();
        graph.forEach((a, bs) -> bs.forEach(b -> rows.add(new String[]{a, b})));
        for (int i = 0; i < 100_000; i++) rows.add(new String[]{"user" + i, "x"});
        rows.sort(Comparator.comparing((String[] r) -> r[0]));

        Set<String> links = new LinkedHashSet<>(), index = new LinkedHashSet<>();
        for (String f : byLink(graph, "Ivan")) links.addAll(byLink(graph, f));
        for (String f : byIndex(rows, "Ivan")) index.addAll(byIndex(rows, f));

        System.out.println("by reference: " + links + ", hops " + hops);
        System.out.println("by index: " + index + ", comparisons " + compares
                + " over " + rows.size() + " rows");
    }
}

The answer matches, the work does not: five pointer hops against three index lookups that take 49 comparisons between them — and the longer the table, the more.

How this differs from the relational model

Let us compare on a single question: "is there a path from account A to account B through a chain of transfers of unknown length".

• In SQL this is a recursive query (WITH RECURSIVE) over the transfers table: a JOIN by index at every step, and the number of steps is not expressed in the shape of the query.
• In Neo4j it is one pattern with a variable-length path (-[:TRANSFERRED*]->): the database follows references from account A until it reaches B or runs out of relationships.

A graph is not always better. For "select the orders of this month above N" a relational database is faster and simpler — there is no traversal there, only a filter over values. Neo4j wins where the question is about connections and their depth, not about a filter over fields.

Where this is used

The property graph fits data where connections are of many kinds and have a life of their own: social networks, recommendations (users and products), fraud detection (accounts and transfers), knowledge graphs. The common sign is one — there are more many-to-many connections than entities, and queries follow a chain.

The mistakes made most often in a model:

• Confusing a node with a property. If connections are searched by a value ("everyone in this city"), it is a :City node, not a string property city on every person. A property is read together with the node, a node connects.
• Forgetting the direction. A connection always has one; a query may walk it both ways, but while modelling it is chosen deliberately: BOUGHT goes from person to product.
• Expecting a graph to speed up everything. Filters and aggregates get no faster — a relational database is quicker there.

In short

• A property graph is nodes with labels, relationships with a type and a direction, and properties on both.
• A node may carry several labels, a relationship has exactly one type; a new kind of connection needs no migration.
• Index-free adjacency: references to relationships live in the node record, so a step to a neighbour is following a reference, not an index lookup.
• The cost of a traversal equals the number of relationships walked; in SQL every step grows more expensive along with the table.
• An index is there to find the starting node of a traversal, not to walk a connection.
• A graph wins on connections and their depth, a relational database on filters and aggregates.

What to read next

• Cypher: a Graph Query Language in Plain Words — relationship patterns and variable-length paths.
• Neo4j graph modeling: indexes, supernodes and operations — what to make a node, what a property, and where an index is needed.
• Graph data in plain words: recursive SQL or a graph database — when WITH RECURSIVE is enough.
• Graphs: vertices, edges, DFS and BFS — adjacency lists and traversals on ordinary collections.