Re: insertion and deletion in the nested set model

From: Joe Celko <71062.1056_at_compuserve.com>
Date: 2000/05/23
Message-ID: <8gd4go$rbe$1_at_nnrp1.deja.com>#1/1


>> I've read an old post by Joe Celko, explaining the nested set
model. Seems interesting, but it seams to me that insertion and deletion of rows within this model must be pretty hairy (it modifies the values of the rgt and lft columns of other rows)... How is this handled usually? <<

  1. organizational structures usually change slower than the membership of the organization.
  2. The tree structure is in its own table, and the rows are small.
  3. The size of the gap to close after a DELETE FROM is computed by the MAX(rgt) minus the size of the subtree that was removed (i.e. (rgt - lft +1)/2).
  4. Single node insertion is done with this. The nested set model has an implied ordering of siblings which the adjacency list model does not. To insert a new node as the rightmost sibling.

BEGIN
DECLARE right_most_sibling INTEGER;

SET right_most_sibling

  • SELECT rgt FROM Personnel WHERE emp = :your_boss;

UPDATE Personnel
  SET lft = CASE WHEN lft > right_most_sibling

                 THEN lft + 2
                 ELSE lft END,
      rgt = CASE WHEN rgt >= right_most_sibling
                 THEN rgt + 2
                 ELSE rgt END

WHERE rgt >= right_most_sibling;

INSERT INTO Personnel (emp, lft, rgt)
VALUES('New Guy', right_most_sibling, (right_most_sibling + 1)) END; The actual timings are pretty good with the right indexes and a good optimizer.

--CELKO--
Joe Celko, SQL and Database Consultant

Sent via Deja.com http://www.deja.com/
Before you buy. Received on Tue May 23 2000 - 00:00:00 CEST

Original text of this message