[prev] 33 [next]

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