Division of Space by Quadtrees Quadtrees ■ Each node of a quadtree is associated with a rectangular region of space; the top node is associated with the entire target space. Each non-leaf nodes divides its region into four equal sized quadrants correspondingly each such node has four child nodes corresponding to the four quadrants and so on Leaf nodes have between zero and some fixed maximum number of points (set to 1 in example). Database System Concepts-7th Edition 24.19 @Silberschatz,Korth and SudarshanDatabase System Concepts - 7 24.19 ©Silberschatz, Korth and Sudarshan th Edition Division of Space by Quadtrees Quadtrees ▪ Each node of a quadtree is associated with a rectangular region of space; the top node is associated with the entire target space. ▪ Each non-leaf nodes divides its region into four equal sized quadrants • correspondingly each such node has four child nodes corresponding to the four quadrants and so on ▪ Leaf nodes have between zero and some fixed maximum number of points (set to 1 in example)