K-D-B Tree.ppt

Jaruloj Chongstitvatana 2006 K-D-B Tree K-D-B Tree Multidimensional Index Characteristics Multi-way branch Height-balanced tree Repeatedly divide area of the domain into disjoint sub-area A node in a tree corresponds to a (set of consecutive) disk page(s) Example of Data Records Table (stdntID, courseID, grade, year, smstr) Table (accID, branchID, saving, name, addr) Table (custID, age, gender, occupation, salary, children, promotion, since) Nodes = Pages Region pages Contain a set of region, ptr. to page Internal nodes Point pages Contain a set of point, ptr. to data record Leaf nodes Region Pages Point Pages Example Search Insert Split Split a region r with page id p along xi If r is on the right/page of xi then put r, p in the right/left page. Otherwise; For each children pc of p , split pc along xi Split r along xi into rleft and rright. Create 2 new pages with page id pleft and pright. Move children of p in the left region into pleft and children in the right region into pright. Return rleft, pleft and rright, pright . Split: Example Split: Example How to find split axis Cyclic: x - y - x - y - … Priority: x - x - y - x - x - y - … Possible one Insert Insert a record with point a and location l in a tree with root r If r is NIL, then create a point page p and insert the record with a,l in p and return p. Otherwise; Search for a in the tree with root r until a point page, say p, is reached. Insert the record in the point page p. Insert (cont’d) Insert a record with point a and location l in a tree with root r If the point page p is overflowed, then find an appropriate axis to split p into pleft and pright. If p is not the root, then change to p and pleft, and insert pright into the parent of p. If p is the root, then create a new root node with two children of pleft and pright. Insert: Example Insert: Example Insert: Example Insert: Example Insert: Example Delete Simple, if storage utilization is ignored. Otherwise, an underfull page should