# Exploring SP-GiST and BRIN indexes visually using pg\_hexedit

DevFeed: [Exploring SP-GiST and BRIN indexes visually using pg\_hexedit](<https://devfeed.tech/articles/exploring-sp-gist-and-brin-indexes-visually-using-pg-hexedit-33660.md>)

Original publisher: [Read original article](<https://pgeoghegan.blogspot.com/2018/01/exploring-sp-gist-and-brin-indexes.html>)

Author: Peter Geoghegan (noreply@blogger.com)

Published: 2018-01-08T22:06:00Z

Content type: article

Language: en

Sources: [Peter Geoghegan's blog](<https://devfeed.tech/sources/peter-geoghegan-s-blog.md>)

Topics: [PostgreSQL](<https://devfeed.tech/topics/postgresql.md>), [Database](<https://devfeed.tech/topics/database.md>), [Data structures](<https://devfeed.tech/topics/data-structures.md>)

Tags: [database](<https://devfeed.tech/tags/database.md>), [experimental](<https://devfeed.tech/tags/experimental.md>), [exploring](<https://devfeed.tech/tags/exploring.md>), [index](<https://devfeed.tech/tags/index.md>), [internals](<https://devfeed.tech/tags/internals.md>), [pageinspect](<https://devfeed.tech/tags/pageinspect.md>), [pg-hexedit](<https://devfeed.tech/tags/pg-hexedit.md>), [postgresql](<https://devfeed.tech/tags/postgresql.md>), [property](<https://devfeed.tech/tags/property.md>), [storage](<https://devfeed.tech/tags/storage.md>), [structure](<https://devfeed.tech/tags/structure.md>)

## AI overview

This article examines the visual representation of PostgreSQL SP-GiST and BRIN indexes using pg_hexedit. It explains SP-GiST's support for unbalanced tree structures and adaptive mapping of tree nodes to disk blocks, then describes BRIN's block-range summaries and in-place index-tuple updates.

## Source excerpt

Support for both BRIN and SP-GiST access methods was recently added to pg_hexedit, the experimental hex editor framework for PostgreSQL relation files. These were the final access methods among the standard Postgres index access methods that required support. SP-GiST (Space-Partitioned GiST) Beginning of an SP-GiST leaf page SP-GiST is unique among index access methods whose index structure is tree-like, in that it supports tree structures that are unbalanced. SP-GiST operator classes exist that support k-d trees, quadtrees, and suffix trees. These structures are traditionally only suited to a fully in-memory representation, with dynamically-allocated nodes that contain a small number of simple pointers (byte addresses) pointing to other nodes. SP-GiST presents a generalized interface through which all of these space-partitioned trees can be constructed for a given datatype, in a way that minimizes disk seeks (PDF) and works well with block-orientated storage. Essentially, SP-GiST maps tree nodes onto disk blocks in an adaptive fashion, rather than simply having a block directly correspond to a tree node, as happens with other access methods. There are particularly intricate data structures needed to support all of this. Space utilization can be an issue with SP-GiST indexes, though that's probably very workload dependent. This is something that pg_hexedit can be effective at representing visually. SP-GiST is a good example of the PostgreSQL community implementing a concept that comes directly from state of the art database research (PDF). I suspect that we have yet to fully realize the benefit of SP-GiST for specific application domains, due to a simple lack of awareness among users and potential users that work in those domains. Perhaps this enhancement can contribute in some small way towards a better understanding of what is possible. BRIN (Block Range Index) BRIN "revmap" page The structure of BRIN indexes is not at all tree-like. BRIN works by summarizing the