CodeParkAn index is a separate data structure that maps column values to row locations. With it, the database can find matching rows without reading the whole table. The price is extra storage, plus extra work on every insert, update and delete.
PostgreSQL's default index type is the B-tree. It is a balanced tree, which means every path from the top to the bottom has the same length. It has two kinds of pages:
- Leaf pages hold the indexed values in sorted order. Each value has a pointer to its row in the table's heap (the main table storage). This pointer is called a TID (tuple ID).
- Inner pages hold separator keys. These keys guide the search down to the right leaf.
The tree is shallow, so a lookup touches only a few pages. The cost is roughly O(log n).
Each leaf page is linked to its neighbours. After the database finds a start point, it can walk forward or backward along the leaves. This is why a B-tree handles =, <, > and BETWEEN. It can also return rows already sorted for ORDER BY.
- An index is a separate structure that maps column values to row locations.
- A B-tree is a balanced tree with sorted leaves, so a lookup reads only a few pages.
- Linked leaf pages allow range scans and already-sorted output.
- Every index costs storage and adds work to every write.
Read more
- Indexes (https://www.postgresql.org/docs/current/indexes.html)postgresql.org
- Use The Index, Luke (https://use-the-index-luke.com/)use-the-index-luke.com