- **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**: - **The Page Header (`BTPageOpaqueData`)**: Every 8KB page contains an "opaque" tail section. This defines the page's role (`BTP_ROOT`, `BTP_LEAF`, `BTP_INTERNAL`) and stores the **Right-Link**—a pointer to the next sibling page. - **Internal Nodes & Pivot Tuples**: Instead of full entries, internal pages store **Pivot Tuples**. These are often truncated keys that serve as signposts. For example, if a child page contains keys from "Apple" to "Banana," the pivot might just store "B" to save space. This increases the **Fan-out** (branching factor), ensuring the tree remains shallow (typically 3-5 levels). - **Leaf Nodes**: Contain the actual `(key, TID)` pairs (`IndexTupleData`). Leaf pages are linked together in a doubly-linked list via Right-Links, enabling fast sequential range scans. - **High-Keys**: Every page except the rightmost one in a level stores a **High Key**. This is the upper bound of all keys on that page. If a seeker finds a value greater than the High Key, they know a concurrent **Page Split** occurred and follow the Right-Link to find the newly moved data. - **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.