Indexing of Spatial Data 3 3 k-d tree-early structure used for indexing in multiple dimensions. Each level of a k-d tree partitions the space into two. 2 choose one dimension for partitioning at the root level of the tree. choose another dimensions for partitioning in nodes at the next level and so on,cycling through the dimensions. In each node,approximately half of 3 3 the points stored in the sub-tree fall on one side and half on the other. The k-d-B tree extends the k- d tree to allow multiple child Partitioning stops when a node has nodes for each internal node; less than a given number of points. well-suited for secondary storage. Database System Concepts-7th Edition 24.18 ©Silberscha乜，Korth and SudarshanDatabase System Concepts - 7 24.18 ©Silberschatz, Korth and Sudarshan th Edition Indexing of Spatial Data ▪ k-d tree - early structure used for indexing in multiple dimensions. ▪ Each level of a k-d tree partitions the space into two. • choose one dimension for partitioning at the root level of the tree. • choose another dimensions for partitioning in nodes at the next level and so on, cycling through the dimensions. ▪ In each node, approximately half of the points stored in the sub-tree fall on one side and half on the other. ▪ Partitioning stops when a node has less than a given number of points. 3 1 3 2 3 3 2 ▪ The k-d-B tree extends the k￾d tree to allow multiple child nodes for each internal node; well-suited for secondary storage