Menu
There is the "put a FK to your parent" method, i.e. each records points to it's parent.
Which is a hard for read actions but very easy to maintain.
And then there is a "directory structure key" method:
0001.0000.0000.0000 main branch 1 0001.0001.0000.0000 child of main branch one etc Which is super easy to read, but hard to maintain.
What are the other ways and their cons/pros?
212
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.
Database type Unless you're aiming at huge amounts of data I suggest you go with any of the SQL databases that you know best (MSSQL, MySQL, Oracle). But if your database will contain enormous number of hierarchy nodes then flirting with a specialised graph-oriented database may be a better option.
An RDBMS is a type of database management system (DBMS) that stores data in a row-based table structure which connects related data elements.
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.
As always: there is no best solution. Each solution makes different things easier or harder. The right solution for you depends on which operation you will do most.
Naive Approach with parent-id:
Pros:
Easy to implement
Easy to move a big subtree to another parent
Insert is cheap
Needed Fields directly accessible in SQL
Cons:
Retrieving a whole tree is recursive and therefore expensive
Finding all parents is expensive too ( SQL doesn't know recursions... )
Modified Preorder Tree Traversal ( saving a start- & end-point) :
Pros:
Retrieving a whole tree is easy and cheap
Finding all parents is cheap
Needed Fields directly accessible in SQL
Bonus: you're saving the order of childnodes within its parentnode too
Cons:
Saving a path in each Node:
Pros:
Finding all parents is cheap
Retrieving a whole tree is cheap
Inserting is cheap
Cons:
Moving a whole tree is expensive
Depending on the way you save the path, you won't be able to work with it directly in SQL, so you'll always need to fetch & parse it, if you want to change it.
Closure table
Pros:
Easy to implement
Finding all parents is cheap
Inserting is cheap
Retrieving whole trees is cheap
Cons:
Needs an additional table
Takes up a lot of space compared to other approaches
Moving a subtree is expensive
I'd prefer one of the last two, depending on how often the data changes.
See also: http://media.pragprog.com/titles/bksqla/trees.pdf
180
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
