August 8, 2020
Hot Topics:

Using the Nested Set Data Model for Breadcrumb Links

  • By Jason Mauss
  • Send Email »
  • More Articles »

It's likely that you have seen what I'm referring to as breadcrumb links before. For example, an online sporting goods store might display breadcrumb links (usually found around the top of the page) so you can see which area of their site you are currently browsing and how you got there:

Home > Sporting Equipment > Tennis > Racquets > Wilson

It's less likely however, that you've heard of what's known as the Nested Set Model of Hierarchies. I know it was new to me when I read about it in a book titled Joe Celko Trees and Hierarchies in SQL for Smarties. So, before I write about how to model breadcrumb link data with this model, I'm going to provide an explanation of what the nested set model is. My explanation might be an oversimplification when compared with the chapter on nested sets from Celko book (and in fact I will be borrowing some ideas and concepts from his book), but it should serve the purpose of getting you familiar with the concept. I would strongly encourage anyone interested in this article to pick up Celko book. (And no, he didn't pay me or ask me give him the ringing endorsement.)

Adjacency List Model vs. Nested Set Model

Even if you've only been a database developer for short time, you've probably either read about or encountered a data model that required storing hierarchical data. The most common example of this kind of data is an organizational chart or "org chart." Most database designers and books on database design will show you how to model an org chart using the simple adjacency list model, like this:

 BossName VARCHAR(32),
 JobTitle VARCHAR(32));

You could add columns such as Salary, HireDate, and others to this table to make it more useful, but I'm sure you get the idea. This model produces a table like this:

EmpName BossName JobTitle
Steve Dave Sr. Vice President
Gary Dave VP Sales
Julia Gary Sales Rep
Kristy Gary Sales Rep
John Gary Sales Rep

Even if you were to fix the obvious normalization problems this example has, it is fraught with weaknesses when it comes to managing the insertion, deletion, and update of records within the hierarchy. It is also limited when it comes to writing self-join queries to do tree traversals. Additionally, the more you try to extend this self-join pattern, the worse query performance becomes.

So what's the answer? The nested set model, of course.

The nested set model design uses two columns to model containment, which represents the subordination that was represented previously in the adjacency list model with the BossName column acting as a foreign key. These two columns can be called "Left" and "Right" or "Begin" and "End" or anything that widely appeals to most people's concept of containment. If you decide to go with "Left" and "Right," you'll need to abbreviate them somehow because they are reserved words in SQL. Something like "lft" and "rgt," for example. I'm going to use "Lft" and "Rgt" because of the left-to-right nature of the images included along with the text of this article.

Breadcrumb Links with the Nested Set Model

Here is what the DDL looks like for your BreadCrumbLinks table. I'll explain which columns hold which pieces of data if it's not clear to you from the column names and the table data.

CREATE TABLE BreadCrumbLinks(
SiteAreaUrl   CHAR(32) NOT NULL,

Which, after some INSERT statements, gives you this:

SiteAreaName SiteAreaUrl Lft Rgt
Home Default.aspx 1 24
SportingGoods SportingGoods.aspx 2 23
Tennis Tennis.aspx 3 14
Racquets TennisRacquets.aspx 4 13
Prince RacquetCategory.aspx?Brand=Prince 5 6
Wilson RacquetCategory.aspx?Brand=Wilson 7 8
Head RacquetCategory.aspx?Brand=Head 9 10
Yonex RacquetCategory.aspx?Brand=Yonex 11 12
Golf Golf.aspx 15 22
Drivers GolfClubs.aspx 16 21
Ping ClubCategory.aspx?Brand=Ping 17 18
TaylorMade ClubCategory.aspx?Brand=TaylorMade 19 20

As you can tell, I've once again used the Sporting Goods online store concept for the test data. If you're confused by the numbers in the Lft and Rgt columns, don't worry. I was also confused by them until I saw how they were used and managed. I'll discuss that shortly. First, I want to explain the columns and the data they hold.

The SiteAreaName column holds the text to be displayed for the link. This is what will go between your <a> and </a> tags. The SiteAreaUrl column holds the URL for the link. This is the href attribute value for the anchor tag. The Lft and Rgt columns hold the hierarchical information that you'll look at now.

If you look at the first row (Home), you will notice that the value in the Rgt column is (and will always be) double the number of rows in the table. Now, look at this data represented in a several different ways so that the relationships become more noticeable.

Listing 1: Data represented as XML

1   <Home>
2      <SportingGoods>
3         <Tennis>
4            <Racquets>
5               <Prince>
6               </Prince>
7               <Wilson>
8               </Wilson>
9               <Head>
10              </Head>
11              <Yonex>
12              </Yonex>
13           </Racquets>
14        </Tennis>
15        <Golf>
16           <Drivers>
17              <Ping>
18              </Ping>
19              <TaylorMade>
20              </TaylorMade>
21           </Drivers>
22        </Golf>
23   </SportingGoods>
24  </Home>

In this XML data, you can see the relationship between the Lft column values (the opening tags) and the Rgt column values (the closing tags). Now, look at some images.

Note: I've omitted one of the racquet types (Prince) so that things would fit nicely in the images; therefore, the numbers are slightly different but still correct.

Figure 1 shows the data as a nested circle diagram that looks similar to a ven diagram without intersecting areas.

Figure 2 shows the data as line intervals, similar to a horizontal bar (or Gantt) chart.

Both of these images help illustrate the relationship between the data in the Lft and Rgt columns. Hopefully, this has made you familiar with how the nested set model uses the Lft and Rgt columns to define the hierarchical structure of the data. Now, look at how you can write queries to retrieve the data you need to build breadcrumb links.

Page 1 of 2

This article was originally published on July 5, 2005

Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

Thanks for your registration, follow us on our social networks to keep up-to-date