B+ tree index in C++: finding a node by name

Intro

0:00 Hello and welcome back to episode six, where we're going to give smollerGraph an index on the names of its nodes, a B+ tree, kept in pages on disk. Let's begin with a quick look at where we're going to be by the end of the episode.

0:14 By the end, typing the start of a name into the walk's form is going to bring up the names that start with it, read in order from the index. Picking the tawny owl fills it in, and the walk starts from there. And opening a graph no longer reads each of its nodes, however big it gets.

0:32 On the website of the series, you can find more information about the project. The code is open source on GitHub, tagged at each step of each episode, so that you can follow along, and each episode has a page here, with its chapters and its code.

Last time

0:47 Now, before we get to today's work, let's quickly go over what we did last time. We counted the pages sg reads and writes, and found six for each relationship we add, each one a system call. We wrote a buffer pool, which keeps pages in frames, with a table from pages to frames, pins and dirty pages. The clock picks which page leaves when the pool is full, and a latch keeps sg serve's threads apart. Loading the million relationships got many times faster, and the walks stopped reading pages at all. What we left alone is what happens when a graph opens: sg reads each node, to build a map from names to ids in memory. Today, that map moves to disk, as an index.

Today

1:27 Today, we're going to build an index that finds a node by its name, kept on disk. It starts as a single page of names in order, each with its node's id. Then pages split when they fill up, which grows it into a tree, a B+ tree. The graph finds nodes through it, so opening a graph reads nothing. As its names are in order, it can list the names that start with what's typed, which the UI is going to suggest. And we measure what it gives, and what it costs. All right, let's get started with what's slow about opening a graph.

Opening a graph

2:01 Let's measure where we left off, on last episode's code. We load the million relationships, with a hundred thousand people. With the buffer pool, that takes a fraction of a second. Then sg bench, which opens the graph before it walks, and times the opening too. Opening it takes about ten point four milliseconds, which is sg reading each of the hundred thousand node records, and putting each name in a hash map. That's quick here, but it grows with the graph: ten times the nodes, ten times the wait, and the map takes memory for each name, whether we ask for it or not.

2:33 A B+ tree keeps names in order, in pages. At the bottom are the leaves, where each name sits next to its node's id, in name order. Above them are pages of names that point the way: each of their names says which page holds the names from it on. So finding the red fox starts at the top, where Rabbit is the last name that isn't after it, and goes down to the page that Rabbit points at. Each page holds over a hundred names, so three levels hold over a million, and finding one reads three pages, from the pool.

A page of names

3:06 The index goes in a header of its own, name index dot h. It includes cstddef, cstdint, optional, string and string view, Abseil's status, and the buffer pool and the pager, as it keeps its pages in a file of its own, through a pool of its own. The class comment says what it is: an index from names to ids, kept in a file of pages as a B+ tree. It has leaves of names in order, each with its id, and pages above them that say which page holds which names, so finding a name reads a page on each level. K max name is the longest name it keeps, twenty-seven bytes, as long as a node's name. Open opens the index in a file, creating it when it isn't there, and Open temporary opens one in a file with no name, as the record files do. Both return a status, as the record files' do. Flush writes the changed pages to the file, through the pool. Find returns the id kept for a name, if there's one, as an optional. Insert keeps an id for a name, which its comment says the index doesn't have yet. In the private part, an entry is a name, padded with zeros, and the id kept for it, as its comment says. The name takes k max name plus one bytes, twenty-eight, so it always has room for its zero, and with the id that's thirty-two bytes. K header size is sixteen, and k entries is how many entries fit in a page after the header: a hundred and twenty-seven. A node, in a tree's sense of the word, is a page of the tree, laid out in the file as the comment says: a header of sixteen bytes, then its entries, in name order. Its header is whether it's a leaf, and how many entries it has, and two numbers we don't use yet. A static assert checks that a node fits in a page. The header, in page zero, says which page is the root, and how many pages the index has, as its comment says. Name of returns the name in an entry, up to its first zero. Position says how many of a page's entries come before a name, which its comment says is where the name is, or where it would go. Start, Load and Store come next, and k pool pages is four thousand and ninety-six, up to sixteen mebibytes of the index in memory, about a hundred and fifty thousand names, as the comment says. Last come the members: the pager, the pool on top of it, mutable like the record file's, and the root's page and the page count. In name index dot c c, we include algorithm, for the binary search, cstdio and cstdlib, for stopping with an error, and cstring. Open clears the pool, and opens the file. When the pager can't open it, Open returns its status, before starting anything, and otherwise it starts the index, and returns ok. Open temporary does that too, with a temporary file in place of a named one. Find loads the root, and looks for where the name would be, with Position. When an entry is there, and its name is the one we're after, we return its id, and otherwise nothing. Insert loads the root page too, to put the name in it. For now, the root is the whole index, a single leaf, and when it's full, we stop with an error, as pages don't split until the next step. Otherwise, Position says where among the entries the name goes. Copy backward moves the entries from there on along by one, from the back, so none of them overwrites another, and the comment says why: to make room. Then the entry at that spot is cleared with memset, so the name is padded with zeros, and the name is copied in with memcpy, cut to k max name bytes. The id goes in after it, and the page has one more entry. Store writes the changed page back, into its frame. Name of makes a string view of the name, up to its first zero, with strnlen, which stops at the end of the field when there's no zero, so the read stays inside the entry's own bytes. Position is a binary search, with lower bound, which finds the first entry whose name isn't before ours, in about seven steps for a hundred and twenty-seven entries. The lambda says how to compare an entry with a name, by the entry's name, as string views compare their bytes in order. Start sets up a new file, or reads one that has been set up, which its comment says. A new file gets a header that says the root is page one, and that there are two pages, and an empty leaf as its root. A file that has pages already gets its header read from page zero. Either way, we keep the root and the page count. The comment over Load says how pages come in and out of their frames: copied whole, as a node, which is safer than pointing into the frame's bytes as if they were one. Load fetches the page and copies it out, and Store fetches it and copies a node in, which marks it dirty. In CMake, name index dot c c joins the library, and its test joins the tests. Name index test dot c c includes the index, cstdio, optional and string, Abseil's status header, for comparing statuses, and GoogleTest. Finds what it keeps opens an index on a temporary file, and inserts the red fox, the rabbit and the clover, with ids of their own. It has to find each of them, and find no badger. Keeps its names in a file makes a path in GoogleTest's temporary folder, and removes a file left over there from an earlier run. Then it opens an index on that file, and inserts the tawny owl. At the closing brace, the index goes away, and its pool writes its pages. A second index opens the file, and has to find the tawny owl, with its id, four.

8:31 Let's build it, and run just the index's two tests: dash R runs the tests whose names match name index. Both of them pass, with the names kept in a single page.

Splits, and a tree

8:42 A page holds a hundred and twenty-seven names, so the next step is what happens when it's full. A new name goes into a full leaf, so the leaf keeps the first half of its names, and a new page, on its right, takes the rest. The page above needs to know about the new page, so the new page's first name goes up into it, pointing at it. That can fill the page above, which splits like the leaf did, and when the root splits, a new root goes above its two halves, and the tree is a level taller. That's why a B+ tree grows from the top, and why its leaves are always at one depth.

9:17 In name index dot h, we include vector. The entry's comment gets a second sentence: above the leaves, the id is the page that holds the names from that one on. The node's first unused number becomes first, which the comment says is the page for names before the first entry's, above the leaves. Child returns the page below a node that holds a name, or would. Insert under inserts an entry under a page, and when a page splits, it returns the entry that the page above needs, for the new page, as its comment says. Add puts an entry in a node at a position, splitting the page when it's full, and Store header writes the header page. In name index dot c c, Find now goes down from the root: while the page isn't a leaf, it loads the child that holds the name. Then it looks in the leaf as before. Insert now fills in an entry, with the name, padded with zeros, and the id, and inserts it under the root. When that returns a split, the comment says what happens: the root split, so a new root goes above its two halves, and the tree is a level taller. The new root's first page is the old root, and its one entry is the split's, which points at the new half. It gets the next page number, and becomes the root. Either way, Store header keeps the root and the page count. Insert under starts by loading the page it's given. A leaf adds the entry where Position says it goes. Above the leaves, it inserts under the child that holds the name, and if that child split, it adds the split's entry to this page, which may split this page too. Add copies the page's entries into a vector, and inserts the new one at its place. When they fit, they go back into the page, which is stored, and there's no split. When they don't, half is the middle of the entries, rounded down, and the comment over it says what happens: the page keeps its first half, and a new page on its right takes the rest. The right page is a leaf when this one is, and it gets the next page number. Up is the middle entry, pointing at the new page, which is what the page above gets. In a leaf, the right page takes the entries from the middle on, so the middle name stays in a leaf, where its id is. Above the leaves, the right page's first is the middle entry's page. The comment over it says what's different: the middle entry moves up, and its page becomes the first of the right half, so the right page takes the entries after the middle. Then the left page keeps the first half, and both pages are stored, the left one where it was, and the right one in its new page. Neither of them is full any more, so the next few names that land in them have room, without another split. Those lines are a split, from one full page to two half-full ones. Child, which picks the page to go down to, is a binary search too. End is just past the page's last entry. The comment says how a name finds its page. An entry's page holds the names from its name on, so the name we want is under the last entry whose name isn't after it, or under first, when they all are. Upper bound finds the first entry whose name is after ours, and we go under the entry before it, or under first, when there's none before it. Store header writes the root and the page count into page zero. The new test, Splits as it grows, opens an index on a temporary file, and inserts twenty thousand names, Person zero to Person nineteen thousand, nine hundred and ninety-nine, in a jumbled order. The comment says why so many: enough to split pages above the leaves too. Multiplying by seven thousand, nine hundred and nineteen, a prime, and taking the remainder visits each number once, in an order that jumps about. Each number goes in as a name, Person and the number, with the number as its id. Then each name has to be found, with its id, and a name one past the last has to be missing.

13:02 Let's build it, and run the index's tests again. All three pass, and the twenty thousand names come back, through a tree three levels deep.

The graph finds names in it

13:12 In name index dot h, the index passes its pager's counts on, as the record files do, page reads and page writes. In graph dot h, the graph includes name index dot h instead of unordered map, and its comment says it has an index that finds a node by its name. Flush flushes the names too, and the page counts add the index's reads and writes to the records', which their comment now calls the graph's files. At the bottom, the map from names to ids goes, and the names member takes its place, which its comment says is in a file of its own. In graph dot c c, the constructor opens a temporary file for the names too, as it does for the records. Open opens three files now, the nodes, the relationships and the names, each one if the one before it opened, and returns the first error, or ok. The loop that read each node to build the map is gone, along with its comment, so opening a graph reads no records at all. Add node inserts the new node's name into the index, with its id. And Find asks the index, instead of the map.

14:13 First, the tests, all of them, from episode one on, which pass with the graph finding its nodes through the index. Then we load the million relationships again, with the index this time. Loading is slower than it was, at about a second and a half, and we're going to come back to why. And opening the graph, which takes about zero point seven milliseconds now, as it reads nothing but the index's header, however many nodes the graph has.

Names by how they start

14:41 A hash map can find a name, but it can't tell you which names start with "Ra", as it keeps them in no order. Our leaves keep them in order, so they can, if a scan can go from one leaf to the next. In name index dot h, Names starting with returns up to a limit of names that start with a prefix, in order, as its comment says. The node's last unused number becomes next, and the comment gets a sentence: in a leaf, next is the leaf after it, or zero for the last one, as page zero is the header. In name index dot c c, a leaf's split now puts the new leaf between this one and the next, as the comment says, so a scan can go from leaf to leaf in name order. The new leaf's next is this leaf's old next, and this leaf's next is the new leaf. Names starting with goes down to the leaf where the prefix would go, the way Find does. The comment explains the rest: the names that start with the prefix sit together, from where the prefix would go, and may go on into the leaves after this one. So from that position, while we have fewer names than the limit, we read the next name. At the end of a leaf, we load the next leaf, and stop when there isn't one. A name that doesn't start with the prefix ends the scan, as all the later names are after it too. Starts with is new in C++ twenty, on string views, and it saves us comparing the first few characters by hand. The names come back as strings, so they outlive the pages they were read from. That loop reads names in order, a leaf at a time, which no hash map can do. The new test, Finds names by how they start, opens an index on a temporary file, and inserts a thousand people and a rabbit. It asks for the names that start with Person twelve, twenty at most. The comment over that says which they are: Person twelve and the ten after it, Person a hundred and twenty to a hundred and twenty-nine, in name order. So the scan returns eleven of them, starting with Person twelve and ending with a hundred and twenty-nine. Ra finds the rabbit, and nothing else, as no other name starts with it. Asking for all the names that start with Person has to return the thousand of them, and the last comment says what that check is for: the thousand people fill several leaves, and the scan goes through them. In graph dot h, the graph passes Names starting with on to its index. In api dot h, Names JSON returns a few of the graph's names that start with a prefix, in order, for the UI to suggest, which its comment says, over the declaration. In api dot c c, a new constant, k suggestions, says how many names the UI suggests at a time, which is eight, as its comment says. Names JSON starts an object with a field called names, and opens its array, in a string it builds up. Then it asks the graph for up to k suggestions names that start with the prefix, and appends each one through Json string, with a comma before all but the first, then closes the array and the object. Its test, Suggests names that start with what's typed, adds the red fox, the rabbit and the clover. R suggests the rabbit and the red fox, in name order, and Bad suggests nothing. In server dot c c, the handler for slash A P I slash names reads the prefix from the query string, and answers with Names JSON. In index dot html, the walk's name input sits in a span with the class names, next to an empty list, where the suggestions go. Autocomplete off stops the browser from suggesting names of its own over ours. The style sheet places the list under the input, in the panel's colour, hides it while it's empty, and lights up the name under the pointer. In graph dot js, the submit handler clears the suggestions, so the list goes away when a walk starts. Then, as the comment says, as a name is typed, sg serve suggests the names that start with it, from its index, and clicking one fills it in. From is the input, and suggestions is the list. On each input event, we read what's typed. When there's something, we ask slash A P I slash names for it, with the prefix in the query string, and otherwise we use an empty list of names. The list is another data join, a list item for each name, which shows the name. Clicking one puts it in the input, and removes the list's items. And the README says what the graph keeps in memory, and how it finds names: its pages sit in a buffer pool, and a B+ tree finds a node by its name.

19:06 With the page at the end of this episode, let's type an R into the walk's form. The index answers with the two names that start with it, the rabbit and the red fox, in order. Clicking the rabbit fills it in, and for one hop of EATS, the walk lights up the clover, which is what the rabbit eats.

What it costs

19:24 So, here's what the index gives us, for opening a graph. Opening the graph went from about ten point four milliseconds, building the map, to about zero point seven, reading a header, and the gap grows with the graph. Nor does the graph keep each name in memory any more, just the pages of the index it's using, through the pool.

19:46 And here's what it costs us, in return. Finding a name in a hash map is a single lookup in memory. Finding one in the tree means a page from the pool on each of its three levels, a binary search in each, and copying each page out of its frame. Loading looks up two names for each relationship, two million lookups for the million relationships, so the load went from about half a second to about a second and a half. That's a trade most databases make, and Neo4j's indexes are B+ trees too. And in return, the names come in order, which is what let us suggest them, and what range queries in Cypher are going to need later.

Wrap-up

20:24 So, today we built a B+ tree of names, in a file of its own, through the buffer pool. It started as a page of names in order, and splits grew it into a tree, a level at a time, from the top. The graph finds its nodes through it, so opening a graph reads nothing, and its leaves, linked in order, let the UI suggest names as they're typed. In return, loading got slower, as a tree lookup costs more than a hash map's. Next time, we're going to start on what Neo4j and Kùzu have that we don't: Cypher. A small subset of it, parsed and planned, so we can ask smollerGraph questions the way we asked them in episode one.

21:04 This is going to be an evolving project, so I'd love to hear from you. Let me know in the comments which index you'd have built, a hash or a tree, and if you'd like to follow along, subscribe to the channel. I hope you find this useful, and thanks for watching.