Post

R-trees are a powerful structure for indexing geometric data. They’re used by MySQL, and Postgres uses an R-tree-like structure via GiST in PostGIS. 🧵

They function similarly to B-trees: It’s a tree structure with multiple entries at each page-aligned node. This generally keeps the trees nice and shallow, and allows for efficient lookups for millions of elements stored on-disk. It also generally only stores data values at the leaves, like B+trees.

Entries in an R-tree are bounding rectangles. At the leaves we store the minimum bounding rectangle (MBR) for each region being stored, with a reference to the full geometry stored on-disk elsewhere. The parent entry of a leaf MBR stores a bounding rectangle that fully bounds all children.

Moving up the tree, the bounding rectangles get larger and larger, up to the root node storing a small number of large bounding boxes.