Menu
The so-called trie data structure poses an interesting way to store data in an easily searchable manner. When segmenting sentences of text into lists of words, it is often possible to combine the first few words that some sentences have in common.
Inserting a key into Trie is a simple approach. Every character of the input key is inserted as an individual Trie node. Note that the children is an array of pointers (or references) to next level trie nodes. The key character acts as an index to the array children.
The materialized path in the tree is the prefixed sequence of characters itself. This also forms the primary key. The size of the varchar column is the maximum depth of trie you want to store. I can't think of anything more simple and straightforward than that, and it preserves efficient string storage and searching.
MongoDB allows various ways to use tree data structures to model large hierarchical or nested data relationships. Presents a data model that organizes documents in a tree-like structure by storing references to "parent" nodes in "child" nodes.
How about the Materialized Path design?
CREATE TABLE trie (
path VARCHAR(<maxdepth>) PRIMARY KEY,
...other attributes of a tree node...
);
To store a word like "stackoverflow":
INSERT INTO trie (path) VALUES
('s'), ('st'), ('sta'), ('stac'), ('stack'),
('stacko'), ('stackov'), ('stackove'), ('stackover'),
('stackover'), ('stackoverf'), ('stackoverflo'),
('stackoverflow');
The materialized path in the tree is the prefixed sequence of characters itself. This also forms the primary key. The size of the varchar column is the maximum depth of trie you want to store.
I can't think of anything more simple and straightforward than that, and it preserves efficient string storage and searching.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With