R-Tree

Intro

Similar to B-Tree, R-Tree is also a balanced search tree.

Search algorithms such at intersection, containment, nearest neighbor are still similar to other tree structures.

The major difficulty is how to build a balanced R-Tree. We definitely want the tree to be balanced but each node (rectangle) should not cover too much empty space and rectangles within it should not overlap too much.

Insertion

Recursively search to the root level, insert, if full, split, then recursively insert & split to the root level.

Reference

Wikipedia R-tree