B-trees in PostgreSQL
PostgreSQL implements ≅ Lehman/Yao-style B-trees
- variant that works effectively in high-concurrency environments.
B-tree implementation: backend/access/nbtree
-
README ... comprehensive description of methods
-
nbtree.c ... interface functions (for iterators)
-
nbtsearch.c ... traverse index to find key value
-
nbtinsert.c ... add new entry to B-tree index
Notes:
- stores all instances of equal keys (dense index)
- avoids splitting by scanning right if key = max(key) in page
- common insert case: new key is max(key) overall; handled efficiently
|