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. 🧵

Ben

@benjdd.com

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.

11/1/26, 1:33 pm0 reposts0 likes

Ben

@benjdd.com

11 Jan

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.

Ben

@benjdd.com

11 Jan

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

Ben

@benjdd.com

11 Jan

A key difference from B-trees: searching for a single rectangle may require searching multiple tree paths! In the ideal case, B-trees offer O(log n) search performance, but due to possible overlaps the worst-case performance is actually O(n).