Flowdock
v1.1.6 - Show latest stable - 0 notes

This acts provides Nested Set functionality. Nested Set is similiar to Tree, but with the added feature that you can select the children and all of their descendents with a single query. A good use case for this is a threaded post system, where you want to display every reply to a comment without multiple selects.

A google search for "Nested Set" should point you in the direction to explain the database theory. I figured out a bunch of this from http://threebit.net/tutorials/nestedset/tutorial1.html

Instead of picturing a leaf node structure with children pointing back to their parent, the best way to imagine how this works is to think of the parent entity surrounding all of its children, and its parent surrounding it, etc. Assuming that they are lined up horizontally, we store the left and right boundries in the database.

Imagine:

  root
    |_ Child 1
      |_ Child 1.1
      |_ Child 1.2
    |_ Child 2
      |_ Child 2.1
      |_ Child 2.2

If my cirlces in circles description didn’t make sense, check out this sweet ASCII art:

    ___________________________________________________________________
   |  Root                                                             |
   |    ____________________________    ____________________________   |
   |   |  Child 1                  |   |  Child 2                  |   |
   |   |   __________   _________  |   |   __________   _________  |   |
   |   |  |  C 1.1  |  |  C 1.2 |  |   |  |  C 2.1  |  |  C 2.2 |  |   |
   1   2  3_________4  5________6  7   8  9_________10 11_______12 13  14
   |   |___________________________|   |___________________________|   |
   |___________________________________________________________________|

The numbers represent the left and right boundries. The table then might look like this:

   ID | PARENT | LEFT | RIGHT | DATA
    1 |      0 |    1 |    14 | root
    2 |      1 |    2 |     7 | Child 1
    3 |      2 |    3 |     4 | Child 1.1
    4 |      2 |    5 |     6 | Child 1.2
    5 |      1 |    8 |    13 | Child 2
    6 |      5 |    9 |    10 | Child 2.1
    7 |      5 |   11 |    12 | Child 2.2

So, to get all children of an entry, you

    SELECT * WHERE CHILD.LEFT IS BETWEEN PARENT.LEFT AND PARENT.RIGHT

To get the count, it’s (LEFT - RIGHT + 1)/2, etc.

To get the direct parent, it falls back to using the PARENT_ID field.

There are instance methods for all of these.

The structure is good if you need to group things together; the downside is that keeping data integrity is a pain, and both adding and removing an entry require a full table write.

This sets up a before_destroy trigger to prune the tree correctly if one of its elements gets deleted.

Show files where this module is defined (1 file)
Register or log in to add new notes.