How to represent a data tree in SQL?

 

I'm writing a data tree structure that is combined from a Tree and a TreeNode. Tree will contain the root and the top level actions on the data. I'm using a UI library to present the tree in a windows form where I can bind the tree to the TreeView.

I will need to save this tree and nodes in the DB. What will be the best way to save the tree and to get the following features:

  • Intuitive implementation.
  • Easy binding. Will be easy to move from the tree to the DB structure and back (if any)

    • I had 2 ideas. The first is to serialize the data into a one liner in a table. The second is to save in tables but then, when moving to data entities I will loose the row states on the table on changed nodes.

    Any ideas?

    The easiest implementation is adjacency list structure: 

    id  parent_id  data

    However, some databases, particularly MySQL , have some issues in handling this model, because it requires an ability to run recursive queries which MySQL lacks.

    Another model is nested sets : 

    id lft rgt data

    where lft and rgt are arbitrary values that define the hierarchy (any child's lft , rgt should be within any parent's lft , rgt )

    This does not require recursive queries, but it slower and harder to maintain.

    However, in MySQL this can be improved using SPATIAL abitilies.

    See these articles in my blog:

  • Adjacency list vs. nested sets: PostgreSQL
  • Adjacency list vs. nested sets: SQL Server
  • Adjacency list vs. nested sets: Oracle
  • Adjacency list vs. nested sets: MySQL

    • for more detailed explanations.

    I've bookmarked this slidshare about SQL-Antipatterns, which discusses several alternatives: http://www.slideshare.net/billkarwin/sql-antipatterns-strike-back?src=embed

    The recommendation from there is to use a Closure Table (it's explained in the slides).

    Here is the summary (slide 77): 

                      | Query Child | Query Subtree | Modify Tree | Ref. Integrity
Adjacency List    |    Easy     |     Hard      |    Easy     |      Yes
Path Enumeration  |    Easy     |     Easy      |    Hard     |      No
Nested Sets       |    Hard     |     Easy      |    Hard     |      No
Closure Table     |    Easy     |     Easy      |    Easy     |      Yes

    I'm suprised that nobody mentioned the materialized path solution, which is probably the fastest way of working with trees in standard SQL.

    In this approach, every node in the tree has a column path, where the full path from the root to the node is stored. This involves very simple and fast queries.

    Have a look at the example table node: 

    +---------+-------+
| node_id | path  |
+---------+-------+
| 0       |       |
| 1       | 1     |
| 2       | 2     |
| 3       | 3     |
| 4       | 1.4   |
| 5       | 2.5   |
| 6       | 2.6   |
| 7       | 2.6.7 |
| 8       | 2.6.8 |
| 9       | 2.6.9 |
+---------+-------+

    In order to get the children of node x, you can write the following query: 

    SELECT * FROM node WHERE path LIKE CONCAT((SELECT path FROM node WHERE node_id = x), '.%')

    Keep in mind, that the column path should be indexed, in order to perform fast with the LIKE clause.

    链接地址: http://www.djcxy.com/p/93876.html

    上一篇: 从MySQL中的分层数据生成基于深度的树（无CTE）

    下一篇: 如何在SQL中表示数据树？