notexOPENOverview
Notex/Systems/Trie operations
13.11LESSON 11 OF 13 · 1 MIN READ

Trie operations

Always free to read
SECTION VIDEOTrie operations

Video coming soon. Start with the reading below.

COMING SOON

Trie is a core component of the autocomplete system. Let us look at how trie operations (create, update, and delete) work.

Create Trie is created by workers using aggregated data. The source of data is from Analytics Log/DB.

Update There are two ways to update the trie.

Option 1: Update the trie weekly. Once a new trie is created, the new trie replaces the old one.

Option 2: Update individual trie node directly. We try to avoid this operation because it is slow. However, if the size of the trie is small, it is an acceptable solution. When we update a trie node, its ancestors all the way up to the root must be updated because ancestors store top queries of children. Figure 13-13 shows an example of how the update operation works. On the left side, the search query “beer” has the original value 10. On the right side, it is updated to 30. As you can see, the node and its ancestors have the “beer” value updated to 30.

Design a search autocomplete system — original diagram 180

Delete We have to remove hateful, violent, sexually explicit, or dangerous autocomplete suggestions. We add a filter layer (Figure 13-14) in front of the Trie Cache to filter out unwanted suggestions. Having a filter layer gives us the flexibility of removing results based on different filter rules. Unwanted suggestions are removed physically from the database asynchronically so the correct data set will be used to build trie in the next update cycle.

Design a search autocomplete system — original diagram 181
Progress is saved on this device.
KEEP EXPLORING

One note leads to another.

Back to the library →
⌕
Search across the entire library ⌘ K