Folk Computer

A Trie is the data structure that underlies Folk's database. It is the database's index for all Statements. Let's look at an example Statement with the Clause “the sky is blue”.

Let's insert that Clause into the Trie and see what happens:

As you can see, the Clause has been turned into a set of nodes in the Trie. Let's try inserting another Clause, “the sky has clouds”:

As seen, a Trie is just a tree, with each successive Term placed one level deeper in the tree*.

We've now covered inserting, but what about querying? Let's try querying for “the sky has clouds”. We'll do this by comparing each Term of the query against the Trie:

It seems that “the sky has clouds” exists!

Notice how we never had to check the Term “blue”, since that was on a separate branch of the Trie. When there's thousands of nodes, the Trie effectively trims irrelevent branches at each level it traverses.

There's one last thing that I haven't mentioned: a Trie can contain values. Let's look at the previous Trie example, but now with values:

If we to rerun the query “the sky has clouds”, we'd not only get confirmation of existance, but we'd also get the value “10”. We'll see why this is important in the next article.

* Technically, the definition of a trie uses a level for each letter, not for each word. It makes more sense to be for each word in Folk though.