Re: insertion and deletion in the nested set model
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? <<
- organizational structures usually change slower than the membership of the organization.
- The tree structure is in its own table, and the rows are small.
- 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).
- 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