PostGIS adds geometry types and spatial operators to PostgreSQL, but the real
performance win comes from its GiST-based R-tree index. Instead of
storing rows in the order they were inserted, the index groups nearby geometries into
nested bounding boxes, so a query like WHERE geom && box can skip
entire branches of the tree that can't possibly overlap the search box.
PostGIS's spatial index is built on PostgreSQL's generic GiST (Generalized Search Tree) framework — the same extensible index machinery also used for full-text search and range types — with R-tree-style bounding-box splitting rules registered specifically for geometry columns.
A 3D map scattered with data points sits under a spatial R-tree/GiST index grid. Draw a bounding-box query and watch the index highlight only the cells — and the rows inside them — it actually needs to search.
PostGIS's GiST index groups geometries into bounding boxes so a query can discard whole branches of the tree at once. Amber points are candidates inside searched cells; green points are exact matches inside the query box; grey points were never touched.
Move the query box with the X/Z sliders and resize it, then change the index granularity to see the searched-cell count shrink or grow. Hit "Compare full table scan" to see what scanning every row without an index looks like.
PostGIS is built on PostgreSQL's generic GiST framework — the same indexing machinery that also powers full-text search — with bounding-box splitting rules registered specifically for geometry columns.