I NEED R TREE ALGORITHM AND CLEAR EXPLANATION FOR THATSoluti

I NEED R- TREE ALGORITHM AND CLEAR EXPLANATION FOR THAT

Solution

R-Tree

R-trees are hierarchical data structures based on B+ trees. They are used for the dynamic organization of a set of d-dimensional geometric objects representing them by the minimum bounding d-dimensional rectangles (for simplicity, MBRs in the sequel).

Each node of the R-tree corresponds to the MBR that bounds its children. The leaves of the tree contain pointers to the database objects instead of pointers to children nodes. The nodes are implemented as disk pages.

An R-tree is a depth-balanced tree –Each node corresponds to a disk page –Leaf node: an array of leaf entries

An R-tree of order (m,M) has the following characteristics:

– Each leaf node (unless it is the root) can host up to M entries, whereas the minimum allowed number of entries is mM/2. Each entry is of the form (mbr,oid), such that mbr is the MBR that spatially contains the object and oid is the object’s identier.

– The number of entries that each internal node can store is again between mM/2 and M. Each entry is of the form (mbr,p), where p is a pointer to a child of the node and mbr is the MBR that spatially contains the MBRs contained in this child.

– The minimum allowed number of entries in the root node is 2, unless it is a leaf (in this case, it may contain zero or a single entry).

– All leaves of the R-tree are at the same level.

From the denitionoftheR-tree,itfollowsthatitisaheight-balancedtree. As mentioned, it comprises a generalization of the B+-tree structure for many dimensions. R-trees are dynamic data structures, i.e., global reorganization is not required to handle insertions or deletions.

The R-tree range search algorithm-

1. if RN is not a leaf node

2. examine each entry e of RN to nd those e.mbr that intersect Q

3. foreach such entry e call RangeSearch(e.ptr,Q)

4. else // RN is a leaf node

5. examine all entries e and nd those for which e.mbr intersects Q

6. add these entries to the answer set A

7. endif

The R-tree insertion algorithm-

Insertions in an R-tree are handled similarly to insertions in a B+-tree. In particular,theR-treeistraversedtolocateanappropriateleaftoaccommodate thenewentry.Theentryisinsertedinthefoundleafand,thenallnodeswithin the path from the root to that leaf are updated accordingly. In case the found leaf cannot accommodate the new entry because it is full (it already contains M entries), then it is split into two nodes. Splitting in R-trees is dierent from that of the B+- tree, because it considers dierent criteria.

1. Traverse the tree from root RN to the appropriate leaf. At each level, select the node, L, whose MBR will require the minimum area enlargement to cover E.mbr

2. In case of ties, select the node whose MBR has the minimum area

3. if the selected leaf L can accommodate E

4. Insert E into L

5. Update all MBRs in the path from the root to L, so that all of them cover E.mbr

6. else // L is already full

7. Let E be the set consisting of all L’s entries and the new entry E Select as seeds two entries e1,e2 E, where the distance between e1 and e2 is the maximum among all other pairs of entries from E Form two nodes, L1 and L2, where the rst contains e1 and the second e2

8. Examine the remaining members of E one by one and assign them to L1 or L2, depending on which of the MBRs of these nodes will require the minimum area enlargement so as to cover this entry

9. if a tie occurs

10. Assign the entry to the node whose MBR has the smaller area

11. endif

12. if a tie occurs again

13. Assign the entry to the node that contains the smaller number of entries

14. endif

15. if during the assignment of entries, there remain entries to be assigned and the one node contains m entries

16. Assign all the remaining entries to this node without considering the aforementioned criteria /* so that the node will contain at least m entries */

17. endif

18. Update the MBRs of nodes that are in the path from root to L, so as to cover L1 and accommodate L2
19. Perform splits at the upper levels if necessary

20. In case the root has to be split, create a new root

21. Increase the height of the tree by one

22. endif

The R-tree deletion algorithm

1. if RN is a leaf node

2. search all entries of RN to nd E.mbr

3. else // RN is an internal node

4. Find all entries of RN that cover E.mbr

5. Follow the corresponding subtrees until the leaf L that contains E is found
6. Remove E from L

7. endif

8. Call algorithm CondenseTree(L) /* Figure 1.8 */

9. if the root has only one child /* and it is not a leaf */

10. Remove the root

11. Set as new root its only child

12. endif