![[assets/str_idx_btree.png|256]] - **Description**: The default and most common index type. It implements a **B-link tree** (as defined by Lehman and Yao), which allows for high concurrency by using "Right-Links" and "High Keys" to handle concurrent page splits without heavy locking. - **Data Structure**: - **Internal Nodes**: Contain (key, child-link) pairs. - **Leaf Nodes**: Contain (key, TID) pairs pointing to the heap. - **Right-Links & High-Keys**: Every page has a `bt_opaque` header containing a pointer to its right sibling and the maximum key value on the page. This allows seekers to detect if a page split occurred while they were traversing. - **Supported Operators**: `<`, `<=`, `=`, `>=`, `>`, `BETWEEN`, `IN`, `IS NULL`, `IS NOT NULL`. - **Special Features**: - **Deduplication (PG 13+)**: Stores duplicate keys in a compressed "Posting List" format, significantly reducing index size for low-cardinality columns. - **Index-Only Scans**: Can retrieve data entirely from the index if the visibility map confirms the page is all-visible. - **Metaphor**: A perfectly balanced set of nested Russian dolls, where each doll tells you exactly which smaller doll to open next until you find the prize. Internally, these dolls have secret backdoors (Right-Links) so they can pass you to the next doll even if the shelf is being cleared.