news.clarionlife.net

My Comments About A Trees

We use one table to create a tree normally. This table should contain at least two columns. One column is the identifier of the record. The second column is the identifier of the parent record.

Example:

Office
   Lawyer department
      Bob
      John
   Tech department
      Dave
      Michael

 ID ParentID Desc
 1   0       Office
 2   1       Lawyer department
 3   2       Bob
 4   2       John
 5   1       Tech department
 6   5       Dave
 7   5       Michael

If we want to climb up or down the tree, then typically we use a recursion. This works but not effective. This method becomes slow when the table becomes large.

To speed up the movement, you can add an additional field that will contain the path to the first parent. This is a string field. The format you can define yourself.

Example:

 ID ParentID Path          Desc
 1   0       .1.           Office
 2   1       .1.2.         Lawyer department
 3   2       .1.2.3.       Bob
 4   2       .1.2.4.       John
 5   1       .1.5.         Tech department
 6   5       .1.5.6.       Dave
 7   5       .1.5.7.       Michael

“Path”-field helps to easily and quickly identify all the children of the selected record. You should have the index for this field of course. You can create triggers that will automatically build the “Path”-field.

But it turned out that the definition of the parent of choosed record is too slow. So I found another way. The method is that you must add additional table, which contains all the parents’ IDs to the upper level for each record.

I have read about this method about two years ago and used it on a large SQL-tables.

 Table                               Additional Table
 ID ParentID Desc                     ID  ParentID
 1   0       Office                   1      0
 2   1       Lawyer department        2      1
 3   2       Bob                      2      0
 4   2       John                     3      2
 5   1       Tech department          3      1
 6   5       Dave                     3      0
 7   5       Michael                  4      2
                                      4      1
                                      4      0
                                      5      1
                                      5      0
                                      6      5
                                      6      1
                                      6      0
                                      7      5
                                      7      1
                                      7      0

You can move up and down on the table more quickly. This method is suitable for tps-tables and for SQL. You must create an indexes of course. For SQL you can create triggers that will fill in the additional table. The additional table may also contain additional fields, for example, the “Level”-field.

Tags: trees | No Comments »