hesela.devB-tree
A B-tree is a balanced multiway search-tree family that groups ordered keys into nodes and keeps leaves at a common depth.
Many keys fit in one node, allowing a page-oriented index to branch more widely than a binary search tree. Implementations differ in whether records appear in internal nodes or only at leaves; B-tree is often used as a family name. [1]
PostgreSQL B-tree indexes support equality, range predicates and ordered retrieval. An index's ordering does not establish transaction visibility or verify the stored payload; an index-only scan has additional requirements. [2] [3]
Relations
Citations
- Lehman and Yao (1981), Efficient Locking for Concurrent Operations on B-Trees, TODS 6(4), 650-670; DOI 10.1145/319628.319663
- PostgreSQL 16: Index Types, B-tree supported operations
- PostgreSQL 16: Index-Only Scans and Covering Indexes
Sources & caveats
- Family-level definition; PostgreSQL-specific capabilities are scoped to version 16.