PostgreSQL Blink-tree Implementation
Author: ApsaraDB (Alibaba Cloud) | Source: Alibaba Cloud Blog | Published: 2026-02-27
한 줄 요약
PostgreSQL의 Blink-tree 구현은 링크 포인터와 하이 키(high key)를 통해 검색 중 락 커플링 없이 고동시성 B-tree 인덱스 운영을 가능하게 하며, 이는 MySQL InnoDB보다 세밀한 락 粒度를 제공한다.
핵심 주장/내용
- Blink-tree는 각 노드에 링크 포인터(우측 형제 노드로 이동)와 하이 키(탐색 범위 검증)를 추가
- 검색 시 락 커플링을 사용하지 않아 현재 레이어에만 래치(latch)를 보유 — InnoDB와 달리 부모-자식 래치를 동시에 보유하지 않음
- SMO(구조 변경 작업, 예: 노드 분할) 중 최대 3개 노드에만 래치 보유
- 검색과 SMO가 충돌하지 않는 이유: 분할로 노드 내용이 이동해도 하이 키를 통해 올바른 노드를 추적 가능
- InnoDB는 락 서브트리 범위 계산 복잡도 문제, PostgreSQL은 단일 노드 래치로 더 높은 동시성 달성
주요 수치 / 사실
- 검색 중 읽기 락 최대 1개만 보유
- 삽입 중 쓰기 락 최대 1개만 보유
- 삭제 중 쓰기 락 최대 2개만 보유
- 참조: Lehman-Yao, Lanin-Shasha, Bayer-Schkolnick 논문
관련 위키
Source: 원문 보기