Week 09 Lecture (25)

Insertion of an object R occurs as follows:

start at root, look for children that completely contain R
if no child completely contains R, choose one of the children and expand its boundaries so that it does contain R
if several children contain R, choose one and proceed to child
repeat above containment search in children of current node
once we reach data page, insert R if there is room
if no room in data page, replace by two data pages
partition existing objects between two data pages
update node pointing to data pages
(may cause B-tree-like propagation of node changes up into tree)

Note that R may be a point or a polygon.