Nested Directory Structure in SQL

directories.sql

-- Create our directories table.
CREATE TABLE `directories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  `lft` int(11) NOT NULL,
  `rgt` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `directory_lft` (`lft`),
  UNIQUE KEY `directory_rgt` (`rgt`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

-- A procedure for creating space in the directory tree.
CREATE PROCEDURE allocate_directory_space (IN position int(11), IN size int(11))
MODIFIES SQL DATA
BEGIN
  DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
  START TRANSACTION;
  UPDATE `directories` SET `lft` = `lft` + size WHERE `lft` >= position ORDER BY `lft` DESC;
  UPDATE `directories` SET `rgt` = `rgt` + size WHERE `rgt` >= position ORDER BY `rgt` DESC;
  COMMIT;
END;

-- A procedure for removing space in the directory tree.
CREATE PROCEDURE deallocate_directory_space (IN position int(11), IN size int(11))
MODIFIES SQL DATA
BEGIN
  DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
  START TRANSACTION;
  UPDATE `directories` SET `lft` = `lft` - size WHERE `lft` > position ORDER BY `lft` ASC;
  UPDATE `directories` SET `rgt` = `rgt` - size WHERE `rgt` > position ORDER BY `rgt` ASC;
  COMMIT;
END;

-- A procedure for moving trees into or next to other trees.
CREATE PROCEDURE move_directory_tree (
  IN subject int(11),
  IN mode enum('left','right','into'),
  IN target int(11)
)
MODIFIES SQL DATA
BEGIN
  DECLARE old_lft int(11);
  DECLARE old_rgt int(11);
  DECLARE new_lft int(11);
  DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING BEGIN
    ROLLBACK;
    SELECT 0 AS `ok`, old_lft AS `lft`, old_rgt AS `rgt`;
  END;

  START TRANSACTION;

  -- Query for the old left and right values.
  SELECT `lft`, `rgt` INTO old_lft, old_rgt FROM `directories` WHERE `id` = subject;

  -- Check if the move is valid.
  IF target IN (SELECT `id` FROM `directories` WHERE `lft` >= old_lft AND `rgt` <= old_rgt) THEN
    ROLLBACK;
    SELECT 0 AS `ok`, old_lft AS `lft`, old_rgt AS `rgt`;
  ELSE
    -- Remove the directory we're moving by flipping it into negative space.
    UPDATE `directories` SET `lft` = (0 - `lft`), `rgt` = (0 - `rgt`)
    WHERE `lft` >= old_lft AND `rgt` <= old_rgt;

    -- Remove the space we've created.
    CALL deallocate_directory_space (old_lft, (old_rgt - old_lft) + 1);

    -- Determine target position.
    SELECT CASE mode
    WHEN 'left' THEN `lft`
    WHEN 'right' THEN `rgt` + 1
    WHEN 'into' THEN `rgt`
    END INTO new_lft FROM `directories` WHERE `id` = target;

    -- Allocate space at target position.
    CALL allocate_directory_space (new_lft, (old_rgt - old_lft) + 1);

    -- Move the subject and all of its children into the allocated space.
    UPDATE `directories`
    SET `lft` = (0 - `lft` + (new_lft - old_lft)), `rgt` = (0 - `rgt` + (new_lft - old_lft))
    WHERE `lft` < 0;

    COMMIT;
    SELECT 1 AS `ok`, new_lft AS `lft`, new_lft + (old_rgt - old_lft) AS `rgt`;
  END IF;
END;

-- A procedure for creating a new directory with a parent.
CREATE PROCEDURE create_directory (IN new_name varchar(255), IN parent int(11))
MODIFIES SQL DATA
BEGIN
  DECLARE position int(11);
  DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
  START TRANSACTION;
  SELECT `rgt` INTO position FROM `directories` WHERE `id` = parent;
  CALL allocate_directory_space (position, 2);
  INSERT INTO `directories` (`name`, `lft`, `rgt`) VALUES (new_name, position, position + 1);
  COMMIT;
  SELECT LAST_INSERT_ID() AS `id`;
END;

-- A procedure for creating a new directory without parents.
CREATE PROCEDURE create_directory_tree (IN new_name varchar(255))
MODIFIES SQL DATA
BEGIN
  INSERT INTO `directories` (`name`, `lft`, `rgt`)
  SELECT new_name, IFNULL(MAX(`rgt`) + 1, 1), IFNULL(MAX(`rgt`) + 2, 2)
  FROM `directories`;

  SELECT LAST_INSERT_ID() AS `id`;
END;

-- A procedure for removing a directory and its descendants.
CREATE PROCEDURE delete_directory_tree (IN subject int(11))
MODIFIES SQL DATA
BEGIN
  DECLARE old_lft int(11);
  DECLARE old_rgt int(11);
  DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
  START TRANSACTION;
  SELECT `lft`, `rgt` INTO old_lft, old_rgt FROM `directories` WHERE `id` = subject;
  DELETE FROM `directories` WHERE `lft` >= old_lft AND `rgt` <= old_rgt;
  CALL deallocate_directory_space (old_lft, (old_rgt - old_lft) + 1);
  COMMIT;
END;

unflatten.js

// MySQLDir :: { id :: Number, name :: String, lft :: Number, rgt :: Number }
// Directory :: { id :: Number, name :: String, children :: Array Directory }
// unflatten :: Array MySQLDir -> Array Directory
const unflatten = directories => {
  if (directories.length === 0) { return []; }
  const head = directories[0];
  const children = directories.filter(dir => dir.lft > head.lft && dir.rgt < head.rgt);
  const remainder = directories.filter(dir => dir.lft > head.rgt);
  return [{id: head.id, name: head.name, children: unflatten(children)}]
  .concat(unflatten(remainder));
};