The original R-tree
a depth balanced tree in which each node is stored in a disk page
- leaf nodes contain pairs (mbb, oid)
- non-leaf nodes contains pairs (dr, nodeid) where
- nodeid is a pointer to a son node in the tree
- dr is the directory rectangle which covers all drs or mbbs of sons.
- additional properties
- number of pairs - so called “entries” - in all nodes (except for the root) stays between m and M (with m ? [0, M/2]
- the root node has at least 2 entries, unless it is a leaf itself
- all leaf entries are different, in the other hand drs may overlap, as mbbs do.