Quadtrees (Cont.) PR quadtree:stores points;space is divided based on regions,rather than on the actual set of points stored. Region quadtrees store array(raster)information. A node is a leaf node is all the array values in the region that it covers are the same.Otherwise,it is subdivided further into four children of equal area,and is therefore an internal node. Each node corresponds to a sub-array of values. The sub-arrays corresponding to leaves either contain just a single array element,or have multiple array elements,all of which have the same value. ■ Extensions of k-d trees and PR quadtrees have been proposed to index line segments and polygons Require splitting segments/polygons into pieces at partitioning boundaries Same segment/polygon may be represented at several leaf nodes Database System Concepts-7th Edition 24.20 ©Silberscha乜，Korth and SudarshanDatabase System Concepts - 7 24.20 ©Silberschatz, Korth and Sudarshan th Edition Quadtrees (Cont.) ▪ PR quadtree: stores points; space is divided based on regions, rather than on the actual set of points stored. ▪ Region quadtrees store array (raster) information. • A node is a leaf node is all the array values in the region that it covers are the same. Otherwise, it is subdivided further into four children of equal area, and is therefore an internal node. • Each node corresponds to a sub-array of values. • The sub-arrays corresponding to leaves either contain just a single array element, or have multiple array elements, all of which have the same value. ▪ Extensions of k-d trees and PR quadtrees have been proposed to index line segments and polygons • Require splitting segments/polygons into pieces at partitioning boundaries ▪ Same segment/polygon may be represented at several leaf nodes