Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to represent a tree like structure in a db

I'm starting a project and I'm in the designing phase: I.e., I haven't decided yet on which db framework I'm going to use. I'm going to have code that creates a "forest" like structure. That is, many trees, where each tree is a standard: nodes and edges. After the code creates these trees I want to save them in the db. (and then pull them out eventually)

The naive approach to representing the data in the db is a relational db with two tables: nodes and edges. That is, the nodes table will have a node id, node data, etc.. And the edges table will be a mapping of node id to node id.

Is there a better approach? Or given the (limited) assumptions I'm giving this is the best approach? How about if we add an assumption that the trees are relatively small - is it better to save the whole tree as a blob in the db? Which type of db should I use in that case? Please comment on speed/scalability.

Thanks

like image 963
Guy Avatar asked Jul 04 '11 04:07

Guy


People also ask

How do you represent a tree in database?

You could use adjacency lists (your current idea), nested sets, or even (with appropriate database support) arrays of node ids to represent the path from the root. Which representation you choose depends on what you need to do to your data. @Kim, why array? If the graph is a tree, each node has at most one parent.

How do you represent a tree structure?

Binary Tree Representation: A tree is represented by a pointer to the topmost node of the tree. If the tree is empty, then the value of the root is NULL. A Tree node contains the following parts. In C, we can represent a tree node using structures.

How does DB store tree structure?

The standard method of storing hierarchical data is simple parent-child relationship. Each record in the database includes a —parent id—, and a recursive query through the records build the children, siblings, and levels of the tree.

Which database is best for tree structure?

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.


2 Answers

I showed a solution similar to your nodes & edges tables, in my answer to the StackOverflow question: What is the most efficient/elegant way to parse a flat table into a tree? I call this solution "Closure Table".

I did a presentation on different methods of storing and using trees in SQL, Models for Hierarchical Data with SQL and PHP. I demonstrated that with the right indexes (depending on the queries you need to run), the Closure Table design can have very good performance, even over large collections of edges (about 500K edges in my demo).

I also covered the design in my book, SQL Antipatterns: Avoiding the Pitfalls of Database Programming.

like image 179
Bill Karwin Avatar answered Oct 08 '22 07:10

Bill Karwin


Be sure to use some sort of low level-coding for the entity being treed to prevent looping. The entity might be a part, subject, folder, etc.

With an Entity file and and Entity-Xref file you can loop through one of say two relationships between the two files, a parent and a child relation.

A level is the level an entity found in a tree. A low-level-code for the entity is the lowest level an entity is found in any tree anywhere. Check to make sure the low level code of the entity you want to make a child is less than or equal to prevent a loop. after adding an entity as a child it will become at least one level lower.

like image 34
eric Avatar answered Oct 08 '22 08:10

eric