Thursday, February 25, 2010

MySQL Hierarchical Data

Original Post: May 21st, 2008

Two common ways of storing hierarchical data in MySQL are the Adjacency List Model and the Nested Set Model. The Adjacency uses a `parent id` to determine de parent of a record. The Nested Set Model uses the `left` and `right` values to determine the parent.


Adjacency List Model

Pros

  • Easy to implement
  • Queries are simpler to write
  • Fast updates
  • Fast Inserts

Cons

  • Retrieving the data is slower since it requires recursion to do it.

Nested Set Model

Pros

  • Faster selects.
  • Indefinite number of levels since with one query.

Cons

  • Queries are a little bit more complicated to write.
  • Updates are slow since multiple rows have to be updated.
  • Inserts are slower since multiple rows have to be updated.


Sample table structure for Adjacency List Model:

CREATE TABLE category(
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
parent INT DEFAULT NULL);

Sample Table Structure for Nested Set Model:

CREATE TABLE nested_category (
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
lft INT NOT NULL,
rgt INT NOT NULL
);

For more information on how to use these models visit the MySQL article by Mike Hillyer at http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

No comments:

Post a Comment