Differences

This shows you the differences between two versions of the page.

--- notes:internals:trie [2025/08/11 20:10] – created smj-edison
+++ notes:internals:trie [2025/09/07 01:51] (current) – smj-edison
@@ Line 1: / Line 1: @@
-===== Part 1: the Trie =====
+===== The Trie =====
-A Trie is the data structure that underlies Folk's database. It is the index to all Wishes, Claims, and Whens. The Trie works by inserting and removing Clauses. A Clause is an array of space-seperated words, with each word being called a Term. An example Clause, "the sky is blue", would become ["the", "sky", "is", "blue"].
+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 the Clause into the Trie and see what happens:
+Let's insert that Clause into the Trie and see what happens:
 {{notes:pxl_20250811_192744566.jpg?200|}}
-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 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":
 {{notes:pxl_20250811_193540816.jpg?200|}}
-A Trie is just a tree, with each level being one word*.
+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:
+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:
 {{notes:trie-lookup-level-1.jpg?400|}}
@@ Line 24: / Line 27: @@
 {{notes:trie-lookup-level-4.jpg?400|}}
-Notice how we never had to check "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 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.
-* 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.
+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:
+{{notes:internals:trie-with-values.jpg?400|}}
+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.
+=== Footnotes ===
+* 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.