Procedimientos MySql para modelos anidados de estructuras árbol

Antes de comenzar, dejamos a cargo del lector el conocimiento sobre el tema, existe mucha bibliografía que podrá consultar.

La tabla

CREATE TABLE `nested_table` (
 `id` smallint(4) unsigned NOT NULL AUTO_INCREMENT,
 `left_id` smallint(6) NOT NULL,
 `right_id` smallint(6) NOT NULL,
 `row_name` varchar(16) NOT NULL,
 PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

Conforme al modelo anidado además de la clave id, cada registro tendrá una id por la derecha y por la izquierda.

Insertar

Para insertar un registro debe seleccionarse un nodo, e indicar si se le agregará un hermano (el id de apertura será right_id) o un hijo (el id de apertura será left_id, quedándo el nuevo nodo como primer hijo).

A partir de ese id de apertura se abre un espacio de 2 y se inserta el nuevo registro.

DELIMITER //
CREATE PROCEDURE `insertNestedRow`(
  IN `_peak_id` SMALLINT,
  IN `_is_first_child` TINYINT(1),
  IN _row_name VARCHAR (16)
)
BEGIN
  -- vars
  DECLARE _open_id SMALLINT DEFAULT 0;
  DECLARE _depth TINYINT(2) DEFAULT 0;
  SELECT
    IF (_is_first_child, left_id, right_id)
  INTO _open_id
  FROM `nested_table`
  WHERE id = _peak_id;

  -- open space with a width of 2, after the peak
  UPDATE `nested_table` SET left_id = left_id + 2 WHERE left_id > _open_id;
  UPDATE `nested_table` SET right_id = right_id + 2 WHERE right_id > _open_id;

  -- insert a new item
  INSERT INTO `nested_table` (left_id, right_id, row_name) VALUES (_open_id + 1, _open_id + 2, _row_name);
END//

Eliminar

Cuando se elimina un registro debe calcularse la apertura que produce, si es una hoja del árbol será de 2, pero si no lo es, la apertura se calcula como right_id - left_id.

Una vez calculada la apertura, se elimina el nodo y se cierra el espacio abierto.

DELIMITER //
CREATE PROCEDURE `deleteNestedRow`( IN _id SMALLINT )
BEGIN
 -- vars
 DECLARE _left_id, _right_id, _width SMALLINT DEFAULT 0;
 SELECT left_id, right_id, ( right_id - left_id + 1 ) INTO _left_id, _right_id, _width FROM `nested_table` WHERE id = _id;

 -- delete
 DELETE FROM `nested_table` WHERE (left_id BETWEEN _left_id AND _right_id);

 -- close the space
 UPDATE `nested_table` SET left_id = left_id - _width WHERE left_id > _left_id;
 UPDATE `nested_table` SET right_id = right_id - _width WHERE right_id > _right_id;
END//

Subir o bajar

Subir o bajar la posición de un registro con respecto a sus hermanos requiere varios datos. En principio, el ancho del nodo a mover, como cuando se elimina. También, la id de apertura como cuando se inserta. Por último,  la diferencia entre el nodo a mover y el de llegada (salto).

La condición del procedimiento garantiza que es posible reordenar el nodo.

DELIMITER //
CREATE PROCEDURE `upDownNestedRow`(
  IN `_id` SMALLINT,
  IN `_is_down` TINYINT(1)
)
BEGIN
 -- vars
 DECLARE _left_id, _right_id, _width, _jump, _open_id SMALLINT DEFAULT 0;

 SELECT left_id, right_id, ( right_id - left_id + 1 )
 INTO _left_id, _right_id, _width
 FROM `nested_table`
 WHERE IF (_is_down, id = _id, right_id = (SELECT left_id - 1 FROM `nested_table` WHERE id = _id));

 SELECT right_id, ( right_id + 1 - _left_id )
 INTO _open_id, _jump
 FROM `nested_table`
 WHERE left_id = _right_id + 1;

 IF FOUND_ROWS() = 1 THEN
 BEGIN
 -- open space
 UPDATE `nested_table` SET left_id = left_id + _width WHERE left_id > _open_id;
 UPDATE `nested_table` SET right_id = right_id + _width WHERE right_id > _open_id;

 -- move the item
 UPDATE `nested_table` SET left_id = left_id + _jump, right_id = right_id + _jump WHERE ( left_id BETWEEN _left_id AND _right_id );

 -- close the space left
 UPDATE `nested_table` SET left_id = left_id - _width WHERE left_id > _right_id;
 UPDATE `nested_table` SET right_id = right_id - _width WHERE right_id > _right_id;
 END;
 END IF;
END//

Mover

Hemos llegado al más complicado, pero si no dejamos de compararlo con las anteriores tareas resultará fácil.

Debemos indicar un nodo a mover, un nodo de llegada, y si el nodo a mover lo queremos hermano o hijo del nodo de llegada.

Se calculará el ancho del nodo a mover, la id de apertura, la diferencia entre el nodo a mover y el de llegada (salto) y, como novedad, un corrector, para el caso en que el salto sea negativo.

Que el salto sea negativo implica que al abrir el espacio se modifica las id izquierda y derecha del nodo a mover, de esto surge la necesidad de un corrector que se usa cuando efectivamente movemos nuestro nodo.

DELIMITER //
CREATE PROCEDURE `moveNestedRow`(
  IN `_id` SMALLINT,
  IN `_peak_id` SMALLINT,
  IN `_is_first_child` TINYINT(1)
)
BEGIN
 -- vars
 DECLARE _left_id, _right_id, _width, _jump, _open_id, _corrector SMALLINT DEFAULT 0;
 
 -- initialize vars
 SELECT left_id, right_id, ( right_id - left_id + 1 )
 INTO _left_id, _right_id, _width
 FROM `nested_table`
 WHERE id = _id;
 
 SELECT
 IF ( _is_first_child, left_id, right_id )
 INTO _open_id
 FROM `nested_table`
 WHERE id = _peak_id;
 
 SELECT _open_id + 1 - _left_id INTO _jump;

 IF _jump < 0 THEN
 SELECT _jump - _width, _width INTO _jump, _corrector;
 END IF;

 -- open space
 UPDATE `nested_table` SET left_id = left_id + _width WHERE left_id > _open_id;
 UPDATE `nested_table` SET right_id = right_id + _width WHERE right_id > _open_id;

 -- move the item
 UPDATE `nested_table` SET left_id = left_id + _jump, right_id = right_id + _jump WHERE (left_id BETWEEN _left_id + _corrector AND _right_id + _corrector);

 -- close the space left
 UPDATE `nested_table` SET left_id = left_id - _width WHERE left_id > _right_id;
 UPDATE `nested_table` SET right_id = right_id - _width WHERE right_id > _right_id;

END//

Conclusión

La idea ha sido ser breves, los procedimientos podrán encontrarlos funcionando en extensiones como contents. Por claridad, no se incluyó los valores de id del padre y profundidad, pero conviene calcularlos y guardarlos, ya que facilitan la tarea de consulta de la tabla.