在关系型数据库中存储树状结构的已知方式有哪些？[英] What are the known ways to store a tree structure in a relational DB?

问题描述

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?

推荐答案

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:

• Inserting / Updating can be very expensive, as you'll maybe have to update a lot of nodes

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

其他推荐答案

Modified Preorder Tree Traversal

This is a method which uses a non-recursive function (usually a single line of SQL) to retrieve trees from the database, at the cost of being a little trickier to update.

**

Section 2 of the Sitepoint article Storing Hierarchical Data in a Database for more detail.

其他推荐答案

I'd say the "golden way" to store a hierarchical data structure is to use a hierarchical database. Such as, for instance, HDB. That's a relational database that handles trees quite well. If you want something more powerful, LDAP might do for you.

A SQL database is ill-suited to this abstract topology.