How graph databases work: Neo4j and Kùzu

Intro

0:00 Hello and welcome to this series, where we're going to build a graph database from scratch in C++, a small one that you can read, run and understand from one end to the other. Let's begin with a quick look at the kind of graph we're going to be working with.

0:14 This is a small knowledge graph about animals, drawn by Neo4j: what each animal is, where it lives, and what it eats. And a query can walk it, such as two hops down the food chain from the red fox, to the clover and the wheat that its prey eat.

0:30 By the end of this episode, we're going to have run that query in two graph databases, and in a throwaway graph of our own, written in C++. And over the series, we're going to build a graph database of our own, which answers questions like these and grows towards a knowledge graph. We're going to draw its graphs too, in a small browser UI made with D3, the JavaScript library for drawing data on the web. My name is Adrian, and this first episode is a little different from the ones that will follow, as most of it is about figuring out what smollerGraph should be. I'd like to do some of that figuring out together with you. So today, we're going to look at what a graph database is, and at two of them that I have a lot of respect for, Neo4j and Kùzu. A quick note on how the series is made: often, the voice you're hearing is generated with AI, and it's designed to sound like me.

1:22 On the website of the series, you can find more information about the project. The code is going to be open source on GitHub, tagged at each step of each episode, so that you can follow along, and each episode gets a page here as it comes out.

Why graphs

1:36 As for why a graph database, graphs are at the core of many of the problems we solve through engineering. Knowledge graphs help search engines and AI models find facts, and how those facts relate. In healthcare, a graph can link patients, conditions, treatments and the research behind them. Routing on a map is a search through a graph of roads and junctions, and a file system is a tree of folders and files, with links across it. A distributed system is a graph of services and the calls between them. In an enterprise, batch processing and ETL loads are graphs too, as each job depends on the ones that feed it, so schedulers such as Airflow run them as a directed acyclic graph. A game engine keeps track of its entities and how they relate, such as which object belongs to which parent. And in cybersecurity, graphs show how an attacker could move from one account or machine to the next. So once you understand how a graph is stored and searched, it comes into play in a lot of places.

2:37 A well-known example is BloodHound, from SpecterOps, which maps an organisation's Active Directory and Azure environments as a graph of users, groups, computers and the permissions between them. It uses graph theory to find attack paths, the chains of permissions an attacker could follow to reach something valuable, so that defenders can find and close them first. And its graph lives in Neo4j, next to a Postgres database for the rest of the application.

Towards a knowledge graph

3:02 Where I'd like smollerGraph to head is a knowledge graph, a knowledge base that keeps facts as a graph, with things as nodes and how they relate as relationships. Google introduced its Knowledge Graph in 2012, building on DBpedia and Freebase, and it's what fills the panel of facts next to a search result. And with large language models, knowledge graphs have come back as a way to structure what's in text, so that a model can retrieve facts and reason over them.

3:29 A knowledge graph is also where smollerGraph meets mvGPT, the other series on this channel, where we're building a small GPT from scratch in PyTorch. We take it through the whole training pipeline, from pretraining to reinforcement learning, and for now, it writes short stories. At some point, we're going to bring the two together, with mvGPT asking smollerGraph for facts, so that what it writes can rest on a knowledge graph, and not just on what it picked up in training.

What a graph database is

3:55 A graph database stores data as nodes, and the relationships between them. Here, the red fox is a node, with the label Animal and a property, its name. It eats rabbits, and that relationship is stored as data in its own right, with a type, EATS, a direction, and properties of its own, such as where the fact came from. The rabbit eats clover, which is a node with another label, Plant. Both animals are mammals, and the rabbit lives in the meadow, which is a habitat. This is called the property graph model, and it's what Neo4j and Kùzu are both built around.

4:32 You could keep all of this in MySQL, like the accounts in nanoMMO, with a table of animals and a table of what eats what. Then what the fox's prey eat is a join of the eats table with a second copy of that table, and each hop further is one more join, which looks the next animals up through an index. A graph database turns this around, as it keeps with each node where its relationships are. So a hop is following a stored reference from one record to the next, and queries that walk many hops, such as a food chain, a route on a map or an attack path, are what it's built for.

Cypher

5:08 Both databases speak Cypher, a query language that Neo4j created, which draws the pattern you're looking for in ASCII art. A node goes in round brackets, like a circle, with a variable and a label, here a, for an Animal. A relationship is an arrow between two nodes, with its type in square brackets, which here is LIVES_IN. And the node it points to has a property to match, the name Meadow. The database fills in a with each animal that matches the pattern, and RETURN says what we want back, which here is their names. Cypher has since been opened up as openCypher, and much of it went into GQL, the ISO standard for graph query languages, which was published in 2024.

Neo4j

5:51 Neo4j is the best known graph database, and it's been around since the late two thousands, from a company that started in Sweden. It's written in Java, and it runs as a server: applications connect to it over the network, through Bolt, its own binary protocol, or over HTTP. Its Community Edition is open source, and there's an Enterprise Edition and a cloud service, Aura, on top of it.

6:15 Inside, Neo4j has long kept the graph in store files of fixed-size records, with a file for nodes, one for relationships and one for properties. As the records in a file are all one size, a node's id tells Neo4j where its record is, without an index. A node's record holds the id of its first relationship, and each relationship's record links to the next and the previous relationships of both of its nodes, so a node's relationships form a chain. Properties hang off the node in a chain of their own. Neo4j calls this index-free adjacency: walking from the fox to what it eats follows these ids from record to record.

6:55 Now, let's load that graph into Neo4j and run some queries on it. Neo4j comes as a Docker image, so we start a container of Neo4j five point two six, a long-term support release, and talk to it with cypher-shell, its command-line client. Our knowledge graph is a single CREATE statement in a file: ten nodes, for the animals, plants, classes and habitats, and the relationships between them. We load it with cypher-shell, which runs the file against the database. Then we ask what the red fox eats, which gives us the rabbit and the field mouse. With star two on the relationship, the pattern walks two hops of EATS, down the food chain, and we get the clover and the wheat that its prey eat.

Kùzu

7:36 Kùzu comes from the other end of the field. It started as a research project in Semih Salihoğlu's group at the University of Waterloo, and it's written in C++. It's an embedded database: there's no server, and it runs inside your program as a library, the way SQLite and DuckDB do. It keeps its data in columns, with its adjacency lists in compressed sparse row form, and its query processor works on batches of values at a time. Then, in October 2025, its authors archived the repository. Its releases still install and run, and all of its code is there to read, which makes it a good reference for a series like this one.

8:14 In compressed sparse row form, the relationships of a type are sorted by the node they start from, and the neighbours sit one after another in an array. A second array holds, for each node, where its neighbours start, so what the fox eats is the slice from its offset up to the rabbit's, the first two neighbours. Reading a node's neighbours reads values that sit next to each other, which is what disks and CPU caches are fastest at. And each property is a column of its own, so a query reads the properties it needs and skips the rest.

8:46 Kùzu's Python package carries the whole database, so this script is all we need. Opening a database is creating an object pointed at a folder on disk, with a connection to it, and there's no server anywhere. Kùzu wants a schema first: a node table for species, with the name as its primary key, and a relationship table for EATS, from a species to a species. Then we add five species and four relationships of what eats what, and ask for two hops down the food chain from the red fox. We run it with uv, which installs the package on the fly, and we get the wheat and the clover again, from a database that lives in a folder next to our script.

Side by side

9:24 So, to put the two side by side. Neo4j is a server that applications connect to, while Kùzu is a library that runs inside the application. Neo4j is written in Java, and Kùzu in C++. Neo4j lets you add labels and properties as you go, and Kùzu asks for its tables up front, which it uses to lay out its columns. Neo4j follows references from record to record, and Kùzu reads neighbours and properties as runs of values. They're two quite different answers to how a graph should live on disk, and both of them speak Cypher.

Where to go deeper

10:00 If you'd like to go deeper on how databases work inside, Andy Pavlo and the CMU Database Group put their database courses from Carnegie Mellon on YouTube, lecture by lecture. They go from how data is laid out on disk, through indexes and query plans, to transactions and recovery, and I'd recommend them alongside this series.

10:20 There are also two books I'd recommend, if you prefer reading. Database Internals, by Alex Petrov, goes through how storage engines and distributed databases work, from B-trees to consensus. And Graph Databases, by Ian Robinson, Jim Webber and Emil Eifrem, from Neo4j, covers modelling your data as a graph, and has a chapter on how Neo4j works inside.

What smollerGraph could be

10:42 Now, what should smollerGraph be, with these two in mind? It's going to be written in C++, which is what Kùzu is written in, and what we used for nanoMMO. My instinct right now is an embedded database, like Kùzu, so it's a library you can open from a test, with nothing to start first. For storage, I'm leaning towards records that point at each other, like Neo4j's, as it's the simplest way to see what a hop costs, and maybe columns later, to measure the difference. It should speak a small subset of Cypher, enough for the queries we care about, and at some point it needs transactions and a log, so a crash doesn't lose what was written. And we're going to measure it along the way, running the queries we run on Neo4j and Kùzu. Most of this isn't settled yet, so if you have opinions, I'd love to read them in the comments.

The plan

11:33 So, here's a rough plan, which is going to change as we go. We start from pages on disk, as a database reads and writes in fixed-size blocks, then keep nodes and relationships in them, and follow relationships from one node to the next. Then a parser for our subset of Cypher, and a planner that turns a pattern into steps. Indexes come next, for finding where a query should start, then transactions and a log, so that a crash part way through a write leaves the database as it was. Along the way, we benchmark it against Neo4j and Kùzu, on LDBC's Social Network Benchmark, at a scale that fits on a laptop. We give it a browser UI, which draws query results as a graph with D3, the way Neo4j Browser does. Then we grow it into a knowledge graph, which mvGPT can ask for facts. We're going to start from the bottom, with the pages.

A throwaway graph in C++

12:24 Before we get to pages and disks, I'd like us to write a first graph of our own, a throwaway one that keeps everything in memory, and answers the food chain question we asked Neo4j and Kùzu. We start from an empty repository, and to build it, we're going to use CMake, the build system most C++ projects use. CMake doesn't compile anything on its own, as it generates the build files for a tool such as Ninja, which is what lets one project build on a Mac, on Linux or on Windows. The top-level CMakeLists file opens with cmake minimum required, at version three point two eight, so someone with an older CMake gets a clear error right away. Then the project, smollergraph, at version zero point one, in C++, which CMake writes as C X X, so that it doesn't go looking for a C compiler we don't need. We want the C++20 standard, which gives us designated initialisers and string functions such as starts with, and we mark it as required. That way, a compiler that can't do C++20 stops with an error, instead of quietly falling back to an older standard. We turn the compiler extensions off, so the code sticks to standard C++ and builds with any compiler. Export compile commands writes a file listing how each source file is compiled, which editors read to understand our code. And we switch on the warnings from day one, with all, extra and pedantic, because they get more expensive to fix the longer we wait. Last, add executable declares our program, sg, short for smollerGraph, built from main dot c c in the src folder. The code follows Google's C++ style guide, which ends source files in dot c c and headers in dot h. In main, we include iostream, the standard library's header for input and output streams, as we want to print to the terminal. The main function prints a line saying what the program is, and returns zero, which tells whoever started it that it ran fine. A clang-format file says how our code is laid out, and we base it on Google's style, so nobody has to format anything by hand. An MIT licence, as it's all open source, and git ignores the build folder, so nothing CMake generates ends up in the repository.

14:35 Let's configure the project, which is when CMake writes those build files for us. Dash S says where the source is, and dash B where the build folder goes, so everything it generates stays out of the source tree. Dash G picks the generator, Ninja, a small and fast build tool that came out of Google's work on Chrome. Then we build with dash dash build, which runs Ninja for us, and run sg, which prints its line.

Nodes and relationships

15:02 The graph goes in a header, graph dot h. It's wrapped in a header guard, a define named after the file's path, as the style guide asks, so that a file that pulls it in twice doesn't declare everything twice. We include cstddef, for size t, the type the standard library uses for sizes. Then cstdint, for integers of a fixed width, such as thirty-two bits. And string, for the names of nodes and the types of relationships. String view comes next, which is a view of characters that someone else owns, so a function can take any text without copying it. Unordered map is the standard library's hash map, which we're going to use to find a node by its name. And vector, its growable array, where the nodes and the relationships live. Everything goes in a namespace, smollergraph, so our names can't clash with another library's. A node's id is a thirty-two bit unsigned integer, which we name NodeId with a using alias, and a relationship's id gets a type of its own. Four billion of each is plenty for now, and they take half the memory of sixty-four bit ids, which matters once there are millions of them. A Node is a struct, which in C++ is a class whose members are public, and we use it for plain data. It holds the node's name, and a vector with the ids of the relationships that start at it. Above it, we write why: the relationships that start at this node, so a hop needs no search. A Relationship holds its type, such as EATS, and the two nodes it joins, from and to, which also give it its direction. Then the Graph class, and over it, a comment saying it's a graph kept in memory, nodes by name, and relationships with a type and a direction. Add node takes a name and returns that node's id, adding the node the first time it sees the name, which its comment says. Add relationship joins two nodes with a type. Neighbours returns the nodes one hop from a node, along relationships of one type. It's marked const, which means calling it can't change the graph, so it works on a graph we're just reading. Then three small accessors, which the style guide names in lowercase: a node's name, and how many nodes and relationships there are. Inside, the graph keeps its nodes and its relationships in two vectors, so an id is a place in a vector. And a hash map goes from a name to a node's id. Each data member ends in an underscore, which is how the style guide marks them. In graph dot c c, add node first works out the id a new node would get, which is the number of nodes so far. The size of a vector is a size t, which is sixty-four bits on our machines, so a static cast converts it to our thirty-two bit id, saying that we mean it. Try emplace puts the name in the map with that id, unless the name is there already. It returns where the entry is and whether it added it, which a structured binding unpacks into two names. If it added it, we push the node onto the vector, with designated initialisers, which name each field as we fill in the struct. Either way, we return the id the map holds. So asking for the rabbit twice gives the rabbit's id both times, and the graph doesn't get a second rabbit. The map and the vector stay in step, as both of them change inside that one if. Add relationship takes the ids of the two nodes it joins, and the type between them, as a string view. It works much like Add node, giving the new relationship the next id, which is the number of relationships so far, with a static cast like before. Then it pushes the relationship onto the vector, with its type and its two nodes. Then it appends that id to the out list of the node it starts from. Neighbours goes through the ids in the node's out list, and looks each relationship up by its id, which is a place in a vector. It keeps the ones of the type we asked for, and collects the node each one points to. So the line that appends a relationship's id to its node is the whole idea of index-free adjacency, in its simplest form: a node keeps a list of its relationships, so a hop doesn't search for them. In CMake, add library makes a library, smollergraph, from graph dot c c, so that the program and, later, the tests can both use the graph. Target include directories lets whatever links the library include its headers from src. And sg links it, privately, as nothing links sg in turn. In main, we include graph dot h, our own header, and make a graph by hand. We add the red fox, with two relationships of EATS, to the rabbit and the field mouse. Each Add node inside those calls adds the prey the first time it's named, and returns its id. And the fox gets one relationship of LIVES_IN, to the forest. Then we print what the fox eats, with a range-based for loop, which goes through each id that Neighbours returns.

20:04 Let's build it, which compiles the library and links it into sg. And when we run it, it prints that the red fox eats the rabbit, and the field mouse, while the forest is left out, as that relationship is of another type.

Facts from a file

20:19 Instead of building the graph by hand, we're going to read it from a file. Data slash animals dot txt holds the knowledge graph from the start of the episode, a fact a line, written as a Cypher pattern. The first node goes in round brackets, then the relationship's type in square brackets with an arrow, and then the node it points to. The first four facts say what each animal is: the red fox, the rabbit and the field mouse are mammals, and the tawny owl is a bird. The next four say where they live, with the fox and the owl in the forest, and the rabbit and the mouse in the meadow. The clover and the wheat grow in the meadow too. And the last five are the food chain. The fox eats the rabbit and the field mouse, and the owl eats the field mouse as well. The rabbit eats clover, and the field mouse eats wheat. So there are ten nodes, for four animals, two plants, two classes and two habitats, and fifteen relationships between them. A line starting with a hash is a comment, which says what the file holds. Writing facts this way keeps the file easy to read, and close to how we'd ask for them in Cypher. Facts dot h declares Load facts, the function that reads them. It includes istream, the standard library's input streams, so it reads from a file and, in a test, from a string. Then graph dot h, for the graph it fills in. Load facts takes the stream, the graph to add the facts to, and a string for the error. The graph and the error are references, with an ampersand, so the function changes the caller's objects and not copies of them. Taking a stream instead of a file name keeps files out of it, which is what lets a test hand it a string. An error that comes back as a value also shows up in the function's signature, so a caller can see that it has to check. It returns a bool, which is true when it read the whole stream. The style guide doesn't use exceptions, so a failure comes back as the return value, with the line it couldn't read in the error. Its comment says all of this: it reads facts into the graph, one a line, written as Cypher patterns, such as the red fox eating the rabbit. Blank lines and lines starting with a hash are skipped, and on a line it can't read, it stops, puts the line in the error and returns false. In facts dot c c, we include string view, as we're going to cut each line into pieces without copying them. Load facts has the signature from the header, and its body is a loop over the lines. We read the stream a line at a time, into one string we reuse, with get line. Get line returns the stream, which turns false once there's nothing left to read, and that ends the loop. We skip blank lines and comments, with starts with, which strings have from C++20. Then we look for the two places where a fact splits. The first is where the opening node closes and the relationship opens, and the second is where the relationship ends in its arrow. Find returns where each one is, or n pos when it isn't there. If the line doesn't start and end with a bracket, or either piece is missing, or they're the wrong way round, we keep the line as the error and stop. Then we take the pieces as string views of the line, without copying it. The first name is between the opening bracket and the first piece, and the type is between the two pieces. The second name is what's left after the arrow, without the closing bracket, which the comment over it says. Add node gives us both nodes, adding them the first time they're named, and add relationship joins them. And once the loop has read the last line, Load facts returns true. Facts dot c c goes into the library, next to the graph. Main now takes the file's path as an argument. We include fstream, for reading files, and string, along with our facts dot h. Arg c is how many arguments the program got, counting its own name, and arg v holds them. With anything other than one argument, we print how to use it, to standard error, and return one, so a script can tell that it failed. We open the file with an input file stream, and check that it opened. Then we load the facts, and if a line can't be read, we print it, so whoever runs sg can see which fact to fix, and return one. Returning one tells a script that something went wrong, as it does after the usage. And at the end, we print the counts. The stream operator chains one piece after the next onto standard out: the number of nodes, and then the number of relationships.

24:46 We build it again, and run it on the animals, which reads the file a line at a time into the graph. That gives ten nodes and fifteen relationships, the counts Neo4j loaded from its own file at the start.

Walking the graph

25:00 To start a walk from a node by its name, the graph needs a way to look a name up without adding it. So graph dot h includes optional, the standard library's type for a value that may or may not be there. Find returns an optional node id, which is empty when there's no node by that name. It's const, like Neighbours, as looking a name up doesn't change the graph. Returning an optional, and not a made-up id that means no node, makes the caller check before using it. Its comment says it returns the node with this name, if the graph has one. In graph dot c c, Find looks the name up in the map, and returns standard null opt, the empty optional, when it isn't there, or the id when it is. The walk gets a header of its own, query dot h, as it's the first piece of what's going to become our query engine. Walk takes the graph, a start node, a relationship type and a number of hops. It returns the nodes that many hops away, each once, in the order a breadth-first walk reaches them. Breadth first means it goes a hop at a time, and finishes all the nodes at one distance before it moves on to the next. In query dot c c, we include algorithm, for find, and utility, for move. Walk keeps a frontier, the nodes at the distance it has reached, which starts out as the start node on its own. For each hop, it builds the next frontier from the neighbours of each node in the current one. Two paths can lead to one node, such as two animals that eat one plant, so a node goes in once, which standard find checks. The comment over that check says so: two paths can lead to one node, and it's listed once. A search through a vector is plenty for a few nodes, and we can come back to it when the graph gets bigger. Then the next frontier becomes the current one, moved instead of copied, as we don't need the old one any more. And after the last hop, the frontier that was moved into place is the answer. Query dot c c joins the library, next to the graph and the facts. In main, we include charconv, for turning text into a number, then optional, for what Find returns, and string view. And query dot h, our new header, for the walk. Main takes four arguments now: the file, the start node's name, the relationship type and the number of hops. Loading the facts works as it did before, with the file's path in the first argument. Then Find looks the start node up, by the name in the second argument, and if it isn't there, we say so and return one. The hops come in as text, so from chars converts them, and it reports an error without exceptions. We check that it read the whole argument, as a number that isn't negative. Then we walk, and print each node's name.

27:49 Let's build it, and ask for one hop of EATS from the red fox, which follows the fox's relationships of that type to the nodes they point at. That gives us the rabbit and the field mouse. With two hops, we go down the food chain, from the fox's prey to what they eat in turn, which is the clover and the wheat. And that's the answer Neo4j and Kùzu gave us earlier, from under two hundred lines of our own C++.

Tests

28:17 Now that we've seen it work, let's pin it down with tests. We're going to use GoogleTest, Google's test framework for C++. Fetch content, a module that comes with CMake, downloads it when we configure, from the release we name by its version. Make available then adds it to our build, like a part of our own project. Enable testing turns on CTest, CMake's test runner. All of this goes before the warning flags, so that they apply to our code and not to GoogleTest's. At the bottom, the tests are an executable of their own, linked with our library and with g test main, which gives them a main function that runs all the tests. Then g test discover tests registers each test with CTest, so it can run them and report them one by one. In graph test dot c c, the style guide puts the header under test first, graph dot h. Then sstream, for a string stream, which lets us hand Load facts text from a string instead of a file. Our other two headers come next, along with GoogleTest's. The tests go in our namespace, inside an unnamed namespace, which keeps what's in it private to this file. A small helper, Names, turns node ids into their names, so a test can compare strings we can read. The first test checks that adding a name twice gives back one node, so a name can't end up as two nodes. Expect EQ checks that two values are equal, and reports a failure but carries on with the test. The second checks that Neighbours follows one type of relationship. It builds a small graph by hand, like main did in step two. The prey and the forest are added inside the calls that join them to the fox, which eats the rabbit and lives in the forest. Then it checks that the fox's neighbours along EATS are the rabbit alone, and not the forest. The third loads the food chain from a string. The string is a comment and four facts, written across lines, as C++ joins string literals that sit next to each other. They're the food chain from the file: the fox eats the rabbit and the field mouse, which eat the clover and the wheat. Then the test loads them into a graph. Assert true stops the test right there if the facts don't load, and prints the error, as the rest of the test would make no sense. And it walks two hops from the red fox, which has to give the clover and the wheat. Find gives us the fox's id, and the star in front of it takes the value out of the optional, which is there, as we've just loaded the fox. And the last checks that a line that isn't a fact stops the load. Its line has the type outside of square brackets, which Load facts can't read. Expect false checks that the load fails, and Expect EQ that the error holds the line, so whoever reads the message knows which fact to fix. Last, a README says how to build it, run it and test it.

31:06 We configure again, which downloads GoogleTest this time, and build it, along with our tests. Then ctest runs them, with dash dash test dir pointing it at the build folder, and all four of them pass.

31:20 So, that's our throwaway graph, and what it leaves us with. The CMake project, the tests, the facts file and the three functions the rest of the code calls are going to stay. The vectors behind those functions are what goes, as everything they hold is gone the moment sg exits. From here, the plan is to move the nodes and relationships into pages on disk, behind these functions, so that our tests keep checking that the answers don't change.

Wrap-up

31:46 So, today we looked at why graphs come up in so many places, and at where smollerGraph is heading: a knowledge graph that mvGPT can use, with a browser UI of its own to draw it. We went through the property graph model, and Cypher, which draws the pattern a query looks for. We saw how Neo4j keeps a graph as records that point at each other, and how Kùzu keeps it in columns, with compressed sparse row adjacency, and we ran our food chain query on both. We went through the decisions that are still open, along with a rough plan for building it. And we wrote a first, throwaway graph in C++, which keeps each node's relationships beside it, walks the food chain to the clover and the wheat, and has tests to pin that down.

32:31 This is going to be an evolving project, and right now it's very much open, so I'd love to hear from you. Let me know in the comments what you'd like a graph database of our own to do, and if you'd like to follow along, subscribe to the channel. I hope you find this useful, and thanks for watching.