R树是用来做空间数据存储的树状数据结构,在现实生活中R树可以用来存储地图上的空间信息,例如餐馆地址,或者地图上用来构造街道,建筑,湖泊边缘和海岸线的多边形.然后可以用它来回答"查找距离我2千米以内的博物馆","检索距离我2千米以内的所有路段"(然后显示在导航系统中)或者"查找(直线距离)最近的加油站"这类问题.

R树的核心思想是聚合距离相近的节点并在树结构的上一层将其表示为这些节点的最小外接矩形,这个最小外接矩形就成为上一层的一个节点

• R树每个节点存储多条数据,数据条数不超过一个事先定义的最大值,一般会多于最小值
• 非叶子节点上的每一条数据由指向子节点的标识符和该子节点的外接矩形组成
• 叶子节点则存储每个对象需要的数据,一般是一个关于所有数据最小外接矩形和指向数据的标识符

输入是一个搜索矩形

插入节点时,算法从树的根节点开始递归地向下遍历.检查当前节点中所有外接矩形,并启发式地选择在哪个子节点中插入.

插入算法在树的每一层都要决定把新的数据插入到哪个子树中.如果只有一个外接矩形包含新数据,那么很容易选择.但如果有多个外接矩形包含新数据,或者所有外界矩形都不包含新数据,那么选择算法会极大地影响R树的性能.

经典R树的实现会把数据插入到外接矩形需要增长面积最小的那个子树.而更进一步的R*树则使用了一种混合的启发式算法.

从一个节点中删除一条数据可能会导致算法需要更新它的父节点的外接矩形.但是当一个节点中的数据不足时,它不会和兄弟节点重新平衡.这个节点会被直接删除,它的子节点(可能是子树,不一定是叶子节点)会被重新插入.如果在这个过程中根节点只剩下一个子节点,可以把根节点删除,树的高度降低.