Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL
Help

Chapter 5: Frequent Insertion Trees > 5.1 The Data Type of (lft, rgt) - Pg. 125

5 . 1 T h e D a t a Ty p e o f ( l f t , r g t ) 113 Personnel_Orgchart emp_id `Albert' `Bert' `Chuck' `Donna' `Eddie' `Fred' lft 100 200 400 500 700 900 rgt 1200 300 1100 600 800 1000 The term spread will mean the value of (rgt - lft) for one node, and the term gap will mean the distance between adjacent siblings under the same Parent node. To insert someone under `Bert', say `Betty', you look at the size of Bert's range (300 - 200 = 100) and pack the newcomer to the leftmost position, while leaving her node wide enough for more subordinates. One way of doing this is: INSERT INTO Personnel_Orgchart VALUES ('Betty', 201, 210); -- spread of 9 To insert someone under `Betty', you look at the size of Betty's range (210 - 201) and pack from the left: INSERT INTO Personnel_Orgchart VALUES ('Bobby', 202, 203); --spread of 1 The new rows should be inserted in the table without locking the table for an update on multiple rows. Assuming you have a 32-bit integer, you can have a depth of 9 or 10 levels before you have to reorganize the tree. There are two tricks in this approach. First you must decide on the data type to use for the (lft, rgt) pairs and then get a formula for the spread size you want to use. You will see shortly that my simple multiplication is not the best way to achieve the goal. 5.1 The Data Type of (lft, rgt) The (lft, rgt) pairs will obviously be an exact numeric data type. Because the goal is to get as wide a numeric range as you can, SMALLINT or TINYINT is obviously not going to be considered. Here are your three choices. 5.1.1 Exploiting the Full Range of Integers If you do not mind negative numbers, you can use the full range of the integers, something like this on a typical 32-bit machine: INSERT INTO Tree VALUES ('root', -4294967295, 4294967296);