Creating trees from SQL queries in Javascript

javascript · json

Storing tree structures in a database is simple. Add a column for the parentid and everything makes sense.

Our example data:

[
  {"id": 456, "parentid": 123, "name": "Dogs"}
  {"id": 214, "parentid": 456, "name": "Labradors"}
  {"id": 123, "parentid": 0, "name": "Mammals"}
  {"id": 810, "parentid": 456, "name": "Pugs"}
  {"id": 919, "parentid": 456, "name": "Terriers"}
]
Figure 1

Which should turn to this tree:

  • Mammals
    • Dogs
    • Labradors
    • Pugs
    • Terriers

Figure 2

The problem when storing data in this format is that you need to create the properly ordered tree structure every time you query the data from the database.

Depending on the number of rows and the amount of requests you need to process this can create quite some load on your server(s).

One approach is to store additional columns in your database to retrieve the tree in the correct order. This is discussed in this post from 2003 in great detail. This approach has unmatched read performance but will break down when the tree gets bigger and is updated a lot. It also comes with a lot of additional writes when updating rows.

10 years later

Javascript is a lot faster these days and something unthinkable in 2003 is now reality:
Just let the client do it. And you get:

  • A Dead simple database structure.
  • Fast and easy database reads and updates.
  • Good for small and medium (less than 2000 nodes) trees.
  • If you use NodeJS you can just use these functions on the server.

If your tree has more than 2000 nodes

  • 2k-20k nodes: It still works but you should ask yourself why you need to retrieve such a huge tree anyway.
  • 20k+ nodes: It might still work but this post is not for you.

Again: Why do we want to do it like this

  • We want easy database updates.
  • If we add a node we add the row to the database with the proper parentid. Done.
  • If a node gets deleted we remove the row from the database. Done.
  • If we remove a parent node that has children and don’t move the children to another parent first or delete them. Then these children should become root nodes.
  • If we remove a root node all previous children will become root nodes.
  • We also want fast database reads and preserve the sorting within a group of nodes.
  • Most modern browsers will sort such a query in single digit milliseconds.

OK, let’s do it.

We are working with the data from Figure 1. It could be the result of this query:

SELECT id, parentid, name
FROM Animals
ORDER BY name

Step 1: Sort the query

Please Note: You can find a working version of these examples in this JSfiddle

Our example query in Figure 1 is ordered by name. We want to sort it so that all rows are in the correct order of the tree: Mammals, Dogs, Labradors, Pugs, Terriers

Grab the source code for these functions as Javascript or Coffeescript.

Now call _queryTreeSort like this:

var result = _queryTreeSort({q:
  [
      {"id": 456, "parentid": 123, "name": "Dogs"},
      {"id": 214, "parentid": 456, "name": "Labradors"},
      {"id": 123, "parentid": 0, "name": "Mammals"},
      {"id": 810, "parentid": 456, "name": "Pugs"},
      {"id": 919, "parentid": 456, "name": "Terriers"}
  ]
})
Figure 3

result is this sorted query:

[
    {"id": 123, "parentid": 0, "name": "Mammals"},
    {"id": 456, "parentid": 123, "name": "Dogs"},
    {"id": 214, "parentid": 456, "name": "Labradors"},
    {"id": 810, "parentid": 456, "name": "Pugs"},
    {"id": 919, "parentid": 456, "name": "Terriers"}
]
Figure 4

You might want to stop here if this result is all you needed. Read on to see another useful structure of this data.

If you want to create a simple hierarchical bullet list (like in Figure 2) with <ul> and <li> elements it gets a little complicated. You would loop over this data and need to compare the depth you are currently in with the depth of the previous and next element so you know when to open and close your <ul> elements. Not very nice. Let’s create an easy to use tree.

Step 2: Create the tree

Grab the source code for these functions as Javascript or Coffeescript.

Call _makeTree:

var tree = _makeTree({q: result})
Figure 5

Now tree is this nice nested tree structure:

[
  {
    "id": 123,
    "parentid": 0,
    "name": "Mammals",
    "children": [
      {
        "id": 456,
        "parentid": 123,
        "name": "Dogs",
        "children": [
          {
            "id": 214,
            "parentid": 456,
            "name": "Labradors"
          },
          {
            "id": 810,
            "parentid": 456,
            "name": "Pugs"
          },
          {
            "id": 919,
            "parentid": 456,
            "name": "Terriers"
          }
        ]
      }
    ]
  }
]
Figure 6

Note that some elements have an additional element called children.

Rendering the tree is easy now. This recursive function will loop over the outer array and call itself for each children element it encounters.

_renderTree = (tree) ->
  html = "<ul>"
  for e in tree
    html += "<li>#{e.name}"
    if e.children?
      html += _renderTree(e.children)
    html += "</li>"
  html += "</ul>"
  return html
Figure 7

The result is this HTML:

<ul>
  <li>Mammals
  <ul>
    <li>Dogs
      <ul>
        <li>Labradors</li>
        <li>Pugs</li>
        <li>Terriers</li>
      </ul>
    </li>
  </ul>
  </li>
</ul>
Figure 8

It doesn’t get any easier than this. Working with trees is fun again. Enjoy.

I will cover additional methods like “getting all parents of a node” which can be used for breadcrumbs navigation etc. in another post.

share