Storing trees in a database
19th June 2003
SitePoint: Storing Hierarchical Data in a Database, by Gijs Van Tulder. The article first shows how the easy way of storing hierarchies in a database, using parent fields and a recursive PHP function to iterate up the tree. It then goes on to talk about a far more interesting alternative called “Modified Preorder Tree Traversal” where trees are first “flattened” in to a heap-like structure, then each node is stored with a pair of numbers representing that node’s position in the tree. I’d seen this somewhere before but Gijs Van Tulder’s explanation is far clearer, and comes with some good examples showing how this unconventional storage method can retrieve all of the eventual children of a node in a single query. He also talks about ways of updating the tree structure when new items are added.
More recent articles
- Weeknotes: the Datasette Cloud API, a podcast appearance and more - 1st October 2023
- Things I've learned about building CLI tools in Python - 30th September 2023
- Talking Large Language Models with Rooftop Ruby - 29th September 2023
- Weeknotes: Embeddings, more embeddings and Datasette Cloud - 17th September 2023
- Build an image search engine with llm-clip, chat with models with llm chat - 12th September 2023
- LLM now provides tools for working with embeddings - 4th September 2023
- Datasette 1.0a4 and 1.0a5, plus weeknotes - 30th August 2023
- Making Large Language Models work for you - 27th August 2023
- Datasette Cloud, Datasette 1.0a3, llm-mlc and more - 16th August 2023
- How I make annotated presentations - 6th August 2023