Differences

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

--- notes:internals:trie [2025/08/12 19:51] – smj-edison
+++ notes:internals:trie [2025/09/07 01:51] (current) – smj-edison
@@ Line 1: / Line 1: @@
 ===== The Trie =====
-A Trie is the data structure that underlies Folk's database. It is the index to all Wishes, Claims,
+A Trie is the data structure that underlies Folk's database. It is the database's index for all Statements.
-and Whens. The Trie works by inserting and removing Clauses. A Clause is an array of space-seperated
+Let's look at an example Statement with the Clause "the sky is blue".
-words*, with each word being called a Term. An example Clause, "the sky is blue", would
-become ["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|}}
@@ Line 14: / Line 12: @@
 {{notes:pxl_20250811_193540816.jpg?200|}}
-As seen, a Trie is just a tree, with each successive Term placed one level deeper in the tree†.
+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
@@ Line 42: / Line 40: @@
 also get the value "10". We'll see why this is important in the next article.
+=== Footnotes ===
-* This is a little misleading, as the Trie can have Terms with spaces in them. For example,
+* Technically, the definition of a trie uses a level for each letter,
-the last Term in `Wish $this has name "Mason Jones"` has spaces in it. It's just that tcl lists are
-space seperated (without quotes or escaping), and all the tcl commands for the Trie take in lists.
-† 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.