[prev] 57 [next]

Multi-d Trees in PostgreSQL

Up to version 8.2, PostgreSQL had an R-tree implementation

Superseded by GiST = Generalized Search Trees

GiST indexes parameterise: data type, searching, splitting

  • via seven user-defined functions (e.g. picksplit())
GiST trees have the following structural constraints:
  • every node is at least fraction f full (e.g. 0.5)
  • the root node has at least two children (unless also a leaf)
  • all leaves appear at the same level
Details: src/backend/access/gist