(KO) PostgreSQL B-Tree (nbtree) — Lehman-Yao 동시성, 페이지 분할, 인덱스 튜플 삭제

목차

• 학술적 배경
• DBMS 공통 설계 패턴
• PostgreSQL의 구현
• 소스 코드 가이드
• 소스 검증 (2026-06-05 기준)
• PostgreSQL 너머 — 비교 설계와 연구 프론티어
• 출처

학술적 배경

B-트리는 거의 모든 관계형 엔진이 기본 디스크 인덱스로 선택하는 구조다. 이유는 구조 자체에 있다. B-트리는 균형 잡힌 고-팬아웃(high fan-out) 탐색 트리로, 모든 리프가 동일한 깊이에 있기 때문에 조회·삽입·범위 스캔에 O(log_F N) 페이지 읽기가 필요하다. 여기서 팬아웃 F가 충분히 크면 십억 행 테이블도 트리 높이가 서너 단계에 불과하다. Comer의 고전적 조사 논문 The Ubiquitous B-Tree (Comer 1979; dbms-papers/btree.md 수록)와 Database System Concepts (Silberschatz 7판 14장 “Indexing”)이 이 자료구조를 정식화한다. 내부 페이지는 자식을 가리키는 포인터(다운링크, downlink)와 *구분 키(separator key)*를 번갈아 담고, 리프 페이지는 실제 키 항목을 담는다. 꽉 찬 페이지는 둘로 분할하고 새 구분 키를 부모로 전파하는데, 이 과정이 루트까지 재귀하면 트리 높이가 하나 늘어난다. PostgreSQL을 포함한 대부분의 엔진은 B+-트리 변형을 사용한다. 모든 데이터 항목이 리프에 있고, 내부 페이지는 탐색 키만 보유하며, 리프들은 연결 리스트로 이어지므로 범위 스캔이 트리를 다시 올라갈 필요가 없다.

교과서의 B-트리는 단일 스레드 자료구조다. 어려운 문제는 교과서가 대부분 얼버무리는 동시성이다. 동시 B-트리 구현이라면 반드시 해결해야 할 설계 선택지가 두 가지 있다.

1. 읽기 트랜잭션이 동시 쓰기 트랜잭션에 의해 깨지지 않으려면 어떻게 해야 하는가. 가장 단순한 답은 래치 연결(latch-crabbing)이다. 하강 중인 검색이 자식을 잠그기 전까지 부모 읽기 잠금을 유지해, 분할하려는 쓰기가 읽기 중인 자식을 건드리지 못하게 한다. 정확하지만 동시성을 압박한다. 모든 읽기가 경로 전체에서 쓰기와 직렬화되고, 모든 연산이 통과하는 루트가 병목이 된다.

2. 분할 결과를 어떻게 원자적으로 공개하는가. 분할은 세 페이지를 변경한다. 분할 대상 페이지, 새 오른쪽 형제 페이지, 다운링크를 받을 부모 페이지가 그것이다. 읽기 트랜잭션이 부모의 다운링크가 생기기 전에 새 오른쪽 페이지를 볼 수 있다면, 단순한 설계는 세 페이지 모두에 잠금을 걸거나 키 이동을 놓칠 위험을 감수해야 한다.

이 두 문제에 대한 결정적 답이 Lehman & Yao 1981, “Efficient Locking for Concurrent Operations on B-Trees” (TODS; src/backend/access/nbtree/README 맨 위에 인용되어 있으며, 논문 원문은 dbms-papers/btree.md에 수록)다. 핵심 통찰은 두 필드를 모든 페이지에 추가해 트리를 *동시성 하에서 자가 복구(self-repairing)*하게 만드는 것이다.

• right-link — 같은 레벨에서 바로 오른쪽 형제 페이지를 가리키는 포인터. 각 레벨이 왼쪽에서 오른쪽으로 단방향 연결 리스트가 된다.
• high key — 해당 페이지에 합법적으로 존재할 수 있는 모든 키의 상한선.

이 두 추가 사항 덕분에 분할은 국소적이고 왼쪽-오른쪽 방향의 연산이 된다. 새 오른쪽 페이지가 연결되는 순간 결과가 보이며, 부모의 다운링크가 없어도 된다. 검색이 분할된 페이지에 도달하면 검색 키가 해당 페이지의 high key를 초과한다는 사실을 알아채고 “원하는 키가 오른쪽으로 이동했다”고 판단해 right-link를 따른다. 부모 잠금도, 루트 잠금도, 레벨 사이의 래치 연결도 필요 없다. 트리는 한 번에 최대 페이지 하나만 잠근 채로 검색 가능하다. 이 구조를 “B-link 트리”라 부르며, 이것이 사실상 모든 현대 동시 B-트리의 기반이다.

함께 참고하는 논문이 **Lanin & Shasha 1986, “A Symmetric Concurrent B-Tree Algorithm”**이다. Lehman & Yao가 명세를 불충분하게 남겨 둔 삭제 측면을 보완한다. 빈 페이지를 진행 중인 검색을 깨뜨리지 않고 트리에서 제거하는 방법이 핵심이다. 두 가지 아이디어가 PostgreSQL README에 직계 출처로 명시된다. “drain 기법”(삭제된 페이지는 동시 연산이 더 이상 참조할 수 없을 때까지 묘비로 남는다)과 “fast root”(단일 자식만 남은 퇴화 레벨을 건너뛴다)가 그것이다.

L&Y를 채택하면 두 가지 구현 선택이 남는다. 이 선택들이 이 문서의 나머지를 조직한다.

1. “오른쪽으로 이동해 복구”가 정확히 얼마나 비용이 들고 언제 발동되는가. 검색, 분할 후 부모를 재탐색하는 삽입, 역방향 스캔, 페이지 분할이 발생하는 중에 물리적 순서로 스캔하는 VACUUM 각각의 경우를 포함한다.
2. 여러 페이지를 변경하는 연산(분할, 페이지 삭제)을 어떻게 단일 페이지 단위 원자적 WAL 액션으로 분해해 충돌 안전(crash-safe)하게 만드는가. 어떤 중간 상태도 유효하고 검색 가능한 L&Y 트리여야 한다.

DBMS 공통 설계 패턴

동시 B-트리를 구축하는 엔지니어들은 교과서가 명시하지 않는 공통 패턴으로 수렴한다. 이 관행들을 먼저 이름 붙여 두면, 다음 절의 PostgreSQL 전용 심볼들이 공유 설계 공간 안에서 내린 선택으로 읽힌다.

B-link 트리와 “오른쪽으로 이동해 복구”

1990년 이후 출시된 고-동시성 B-트리는 거의 모두 고전적 lock-coupled B-트리가 아니라 Lehman-Yao B-link 트리의 변형이다. 공통 패턴은 이렇다. 각 레벨은 오른쪽으로 연결된 리스트다. 가장 오른쪽이 아닌 페이지는 high key를 갖는다. 내려가다 낡은 페이지에 도착한 연산은 high key가 “키가 이 페이지에 속한다”고 말할 때까지 오른쪽으로 걷는다. 엔진마다 차이는 복구의 세부 사항(오른쪽 이동 허용 횟수, 읽기 잠금 유무)과 삭제(가장 어려운 부분)에 있다. 핵심 아이디어는 공통이다.

래치(Latch)와 잠금(Lock) — B-트리 페이지 위의 두 가지 동시성 메커니즘

B-트리 페이지는 구현자들이 엄격히 분리하는 두 가지 동시성 메커니즘의 영향을 받는다.

• 래치(Latch) (PostgreSQL에서는 버퍼 콘텐츠 잠금 / LWLock)는 수명이 짧다. 백엔드가 한 페이지의 바이트를 물리적으로 읽거나 쓰는 동안만 보유한다. I/O 대기나 교착 탐지 가능한 대기에 걸린 채로는 잡지 않는다. 페이지 이미지의 물리적 일관성을 보호한다.
• 잠금(Lock) (SQL 수준의 heavyweight lock manager 및 SERIALIZABLE용 predicate lock)은 논리적 데이터베이스 객체를 보호하고 트랜잭션 끝까지 유지된다. B-트리 검색은 읽는 인덱스 페이지에 heavyweight lock을 전혀 걸지 않는다.

이 분리가 의미를 갖는 것은 L&Y 설계 덕분이다. “오른쪽으로 이동해 복구”로 검색이 한 번에 페이지 하나 이상의 래치를 잡을 필요가 없으므로, 인덱스는 거의 전적으로 짧은 래치로 조율된다. 트랜잭션 기간 잠금은 인덱스가 가리키는 힙 튜플로 밀려난다. (PostgreSQL의 페이지 래칭은 postgres-buffer-manager.md에, heavyweight lock 테이블은 postgres-lock-manager.md에 있다.)

원자적이고 복구 가능한 단계로 분해된 분할

분할은 여러 페이지에 걸쳐 있지만 WAL 레코드는 레코드당 원자적이다. 따라서 구현자들은 분할을 각각 유효한 트리를 남기는 단일 레코드 액션의 시퀀스로 분해한다. 표준 분해 방식은 다음과 같다. (1) 새 오른쪽 페이지를 원자적으로 생성·연결하고 기존 페이지를 축소하면서, “오른쪽 형제의 부모 다운링크가 아직 없다”는 플래그를 세운다. 그 다음 (2) 원자적으로 부모에 다운링크를 올리고 플래그를 지운다. (1)과 (2) 사이에 충돌이 발생해도 트리는 완전히 검색 가능하다. right-link가 독자들을 틈새 너머로 안내하기 때문이다. 이후 연산이 지연 방식으로 복구한다. 이것이 “분할은 right-link가 설정되는 순간 국소적으로 완료된다”는 L&Y 속성을 WAL로 표현한 것이다.

인덱스 항목의 지연·다계층 가비지 컬렉션

no-overwrite MVCC 엔진(PostgreSQL, 그리고 대략 Oracle의 undo 모델)에서는 행이 갱신되거나 삭제될 때마다 죽은 인덱스 튜플이 생긴다. 인덱스가 이제 죽은 힙 튜플 버전을 여전히 가리키기 때문이다. 회수는 비용 순서대로 나열되는 다계층 구조다.

1. 힌트 비트 마킹 — 스캔이 힙을 방문해 튜플이 모두에게 죽었음을 발견하면 인덱스 항목에 저렴한 “알려진 죽음” 비트(shared 래치 하에서 설정, 힌트 비트와 유사)를 남긴다. 이후 스캔이 건너뛸 수 있다.
2. 페이지 내 물리 삭제 — 분할 직전에 엔진이 알려진 죽음 항목들을 물리적으로 제거해 트리를 키우지 않고 공간을 확보한다.
3. vacuum 프로세스의 대량 삭제 — 백그라운드 스위프가 회수 중인 힙 튜플을 가리키는 모든 인덱스 항목을 제거한다.
4. 빈 페이지 회수 — 모든 항목이 사라진 페이지를 트리에서 끊어 재활용한다.

각 계층은 그 위 계층의 안전망이다. 모든 계층에서 지켜야 할 MVCC 정확성 제약이 있다. TID(heap tuple identifier)는 어떤 스캔이 낡은 인덱스 포인터를 따라올 가능성이 남아 있는 한 재활용(다른 새 행에 재사용)하면 안 된다. 이것이 “동시 TID 재활용” 위험이다.

팬아웃을 위한 suffix 절단과 중복 제거

두 가지 공간 최적화가 반복해서 등장한다. **Suffix 절단(suffix truncation)**은 분할 시 부모에 쓰는 구분 키를 왼쪽과 오른쪽을 구분하는 최단 접두사로 줄인다(Bayer & Unterauer의 prefix B-트리). 내부 페이지를 밀도 있게 유지하고 트리를 얕게 만든다. **중복 제거(deduplication)**는 같은 리프 항목을 여러 개 담는 대신 posting list(TID 배열) 하나로 접는다. 작은 디코드 비용을 치르고 저-카디널리티 컬럼에서 큰 공간 절약을 얻는다.

Theory ↔ PostgreSQL 대응표

이론 / 관행	PostgreSQL 이름 (nbtree)
B-link 트리 right-link	BTPageOpaqueData.btpo_next (btpo_prev 왼쪽-링크는 PG 추가)
High key (페이지 키 공간 상한선)	비-가장오른쪽 페이지의 P_HIKEY 항목 (오프셋 1)
검색 시 “오른쪽으로 이동해 복구”	_bt_moveright (P_HIKEY와 검색 키를 비교)
래치 연결 하강 (자식 잠금, 부모 해제)	_bt_search 루프 via _bt_relandgetbuf
분할 1단계 (오른쪽 페이지 연결, 왼쪽 플래그 설정)	_bt_split이 BTP_INCOMPLETE_SPLIT 설정
분할 2단계 (다운링크 올리기, 플래그 지우기)	_bt_insert_parent → _bt_insertonpg
부모 다운링크 지연 복구	_bt_finish_split / _bt_getstackbuf
루트 분할 (L&Y가 명세하지 않음)	_bt_newlevel + metapage btm_root 갱신
Fast root (Lanin & Shasha)	BTMetaPageData.btm_fastroot / btm_fastlevel
힌트 비트 “알려진 죽음” 마킹	LP_DEAD 항목 플래그, _bt_killitems / unique 검사에서 설정
분할 전 페이지 내 삭제	_bt_delete_or_dedup_one_page, _bt_simpledel_pass, _bt_bottomupdel_pass
vacuum에 의한 대량 삭제	btbulkdelete → btvacuumscan → btvacuumpage
vacuum/분할 경쟁 감지기	BTCycleId (btpo_cycleid) + BTP_SPLIT_END
두 단계 빈 페이지 삭제	_bt_pagedel → _bt_mark_page_halfdead → _bt_unlink_halfdead_page (BTP_HALF_DEAD → BTP_DELETED)
“drain 기법” 지연 재활용	BTPageIsRecyclable + BTDeletedPageData.safexid + _bt_pendingfsm_*
Suffix 절단	_bt_truncate (_bt_split에서 호출)
중복 제거 / posting list	_bt_dedup_pass, BTreeTupleIsPosting, BT_IS_POSTING
AM 디스패치 테이블	bthandler가 IndexAmRoutine 반환 (postgres-index-am.md 참조)

PostgreSQL의 구현

PostgreSQL의 src/backend/access/nbtree/는 README 표현대로 “Lehman and Yao의 고-동시성 B-트리 관리 알고리즘의 올바른 구현”이며, “Lanin and Shasha가 기술한 삭제 논리의 단순화된 버전”을 포함한다. 현재 온디스크 버전은 **BTREE_VERSION 4**다. 모든 데이터 항목이 리프에 있고, 리프는 양방향으로 연결된다. L&Y는 right-link만 요구하지만 PostgreSQL은 역방향 스캔을 위해 left-link를 추가했다. 결정적으로 버전 4부터 heap TID가 타이브레이커(tiebreaker) 키 컬럼이 되어 모든 항목이 해당 레벨에서 물리적으로 유일하다. 이 점이 L&Y 서브트리 불변식의 엄격-부등식 형태를 사용할 수 있게 한다.

페이지 레이아웃과 L&Y 불변식

모든 nbtree 페이지는 끝에 “특수 영역(special area)“을 예약하고 여기에 BTPageOpaqueData를 저장한다. L&Y 추가 사항이 사는 곳이다.

// BTPageOpaqueData — src/include/access/nbtree.h
typedef struct BTPageOpaqueData
{
    BlockNumber btpo_prev;      /* left sibling, or P_NONE if leftmost */
    BlockNumber btpo_next;      /* right sibling, or P_NONE if rightmost */
    uint32      btpo_level;     /* tree level --- zero for leaf pages */
    uint16      btpo_flags;     /* flag bits, see below */
    BTCycleId   btpo_cycleid;   /* vacuum cycle ID of latest split */
} BTPageOpaqueData;

btpo_next가 L&Y의 right-link이고, btpo_prev는 PostgreSQL이 추가한 left-link다. btpo_level은 리프 레벨을 0으로 시작해 위로 센다. 따라서 루트를 분할해도 기존 페이지의 번호는 바뀌지 않는다. 플래그 비트들이 페이지 상태를 나타낸다.

// btpo_flags 비트 — src/include/access/nbtree.h
#define BTP_LEAF        (1 << 0)  /* leaf page, i.e. not internal page */
#define BTP_ROOT        (1 << 1)  /* root page (has no parent) */
#define BTP_DELETED     (1 << 2)  /* page has been deleted from tree */
#define BTP_META        (1 << 3)  /* meta-page */
#define BTP_HALF_DEAD   (1 << 4)  /* empty, but still in tree */
#define BTP_SPLIT_END   (1 << 5)  /* rightmost page of split group */
#define BTP_HAS_GARBAGE (1 << 6)  /* page has LP_DEAD tuples (deprecated) */
#define BTP_INCOMPLETE_SPLIT (1 << 7)  /* right sibling's downlink is missing */
#define BTP_HAS_FULLXID (1 << 8)  /* contains BTDeletedPageData */

High key는 별도의 필드가 아니다. 페이지의 첫 번째 항목이 high key다. 가장 오른쪽이 아닌 페이지에서는 항목 1(P_HIKEY)이 high key를 담고 실제 데이터는 항목 2(P_FIRSTKEY)부터 시작한다. 가장 오른쪽 페이지에는 high key가 없다. 키 공간 상한이 묵시적으로 +∞이므로 데이터가 항목 1부터 시작한다.

// high key 배치 매크로 — src/include/access/nbtree.h
#define P_HIKEY             ((OffsetNumber) 1)
#define P_FIRSTKEY          ((OffsetNumber) 2)
#define P_FIRSTDATAKEY(opaque)  (P_RIGHTMOST(opaque) ? P_HIKEY : P_FIRSTKEY)

flowchart LR
  subgraph L0["리프 레벨 (btpo_level = 0)"]
    direction LR
    P1["리프 A\nhigh key = k1\n[항목 < k1]"]
    P2["리프 B\nhigh key = k2\n[k1 <= 항목 < k2]"]
    P3["리프 C (가장 오른쪽)\nhigh key 없음 (+inf)\n[항목 >= k2]"]
  end
  P1 -- "btpo_next (right-link)" --> P2
  P2 -- "btpo_next" --> P3
  P2 -- "btpo_prev (left-link)" --> P1
  P3 -- "btpo_prev" --> P2
  ROOT["내부 루트 (btpo_level = 1)\n다운링크 + 구분 키"] --> P1
  ROOT --> P2
  ROOT --> P3
  META["메타 페이지 (블록 0)\nbtm_root, btm_fastroot"] -.-> ROOT

Figure 1 — PostgreSQL이 저장하는 L&Y B-link 트리. 각 레벨은 양방향 연결 리스트다. btpo_next right-link는 L&Y 요구 사항이고, btpo_prev left-link는 역방향 스캔을 위해 PostgreSQL이 추가했다. 가장 오른쪽이 아닌 페이지의 high key(P_HIKEY, 항목 1)는 해당 페이지의 키 공간 상한을 나타낸다. 가장 오른쪽 페이지는 high key를 생략한다(묵시적 +∞). 블록 0의 메타 페이지는 참 루트와 “fast root” 모두를 가리킨다. 부모를 읽은 후 분할된 페이지에 도달한 검색은 현재 페이지 위로 잠금 없이 btpo_next를 따라 복구한다.

high key에 대한 헤더 주석이 알고리즘 전체가 의존하는 불변식을 명시한다.

// nbtree.h — high key 불변식 (주석)
//  The high key on a page is required to be greater than or equal to any
//  other key that appears on the page.  If we find ourselves trying to
//  insert a key that is strictly > high key, we know we need to move right
//  (this should only happen if the page was split since we examined the
//  parent page).

검색 하강: 래치 연결로 내려가고, 오른쪽으로 이동해 복구

_bt_search는 루트에서 시작해 래치 연결로 하강한다. 현재 페이지에 읽기 잠금을 따라갈 다운링크를 찾을 때까지만 유지하고, _bt_relandgetbuf로 자식의 잠금과 원자적으로 교환한다. 각 레벨에서 먼저 _bt_moveright를 호출해 부모의 다운링크를 읽은 후 페이지가 분할된 경우를 처리한다.

// _bt_search — src/backend/access/nbtree/nbtsearch.c (condensed)
*bufP = _bt_getroot(rel, heaprel, access);
/* ... */
for (;;)
{
    /* Race -- the page we grabbed may have split since we read its
     * downlink in its parent.  If so, move right to its new sibling. */
    *bufP = _bt_moveright(rel, heaprel, key, *bufP, (access == BT_WRITE),
                          stack_in, page_access);
    page = BufferGetPage(*bufP);
    opaque = BTPageGetOpaque(page);
    if (P_ISLEAF(opaque))
        break;                          /* found the leaf */

    offnum = _bt_binsrch(rel, key, *bufP);   /* pick the downlink */
    itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
    child = BTreeTupleGetDownLink(itup);
    /* ... push (blkno, offnum) on the descent stack ... */
    /* drop the read lock on the page, then acquire one on its child */
    *bufP = _bt_relandgetbuf(rel, *bufP, child, page_access);
    stack_in = new_stack;
}

복구 단계가 _bt_moveright다. L&Y 읽기 프로토콜 전체가 이 루프에 있다. 검색 키를 페이지의 high key(P_HIKEY)와 비교해, 키가 high key 이상이면 페이지가 분할된 것이므로 오른쪽으로 한 칸 이동한다.

// _bt_moveright — src/backend/access/nbtree/nbtsearch.c (condensed)
cmpval = key->nextkey ? 0 : 1;
for (;;)
{
    page = BufferGetPage(buf);
    opaque = BTPageGetOpaque(page);
    if (P_RIGHTMOST(opaque))
        break;                          /* no sibling; high key is +inf */

    if (forupdate && P_INCOMPLETE_SPLIT(opaque))
        /* finish a split we ran into while locking for write ... */;

    if (P_IGNORE(opaque) || _bt_compare(rel, key, page, P_HIKEY) >= cmpval)
    {
        /* step right one page */
        buf = _bt_relandgetbuf(rel, buf, opaque->btpo_next, access);
        continue;
    }
    else
        break;                          /* key belongs on this page */
}

두 가지를 읽을 수 있다. 첫째, 페이지가 여러 번 분할됐을 수 있으므로 루프가 “필요한 만큼” 오른쪽으로 이동한다. 둘째, P_IGNORE(삭제 중이거나 half-dead 상태인 페이지)도 오른쪽 이동을 강제한다. 삭제 중인 페이지에 도달한 검색이 동시 분할을 만난 것과 동일하게 복구되는 것이다. 이 통합 덕분에 페이지 삭제가 검색을 차단하지 않고도 안전하게 이루어진다.

실제 키 비교는 _bt_compare다. 스캔키 속성을 순서대로 비교한 뒤 heap-TID 타이브레이커를 사용하는 3방향 비교기다. L&Y 불변식이 작동하게 만드는 두 규칙 — 내부 페이지의 첫 번째 데이터 항목을 −∞로 취급하고, 절단된(없는) 속성도 −∞로 취급한다 — 이 모두 여기에 있다.

// _bt_compare — src/backend/access/nbtree/nbtsearch.c (condensed)
/* Force result ">" if target item is first data item on an internal page */
if (!P_ISLEAF(opaque) && offnum == P_FIRSTDATAKEY(opaque))
    return 1;
/* ... compare ncmpkey scankey attributes against the tuple ... */
/* All non-truncated attributes equal: treat truncated attrs as -inf */
if (key->keysz > ntupatts)
    return 1;
/* ... then break ties on heap TID via key->scantid ... */

flowchart TD
  START["페이지 P 진입 (READ 래치)"] --> RM{"P가 가장 오른쪽?\n(btpo_next == P_NONE)"}
  RM -- yes --> STAY["High key = +inf:\n키가 여기에 속함"]
  RM -- no --> IGN{"P가 삭제/half-dead?\n(P_IGNORE)"}
  IGN -- yes --> STEP["P 해제, P.btpo_next 래치"]
  IGN -- no --> CMP{"_bt_compare(key, P_HIKEY)\n>= cmpval ?"}
  CMP -- "yes (키가 high key 초과)" --> STEP
  CMP -- "no (키 <= high key)" --> STAY
  STEP --> START
  STAY --> DONE["이 페이지 사용\n(하강 또는 스캔)"]

Figure 2 — 하강 중 및 스캔 단계 진입 시마다 실행되는 _bt_moveright 복구 결정. 검색 키를 페이지의 high key와 비교한다. 키가 high key에 도달하거나 초과하면(또는 페이지가 삭제 상태이면), 페이지가 동시에 분할되거나 삭제된 것이다. 검색은 btpo_next를 따라 한 칸 오른쪽으로 이동하고, 키가 페이지의 키 공간 안에 들어올 때까지 반복한다. 어느 순간에도 한 페이지만 래치된다. L&Y의 보장이다.

삽입: 하강, 검사, 위치 탐색, 삽입 또는 분할

btinsert(AM 진입점)는 인덱스 튜플을 구성하고 _bt_doinsert를 호출한다. _bt_doinsert는 삽입 스캔키를 만들고, _bt_search_insert로 쓰기 잠금을 잡으며 올바른 리프까지 하강한 뒤, 선택적으로 유니크 제약 검사를 실행하고, 정확한 페이지 내 오프셋을 찾아 삽입한다.

// _bt_doinsert — src/backend/access/nbtree/nbtinsert.c (condensed)
itup_key = _bt_mkscankey(rel, itup);
/* ... */
search:
    stack = _bt_search_insert(rel, heapRel, &insertstate);
    if (checkingunique)
    {
        xwait = _bt_check_unique(rel, &insertstate, heapRel, checkUnique,
                                 &is_unique, &speculativeToken);
        if (TransactionIdIsValid(xwait))
        {
            _bt_relbuf(rel, insertstate.buf);   /* release, wait, retry */
            /* ... XactLockTableWait(xwait, ...) ... */
            goto search;
        }
        if (itup_key->heapkeyspace)
            itup_key->scantid = &itup->t_tid;   /* restore TID tiebreaker */
    }
    CheckForSerializableConflictIn(rel, NULL, BufferGetBlockNumber(insertstate.buf));
    newitemoff = _bt_findinsertloc(rel, &insertstate, checkingunique,
                                   indexUnchanged, stack, heapRel);
    _bt_insertonpg(rel, heapRel, itup_key, insertstate.buf, InvalidBuffer,
                   stack, itup, insertstate.itemsz, newitemoff,
                   insertstate.postingoff, false);

몇 가지 설계 요점이 보인다. 유니크 검사는 검사부터 삽입까지 “해당 값이 존재할 수 있는 첫 페이지”에 쓰기 잠금을 계속 유지한다. 같은 키를 동시에 삽입하는 두 삽입자를 별도 잠금 없이 직렬화하는 방법이다. _bt_check_unique는 SnapshotDirty를 사용해 커밋되지 않은 충돌 튜플을 보고, 기다려야 할 xid를 반환한다. 진행 중인 speculative 삽입과 충돌하면 INSERT ... ON CONFLICT 메커니즘과 협력한다. scantid 처리 방식도 눈여겨볼 부분이다. 유니크 검사 중에는 heap-TID 타이브레이커를 스캔키에서 제거해(중복이 존재할 수 있는 가장 왼쪽 페이지를 찾기 위해), 유니크성이 확인되면 TID를 복원해 물리적으로 올바른 유일 위치에 삽입한다.

_bt_search_insert는 fastpath 최적화도 구현한다. 단조 증가하는 키를 삽입하는 백엔드(시리얼 PK, 타임스탬프 등)는 가장 오른쪽 리프 블록을 RelationGetTargetBlock에 캐시한다. 다음 삽입 시 그 블록을 조건부로 잠그고 여전히 가장 오른쪽이며 공간이 있는지 확인한다. 일반적인 경우 루트에서 리프까지 하강 전체를 건너뛸 수 있다.

페이지 분할: 하나의 원자적 액션, 그 다음 지연된 부모 삽입

_bt_insertonpg가 대상 리프에 빈 공간이 없음을 발견하면 _bt_split을 호출한다. L&Y 쓰기 프로토콜의 핵심이다. 분할은 임시 버퍼에 새 왼쪽 페이지를 구성하고(새 오른쪽 페이지 획득 전에 실패하면 원본을 손상 없이 남긴다), _bt_findsplitloc으로 분할 지점을 선택하고, 새 high key를 계산하고(리프 페이지에서는 _bt_truncate로 suffix 절단), 오른쪽 페이지를 할당하고, 오른쪽 형제의 left-link를 수정하고, 이 모든 것을 단일 임계 구역 / 단일 WAL 레코드로 기록한다. 왼쪽 페이지에 BTP_INCOMPLETE_SPLIT 플래그가 설정된다.

// _bt_split — src/backend/access/nbtree/nbtinsert.c (condensed)
firstrightoff = _bt_findsplitloc(rel, origpage, newitemoff, newitemsz,
                                 newitem, &newitemonleft);
leftpage = PageGetTempPage(origpage);          /* build left half in temp */
_bt_pageinit(leftpage, BufferGetPageSize(buf));
lopaque = BTPageGetOpaque(leftpage);
lopaque->btpo_flags = oopaque->btpo_flags;
/* set flag in leftpage indicating that rightpage has no downlink yet */
lopaque->btpo_flags |= BTP_INCOMPLETE_SPLIT;
lopaque->btpo_prev = oopaque->btpo_prev;
/* ... compute lefthighkey (suffix-truncated copy of firstright on leaves) ...
   lefthighkey = _bt_truncate(rel, lastleft, firstright, itup_key); ... */
rbuf = _bt_allocbuf(rel, heaprel);             /* the new right page */
lopaque->btpo_next = rightpagenumber;          /* left -> right link */
ropaque->btpo_prev = origpagenumber;           /* right -> left link */
ropaque->btpo_next = oopaque->btpo_next;       /* right -> old next */
/* ... copy data items to left/right per split point; insert newitem ... */
if (!isrightmost)
{
    sbuf = _bt_getbuf(rel, oopaque->btpo_next, BT_WRITE);  /* old right sib */
    /* ... verify sopaque->btpo_prev == origpagenumber (corruption check) ... */
}
START_CRIT_SECTION();
PageRestoreTempPage(leftpage, origpage);       /* left never moves */
MarkBufferDirty(buf); MarkBufferDirty(rbuf);
if (!isrightmost) { sopaque->btpo_prev = rightpagenumber; MarkBufferDirty(sbuf); }
/* XLOG: one xl_btree_split record over buf, rbuf, sbuf (+cbuf for internal) */
END_CRIT_SECTION();

세 가지 불변식이 이를 충돌 안전하고 동시성 안전하게 만든다.

1. 왼쪽 페이지는 이동하지 않는다. 원본 블록 번호가 왼쪽 절반으로 남는다. 새 블록이 항상 오른쪽 절반이다. 원본 페이지를 가리키던 모든 기존 다운링크와 right-link가 유효하게 유지된다. 오른쪽으로 이동한 키는 새 right-link를 따라 도달 가능하다.
2. 잠금은 엄격히 왼쪽-오른쪽 순서로 결합된다. 기존 오른쪽 형제는 분할 중인 페이지 이후에 잠근다. 잠금 순서가 항상 오른쪽 방향으로 증가하므로 구조적으로 교착 상태가 발생하지 않는다. (_bt_split 주석: “We are guaranteed that this is deadlock-free, since we couple the locks in the standard order: left to right.”)
3. 분할은 right-link가 설정되는 순간 논리적으로 완료된다. 부모 다운링크가 아직 없어도 마찬가지다. 왼쪽 페이지에 도달한 동시 검색은 새로운(더 낮은) high key를 보고 오른쪽으로 이동해 이동된 키를 찾는다. BTP_INCOMPLETE_SPLIT 플래그는 읽기에 대한 신호가 아니라 쓰기에 대한 메모다.

_bt_split이 잠긴 오른쪽 버퍼를 반환하면 _bt_insertonpg는 _bt_insert_parent를 호출해 다운링크를 올린다. 이것은 별도의 원자적 액션으로, 부모에 재귀적으로 삽입하고(필요시 부모도 분할하며), 루트 분할이면 _bt_newlevel로 새 루트를 구성한다.

// _bt_insert_parent — src/backend/access/nbtree/nbtinsert.c (condensed)
if (isroot)
{
    rootbuf = _bt_newlevel(rel, heaprel, buf, rbuf);   /* new root one level up */
    /* ... release buffers ... */
}
else
{
    ritem = (IndexTuple) PageGetItem(page, PageGetItemId(page, P_HIKEY));
    new_item = CopyIndexTuple(ritem);                  /* parent separator = left's high key */
    BTreeTupleSetDownLink(new_item, rbknum);           /* ... points at new right page */
    pbuf = _bt_getstackbuf(rel, heaprel, stack, bknum);/* re-find parent via descent stack */
    _bt_relbuf(rel, rbuf);                             /* right child can be released now */
    /* ... ereport if pbuf invalid (failed to re-find parent) ... */
    _bt_insertonpg(rel, heaprel, NULL, pbuf, buf, stack->bts_parent,
                   new_item, MAXALIGN(IndexTupleSize(new_item)),
                   stack->bts_offset + 1, 0, isonly);  /* recurse up */
}

부모에 올리는 구분 키는 왼쪽 페이지의 high key다. _bt_split 주석은 이것이 firstright 튜플의 (절단된) 복사본으로, L&Y가 요구하는 “부모 구분 키는 오른쪽 서브트리의 모든 키보다 엄격히 작아야 한다”는 조건을 충족한다고 명시한다. _bt_getstackbuf는 _bt_search가 기록한 하강 스택을 사용해 자식의 블록 번호를 기준으로 부모를 재탐색한다. 구분 키로 찾는 것이 아니다. PostgreSQL이 L&Y보다 의도적으로 단순화한 부분이다. 덕분에 상승 중에 레벨 사이 잠금을 결합할 필요가 없고, 구분 키가 바뀌었는지 신경 쓰지 않아도 된다.

sequenceDiagram
    participant I as 삽입자
    participant L as 왼쪽 페이지 (원본 블록)
    participant R as 새 오른쪽 페이지
    participant S as 기존 오른쪽 형제
    participant P as 부모 페이지
    Note over I,S: 원자적 액션 1 — xl_btree_split WAL 레코드 하나
    I->>L: 임시 버퍼에 왼쪽 절반 구성, 새 (더 낮은) high key
    I->>R: _bt_allocbuf; 이동된 항목 복사; btpo_prev=L, btpo_next=S 설정
    I->>L: btpo_next = R; BTP_INCOMPLETE_SPLIT 설정
    I->>S: btpo_prev = R (left-link 수정; L 다음에 잠금, 왼쪽->오른쪽)
    I->>L: PageRestoreTempPage (왼쪽은 이동하지 않음); 모두 MarkBufferDirty
    Note over I,P: 트리는 이제 검색 가능; 독자는 right-link를 따라 틈새를 건넌다
    Note over I,P: 원자적 액션 2 — 별도의 xl_btree_insert (UPPER) 레코드
    I->>P: _bt_getstackbuf가 자식 blkno로 부모 재탐색
    I->>P: 다운링크(구분 키 = L의 high key) 삽입, 스택 오프셋+1 위치에
    I->>L: 부모 삽입과 원자적으로 BTP_INCOMPLETE_SPLIT 해제

Figure 3 — 두 독립적인 원자적 WAL 액션으로 이루어진 페이지 분할. 액션 1은 새 오른쪽 페이지를 연결하고 왼쪽 페이지에 미완료 플래그를 세운다. 독자가 right-link로 복구하므로 트리는 이 시점부터 완전히 검색 가능하다. 액션 2는 부모에 다운링크를 올리고 플래그를 지운다. 두 액션 사이에 충돌이 발생해도 유효한(다운링크만 없는) 트리가 남는다. _bt_moveright나 _bt_getstackbuf를 통과하는 다음 삽입자가 _bt_finish_split으로 지연 복구한다.

분할 지점 선택

_bt_findsplitloc(nbtsplitloc.c)이 어디서 분할할지 결정한다. 주 목표는 들어오는 튜플을 고려한 후 두 절반의 빈 공간을 균등하게 하는 것이지만, suffix 절단을 효과적으로 만들고 중복 그룹이 페이지에 걸치지 않도록 편향도 적용한다. 가장 오른쪽 페이지에서는 단조 증가 삽입이 밀도 높은 페이지를 생성하도록 왼쪽을 fillfactor%(리프 기본값 90%)로 채운다. 순진한 중간점 분할이라면 50% 활용도에 그쳤을 것이다.

// fillfactor 상수 — src/include/access/nbtree.h
#define BTREE_DEFAULT_FILLFACTOR    90
#define BTREE_NONLEAF_FILLFACTOR    70
#define BTREE_SINGLEVAL_FILLFACTOR  96

허용 빈 공간 범위 안에서 후보 분할 지점 목록을 만들고 세 전략 중 하나를 실행한다. SPLIT_DEFAULT, SPLIT_MANY_DUPLICATES(최소한으로 구분되는 지점 탐색), SPLIT_SINGLE_VALUE(페이지 전체가 하나의 값: 향후 중복을 수용하도록 왼쪽을 거의 가득 채움). suffix 절단을 최대화하면서도 분할 불균형을 과도하게 일으키지 않는 전략을 선택한다.

인덱스 튜플 삭제: 분할 전 네 계층

PostgreSQL은 위에서 설명한 계층화된 방식으로 죽은 인덱스 항목을 제거한다. 가장 저렴한 계층은 LP_DEAD 힌트 마킹이다. 일반 인덱스 스캔이 힙을 방문해 튜플이 모두에게 죽었음을 발견하면 인덱스로 돌아와 항목의 LP_DEAD 라인-포인터 플래그를 설정한다(배타적 잠금이 이미 잡힌 유니크 인덱스 충돌 확인 중에도 수행된다). README:

// nbtree/README — Simple deletion
//  Once an index tuple has been marked LP_DEAD it can actually be deleted
//  from the index immediately; since index scans only stop "between" pages,
//  no scan can lose its place from such a deletion.

삽입이 페이지를 분할하려 할 때, _bt_delete_or_dedup_one_page가 먼저 트리를 키우지 않고 공간을 확보하려 한다. 순서는 다음과 같다. 먼저 LP_DEAD 표시된 튜플을 물리적으로 삭제한다. 그것으로 충분하지 않고 실행기가 들어오는 튜플이 변경 없는 중복(UPDATE로 인한 버전 변경)임을 힌트했다면, bottom-up 삭제 패스(_bt_bottomupdel_pass)를 실행해 테이블 AM에 인근 중복 중 실제로 죽은 것이 있는지 묻는다. 최후의 수단으로 중복 제거 패스(_bt_dedup_pass)를 실행한다. 두 삭제 패스는 동일한 WAL 레코드(_bt_delitems_delete)와 snapshotConflictHorizon 계산을 위한 동일한 테이블-AM 협력을 공유한다. 이 값은 스탠바이에서 복구 충돌을 생성하는 데 쓰인다.

README는 bottom-up 삭제를 “세대 가설(generational hypothesis)” — 대부분의 인덱스 튜플은 일찍 죽는다 — 에 근거한 안전망으로 설명한다. UPDATE 버전 변경이 많은 병적 워크로드에서 죽은 UPDATE 버전을 저장하기 위해 몇몇 리프 페이지가 반복적으로 분할되는 상황을 타깃으로 한다.

VACUUM: 물리적 순서로 대량 삭제, 그리고 분할 경쟁

btbulkdelete는 AM의 대량 삭제 콜백이다. vacuum cycle ID를 획득하고 btvacuumscan을 실행한다. btvacuumscan은 읽기 선행(read-ahead) 효율을 위해 키 순서가 아닌 물리적 블록 순서로 인덱스를 스위프하며 각 페이지에서 btvacuumpage를 호출한다. 삭제할 내용이 없는 리프 페이지에서도 cleanup lock(다른 핀이 없어야 하는 초-배타 잠금)을 잡는다. 진행 중인 스캔이 TID 재활용으로 혼란에 빠지지 않도록 하는 인터락이다.

미묘한 정확성 문제가 있다. VACUUM이 스캔 중에 페이지가 분할되면 아직 방문하지 않은 페이지의 튜플이 이미 방문한 더 낮은 번호의 페이지로 이동할 수 있다. BTCycleId 메커니즘이 이를 감지한다. 분할은 양쪽 절반에 실행 중인 VACUUM의 cycle ID를 찍는다. btvacuumpage가 btpo_cycleid가 현재 cycle과 같고 btpo_next(right-link)가 현재 스캔 위치보다 낮은 블록을 가리키는 리프를 만나면, 스캔이 시작된 이후 페이지가 분할됐음을 알고 right-link를 따라 역추적한다.

// btvacuumpage — src/backend/access/nbtree/nbtree.c (condensed)
/* Check whether we need to backtrack to earlier pages.  What we are
 * concerned about is a page split that happened since we started the
 * vacuum scan, moving right-half tuples to a block we already passed. */
if (vstate->cycleid != 0 &&
    opaque->btpo_cycleid == vstate->cycleid &&
    !(opaque->btpo_flags & BTP_SPLIT_END) &&
    !P_RIGHTMOST(opaque) &&
    opaque->btpo_next < scanblkno)
    backtrack_to = opaque->btpo_next;

BTP_SPLIT_END는 역추적 범위를 제한하는 최적화다. 분할이 오른쪽 형제의 cycle ID가 다름을 감지하면 오른쪽 페이지에 BTP_SPLIT_END를 표시해 VACUUM이 더 오른쪽을 추적하지 않아도 된다고 알린다. cycle ID 검사는 거짓 양성(불필요한 역추적)은 허용하지만 거짓 음성은 절대 없다. 그래서 16비트 카운터(MAX_BT_CYCLE_ID)로 충분하다.

빈 페이지 삭제: 두 단계 half-dead 프로토콜

모든 데이터 항목이 사라진 리프 페이지는 삭제 후보가 된다. 트리에서 제거하는 것이다. PostgreSQL은 레벨의 가장 오른쪽 페이지는 절대 삭제하지 않고, 부분적으로 찬 페이지를 병합하지도 않는다. 완전히 빈 리프(그 위의 단일 자식 내부 페이지 “가느다란 체인” 포함)만 끊어낸다. _bt_pagedel이 두 단계 프로토콜을 구동한다.

• 1단계 — half-dead 표시 (_bt_mark_page_halfdead): 부모를 재탐색하고, 리프의 다운링크를 제거하고, 해당 키 공간을 오른쪽 형제로 돌리고, 리프에 BTP_HALF_DEAD를 설정한다. Half-dead 페이지는 P_IGNORE다. 검색이 불완전 분할과 동일하게 오른쪽으로 이동해 건너뛴다. 트리는 “페이지 분할과 비슷한 상태가 된다: 이 페이지를 가리키는 다운링크는 없지만 형제 연결은 유지된다.”
• 2단계 — 끊어내기 (_bt_unlink_halfdead_page): 왼쪽 형제, 대상, 오른쪽 형제를 잠그고(왼쪽-오른쪽 순서), 대상을 형제 체인에서 빼내고 BTP_DELETED를 설정한다.

stateDiagram-v2
    [*] --> Live
    Live --> HalfDead: 1단계 _bt_mark_page_halfdead\n부모에서 다운링크 제거\n키 공간이 오른쪽 형제로 이동
    HalfDead --> Deleted: 2단계 _bt_unlink_halfdead_page\n형제 체인에서 끊어냄\nsafexid 찍음
    Deleted --> Recyclable: BTPageIsRecyclable\nsafexid가 모두에게 가시적
    Recyclable --> Reused: FSM에서 가져와\n새 오른쪽 페이지로 덮어씀
    Reused --> [*]

Figure 4 — 빈 페이지 삭제 생명주기. 페이지는 Live → HalfDead → Deleted 순서로 전환되며, 각 화살표는 별도의 원자적 WAL 액션이다. VACUUM이 중단돼도 트리는 일관성을 유지하고(다음 VACUUM이 고립된 half-dead 페이지를 마저 처리한다), Deleted 상태의 페이지는 즉시 재사용되지 않는다. safexid가 찍히고, BTPageIsRecyclable이 어떤 스냅샷도 더 이상 참조할 수 없음을 확인할 때까지 묘비로 남는다. Lanin & Shasha의 “drain 기법”이다.

두 단계가 각각 WAL 레코드가 되므로, 중단된 VACUUM은 일관성 있는 트리를 남기고 다음 VACUUM이 마저 처리한다. 삭제된 페이지는 즉시 재활용되지 않는다. 동시 검색이 이미 해당 페이지로의 다운링크를 읽었을 수 있기 때문에 safexid(다음 트랜잭션 카운터)를 찍고 묘비로 남긴다. BTPageIsRecyclable이 해당 xid가 모두에게 가시적이 될 때까지 재사용을 막는다.

// BTPageIsRecyclable — src/include/access/nbtree.h (condensed)
opaque = BTPageGetOpaque(page);
if (P_ISDELETED(opaque))
{
    FullTransactionId safexid = BTPageGetDeleteXid(page);
    /* Recycle only once the deletion XID is visible to everyone, so no
     * in-progress scan could still follow a downlink to this page. */
    return GlobalVisCheckRemovableFullXid(heaprel, safexid);
}
return false;

지연이 “drain 기법”이다. VACUUM은 새로 삭제된 페이지를 BTPendingFSM 배열에 추적하고, 스캔 끝에(_bt_pendingfsm_finalize) 이미 안전해진 것들을 free-space map에 넣는다. 나머지는 다음 VACUUM에 맡긴다. 메타페이지의 btm_last_cleanup_num_delpages가 이 수를 앞으로 전달한다.

중복 제거와 posting list

삭제가 충분한 공간을 확보하지 못하면 _bt_dedup_pass가 동일한 non-pivot 튜플들을 하나의 posting-list 튜플 — 키 값 하나에 heap TID 배열 — 로 접는다. 튜플의 t_tid를 재활용한 BT_IS_POSTING 상태 비트로 식별한다.

// nbtree.h — posting-list 튜플 인식 (condensed)
#define BT_IS_POSTING   0x2000
static inline bool
BTreeTupleIsPosting(IndexTuple itup)
{
    if ((itup->t_info & INDEX_ALT_TID_MASK) == 0)
        return false;
    /* presence of BT_IS_POSTING in offset number indicates posting tuple */
    return (ItemPointerGetOffsetNumberNoCheck(&itup->t_tid) & BT_IS_POSTING) != 0;
}

중복 제거는 항상 지연(분할이 임박할 때만)되며, opclass가 btm_allequalimage(동일한 datum이면 바이트 단위로 동일하므로 접어도 손실 없음)를 보장하는 인덱스에서만 수행된다. 유니크 인덱스에서는 다른 목적으로 쓰인다. 공간 절약이 아니라(장기적으로 실제 중복이 없으므로), 버전 변경 분할 이전에 가비지 컬렉션이 실행될 시간을 벌기 위해서다. 들어오는 튜플의 heap TID가 기존 posting list 범위 안에 들어오면 _bt_insertonpg가 posting-list 분할을 그 자리에서 수행하며, 삽입과 동일한 원자적 액션으로 처리된다.

소스 코드 가이드

서브시스템별로 묶은 심볼 목록이다. 위치 힌트 표가 뒤따른다.

AM 인터페이스 (nbtree.c)

• bthandler — nbtree의 기능 플래그(amcanorder, amcanbackward, amcanunique, amcanparallel, ampredlocks, amcaninclude 등)와 콜백 포인터를 채운 IndexAmRoutine을 반환한다. 디스패치 계약 자체는 postgres-index-am.md가 관리한다.
• btinsert — AM 삽입 콜백. IndexTuple을 구성하고 heap TID를 설정한 뒤 _bt_doinsert에 위임한다.
• btgettuple / btgetbitmap — AM 스캔 콜백(읽기 경로; 정렬 스캔 대 비트맵).
• btbuildempty — _bt_initmetapage를 호출해 메타페이지를 초기화한다.

검색 및 스캔 (nbtsearch.c)

• _bt_search — 루트에서 리프까지 하강하며 래치 연결. 각 레벨에서 _bt_moveright를 호출한다. 나중에 분할이 부모를 재탐색할 때 사용하는 하강 스택을 반환한다.
• _bt_moveright — L&Y 복구 기본 연산. 검색 키가 페이지의 high key에 도달하거나 초과하는 동안, 또는 페이지가 P_IGNORE인 동안 오른쪽으로 이동한다. forupdate일 때 불완전 분할을 마저 처리한다.
• _bt_compare — 3방향 키 비교기. “첫 번째 내부 데이터 항목은 −∞”, “절단된 속성은 −∞”, heap-TID 타이브레이커를 인코딩한다.
• _bt_binsrch / _bt_binsrch_insert — 페이지 내 이진 탐색(탐색 위치 vs. 삽입 위치, 후자는 scantid 포함).
• _bt_first / _bt_next / _bt_readpage / _bt_steppage — 정렬 스캔 상태 기계. _bt_first가 _bt_search로 위치를 잡고 형제 링크를 따라 리프를 스캔한다. 스캔 시점의 right-link를 기억해 동시 분할이 이미 이동된 항목을 다시 스캔하지 못하게 한다.
• _bt_lock_and_validate_left — 역방향 스캔의 왼쪽 이동. 왼쪽 형제 자신이 분할된 어려운 경우를 처리한다(README의 4단계 move-left 알고리즘).

삽입 및 분할 (nbtinsert.c)

• _bt_doinsert — 삽입 드라이버. 스캔키 구성, 쓰기 잠금 하강, 유니크 검사, 위치 탐색, 삽입.
• _bt_search_insert — 가장 오른쪽 리프 fastpath 캐시(RelationGetTargetBlock)를 포함한 _bt_search 래퍼.
• _bt_check_unique — SnapshotDirty 하의 유니크 강제. 기다려야 할 충돌 xid를 반환한다.
• _bt_findinsertloc / _bt_stepright — 정확한 페이지 내 오프셋 탐색. 값이 형제에 속하면 오른쪽으로 이동한다.
• _bt_insertonpg — 삽입/분할 분기. 항목이 맞으면 추가(WAL 레코드 하나, 자식의 incomplete-split 플래그 해제); 아니면 _bt_split 후 _bt_insert_parent 호출.
• _bt_split — 원자적 분할 액션. 임시 왼쪽 페이지, 새 high key(_bt_truncate 포함), 오른쪽 페이지 할당, 오른쪽 형제 left-link 수정, BTP_INCOMPLETE_SPLIT 플래그, 단일 WAL 레코드.
• _bt_insert_parent — 부모에 다운링크 올리기(또는 루트 분할이면 _bt_newlevel). _bt_getstackbuf로 부모를 재탐색한다.
• _bt_finish_split / _bt_getstackbuf — 불완전 분할의 지연 복구. 자식 블록 번호로 부모를 재탐색한다.
• _bt_newlevel — 한 레벨 위에 새 루트 구성. 메타페이지 갱신.
• _bt_delete_or_dedup_one_page / _bt_simpledel_pass — 분할 전 공간 확보(LP_DEAD 물리 삭제, 단순 삭제).

분할 지점 선택 (nbtsplitloc.c)

• _bt_findsplitloc — 분할 지점 선택. 빈 공간 균등화, suffix 절단 편향, 중복 및 가장 오른쪽 페이지 특수 처리.
• _bt_strategy / _bt_bestsplitloc — 전략 선택(SPLIT_DEFAULT, SPLIT_MANY_DUPLICATES, SPLIT_SINGLE_VALUE) 및 최적 지점 탐색.

페이지, 삭제, VACUUM (nbtpage.c, nbtree.c, nbtdedup.c)

• _bt_getroot / _bt_gettrueroot — (fast) 루트 가져오기. 메타페이지를 따르고 캐시된 루트 포인터가 낡았으면 복구.
• _bt_initmetapage / _bt_getmeta / _bt_upgrademetapage — 메타페이지 I/O.
• btbulkdelete → btvacuumscan → btvacuumpage — 물리적 순서로 VACUUM 스캔. cleanup-lock 인터락, cycle-ID 역추적.
• _bt_pagedel — 페이지 삭제 드라이버.
• _bt_mark_page_halfdead / _bt_unlink_halfdead_page — 두 삭제 단계.
• _bt_lock_subtree_parent — 삭제될 서브트리의 부모 재탐색.
• BTPageIsRecyclable / _bt_pendingfsm_init / _bt_pendingfsm_finalize — 지연 재활용(drain 기법)과 FSM 배치.
• _bt_delitems_vacuum / _bt_delitems_delete / _bt_delitems_update — 페이지 항목의 WAL 기록된 제거/갱신.
• _bt_dedup_pass / _bt_bottomupdel_pass — 중복 제거와 bottom-up 삭제.

위치 힌트 (2026-06-05 기준, REL_18 273fe94)

심볼	파일	줄
bthandler	nbtree.c	115
btinsert	nbtree.c	202
btgettuple	nbtree.c	226
btbulkdelete	nbtree.c	1068
btvacuumscan	nbtree.c	1186
btvacuumpage	nbtree.c	1361
_bt_search	nbtsearch.c	107
_bt_moveright	nbtsearch.c	246
_bt_binsrch	nbtsearch.c	348
_bt_compare	nbtsearch.c	693
_bt_first	nbtsearch.c	887
_bt_steppage	nbtsearch.c	2169
_bt_doinsert	nbtinsert.c	102
_bt_search_insert	nbtinsert.c	317
_bt_check_unique	nbtinsert.c	408
_bt_findinsertloc	nbtinsert.c	815
_bt_stepright	nbtinsert.c	1027
_bt_insertonpg	nbtinsert.c	1105
_bt_split	nbtinsert.c	1467
_bt_insert_parent	nbtinsert.c	2099
_bt_finish_split	nbtinsert.c	2241
_bt_getstackbuf	nbtinsert.c	2319
_bt_newlevel	nbtinsert.c	2444
_bt_delete_or_dedup_one_page	nbtinsert.c	2683
_bt_simpledel_pass	nbtinsert.c	2812
_bt_findsplitloc	nbtsplitloc.c	129
_bt_getroot	nbtpage.c	344
_bt_pagedel	nbtpage.c	1802
_bt_mark_page_halfdead	nbtpage.c	2088
_bt_unlink_halfdead_page	nbtpage.c	2314
_bt_lock_subtree_parent	nbtpage.c	2813
_bt_pendingfsm_finalize	nbtpage.c	2996
_bt_dedup_pass	nbtdedup.c	58
_bt_bottomupdel_pass	nbtdedup.c	307
BTPageOpaqueData	nbtree.h	63
BTPageIsRecyclable	nbtree.h	292
P_HIKEY / P_FIRSTKEY	nbtree.h	368

소스 검증 (2026-06-05 기준)

검증된 사실

• right-link(btpo_next), left-link(btpo_prev), 레벨, 플래그, vacuum cycle ID는 페이지 special area의 BTPageOpaqueData에 있다. 2026-06-05에 nbtree.h에서 확인. left-link는 L&Y(right-link만 요구)에 대한 PostgreSQL의 추가다. README의 “Differences to the Lehman & Yao algorithm” 절이 확인한다.

• 검색은 한 번에 최대 페이지 래치 하나를 잡고, 동시 분할에서 btpo_next를 따라 복구한다. _bt_search(부모 잠금을 _bt_relandgetbuf로 자식 획득 전에 해제)와 _bt_moveright(_bt_compare(key, P_HIKEY) >= cmpval인 동안 오른쪽으로 이동)에서 확인. README는 PostgreSQL이 검사 중인 페이지에 읽기 래치를 잡는다고 확인한다. L&Y는 공유되지 않는 인메모리 복사본을 가정하지만 PostgreSQL은 버퍼를 공유하므로 바이트를 읽는 동안 안정적으로 유지하기 위해 래치가 필요하다.

• 페이지 분할은 두 개의 독립적인 원자적 WAL 액션이다. 첫 번째가 왼쪽 페이지에 BTP_INCOMPLETE_SPLIT를 설정하고, 두 번째가 부모 다운링크를 올리고 플래그를 지운다. _bt_split(플래그 설정, 단일 임계 구역 / xl_btree_split 레코드)과 _bt_insertonpg/_bt_insert_parent(플래그를 지우는 별도 부모 삽입)에서 확인. README “WAL Considerations” 절은 두 액션 사이 충돌이 검색 가능한 트리를 남기며, 누락된 다운링크는 다음 삽입자가 _bt_finish_split으로 즉석에서 생성한다고 명시한다.

• 분할 잠금은 엄격히 왼쪽-오른쪽 순서로 결합되고 왼쪽 절반은 원본 블록 번호를 유지한다. _bt_split에서 확인. 기존 오른쪽 형제(oopaque->btpo_next)를 분할 중인 페이지 이후에 잠그고, PageRestoreTempPage(leftpage, origpage)가 왼쪽 절반을 원본 블록에 다시 쓴다. README는 이를 잠금 순서에 의해 교착 상태가 없다고 명시한다.

• 부모 다운링크는 구분 키가 아니라 자식의 블록 번호로 재탐색한다. _bt_insert_parent(bknum을 _bt_getstackbuf에 전달)에서 확인. README는 이것이 상승 중 레벨 간 잠금 결합을 피하는 의도적인 L&Y/Lanin-Shasha 대비 단순화라고 언급한다.

• VACUUM은 물리적 블록 순서로 스캔하고, 모든 리프에 cleanup lock을 잡으며, cycle-ID 검사로 동시 분할 시 역추적한다. btvacuumscan(물리 블록 읽기 스트림)과 btvacuumpage(모든 리프에서 _bt_upgradelockbufcleanup; btpo_cycleid == vstate->cycleid && opaque->btpo_next < scanblkno로 보호되는 backtrack_to 할당)에서 확인. BTP_SPLIT_END가 역추적 범위를 제한한다.

• 빈 페이지 삭제는 two-stage half-dead → deleted 프로토콜이며, 삭제된 페이지는 safexid가 모두에게 가시적이 될 때까지 FSM 반환이 지연된다. _bt_pagedel(두 단계 구동), _bt_mark_page_halfdead(BTP_HALF_DEAD), _bt_unlink_halfdead_page(BTP_DELETED + safexid), BTPageIsRecyclable(GlobalVisCheckRemovableFullXid)에서 확인. README는 이를 Lanin & Shasha의 “drain 기법”이라고 명명한다.

• 중복 제거는 지연되고, btm_allequalimage 조건에 묶이며, BT_IS_POSTING이 표시된 posting-list 튜플을 생성한다. _bt_dedup_pass와 nbtree.h의 BTreeTupleIsPosting 인라인에서 확인. 이를 활성화하는 온디스크 버전은 BTREE_VERSION 4다. v3 인덱스는 사용하려면 REINDEX가 필요하다(버전 주석 참조).

• BTREE_VERSION 4부터 heap TID가 타이브레이커 키 컬럼이 되어 모든 항목이 해당 레벨에서 유일하다. nbtree.h 버전 주석과 _bt_compare의 heap-TID/scantid 경로에서 확인. 이것이 L&Y 서브트리 불변식의 엄격-부등식 형태(Ki < v <= Ki+1)를 허가한다.

미해결 질문

1. btvacuumpage의 역추적 작업 정확한 상한. BTP_SPLIT_END가 VACUUM이 분할 그룹 너머 right-link를 추적하는 것을 멈추지만, 단일 VACUUM 중 지속적인 동시 분할 하에서 역추적 홉의 최악 경우 수는 코드에서 명확하지 않다. 조사 경로: _bt_split의 BTP_SPLIT_END 설정(오른쪽 형제가 다른 cycle ID를 가질 때만)과 분할이 집중된 합성 워크로드에서 btvacuumpage 역추적 루프의 상호작용을 추적한다.

2. 새로 삭제된 페이지가 동일한 VACUUM 내에서 실제로 재활용 가능해지는 빈도. README는 PG14+가 스캔 끝에 _bt_pendingfsm_finalize로 재활용 안전 여부를 확인한다고 명시하지만, GlobalVisCheckRemovableFullXid를 즉시 통과하는 것과 다음 VACUUM을 기다려야 하는 것의 비율은 워크로드에 따라 다르며 여기서는 미측정이다. 조사 경로: 장기 실행 스냅샷 워크로드에서 _bt_pendingfsm_finalize를 계측한다.

3. fastpath 가장 오른쪽 리프 캐시(RelationGetTargetBlock)가 유니크 인덱스에서 bottom-up 삭제와 병리적으로 상호작용하는지 여부. 두 코드 경로 모두 가장 오른쪽/변경이 많은 리프를 대상으로 하며, 코드 경로는 분리되어 있지만 워크로드가 겹친다. 조사 경로: fastpath 삽입이 동일한 페이지에서 bottom-up 삭제 기회를 방해하는지 검토한다.

PostgreSQL 너머 — 비교 설계와 연구 프론티어

• CUBRID의 B+-트리. CUBRID도 형제 링크를 가진 B+-트리를 사용하지만, 동시성 모델이 self-repairing L&Y right-link 복구보다 페이지 수준 래치와 lock manager에 더 의존한다. CUBRID의 인덱스 페이지 래치 프로토콜과 _bt_moveright를 나란히 비교하면 L&Y “오른쪽으로 이동해 복구”가 잠금 트래픽 측면에서 실제로 무엇을 가져다주는지가 명확해진다. (CUBRID 인덱스 분석은 cubrid 트리 참조.)

• Lehman & Yao 1981 vs. PostgreSQL 구현. PostgreSQL은 논문에서 명명된 방식으로 벗어난다. 버퍼가 공유되므로 읽기 래치가 필요하고, 역방향 스캔을 위한 left-link가 있으며, 구분 키가 아닌 자식 블록 번호로 부모를 재탐색하고, 부모 다운링크를 지연 생성한다. 각 편차를 README의 정당화와 매핑하는 집중 노트가 이 문서의 자연스러운 동반 자료가 될 것이다. 논문: Lehman & Yao 1981 (dbms-papers/btree.md).

• Lanin & Shasha 1986 삭제 vs. PostgreSQL의 단순화. PostgreSQL은 삭제 시 키 공간을 오른쪽으로 이동한다(Lanin-Shasha는 왼쪽 선호). left-link가 있으므로 오른쪽이 편리하기 때문이다. “drain 기법”과 “fast root” 아이디어는 채택했다. 대칭 Lanin-Shasha 알고리즘과 _bt_pagedel의 half-dead 프로토콜을 비교하는 것은 삭제 정확성에 대한 연구 수준 과제다.

• Blink-트리 래칭 vs. 잠금 없는 / 낙관적 B-트리 (OLFIT, Bw-tree). 현대 인메모리 엔진(Microsoft의 Bw-tree, OLFIT)은 래치 B-link 트리를 넘어 래치 없는 또는 낙관적 버전 설계로 나아간다. PostgreSQL의 래치 결합 L&Y 트리를 이들과 비교하면 디스크 지향 버퍼 공유 엔진이 무엇을 포기하는지 틀을 잡을 수 있다.

• Suffix 절단 / prefix B-트리. PostgreSQL은 Bayer & Unterauer 1977의 “단순 prefix B-트리” 형태, 즉 전체 속성 절단만 구현한다. 가변 길이 타입(예: text)에 더 짧은 구분자를 만드는 opclass는 README 자체가 스케치하는 미실현 확장이다.

출처

트리 내 README 및 소스 파일 (REL_18_STABLE, commit 273fe94)

• src/backend/access/nbtree/README — 설계 문서. L&Y 기초, PostgreSQL의 차이점, VACUUM 중 삭제, 페이지 삭제, drain 기법, fast root, WAL 고려사항, 복구 중 스캔, suffix 절단, 중복 제거, posting-list 분할, 데이터 표현.
• src/include/access/nbtree.h — BTPageOpaqueData, BTMetaPageData, 플래그 비트, P_HIKEY/P_FIRSTKEY, pivot/posting 튜플 포맷, BTPageIsRecyclable, BTStackData, 버전/fillfactor 상수.
• src/backend/access/nbtree/nbtree.c — bthandler, AM 콜백, VACUUM 스캔(btbulkdelete/btvacuumscan/btvacuumpage).
• src/backend/access/nbtree/nbtinsert.c — _bt_doinsert, _bt_check_unique, _bt_insertonpg, _bt_split, _bt_insert_parent, _bt_finish_split.
• src/backend/access/nbtree/nbtsearch.c — _bt_search, _bt_moveright, _bt_compare, _bt_binsrch, 스캔 상태 기계.
• src/backend/access/nbtree/nbtpage.c — 메타페이지, _bt_pagedel, half-dead/unlink 단계, 지연 FSM 재활용.
• src/backend/access/nbtree/nbtsplitloc.c — _bt_findsplitloc 및 분할 전략.
• src/backend/access/nbtree/nbtdedup.c — _bt_dedup_pass, _bt_bottomupdel_pass.

논문 및 교과서 장

• Lehman, P. & Yao, S. B. (1981). “Efficient Locking for Concurrent Operations on B-Trees.” ACM TODS 6(4):650-670. 기반 알고리즘. 원문은 knowledge/research/dbms-papers/btree.md에 수록.
• Lanin, V. & Shasha, D. (1986). “A Symmetric Concurrent B-Tree Algorithm.” Proc. 1986 Fall Joint Computer Conf., 380-389. 삭제 논리 출처(drain 기법, fast root).
• Comer, D. (1979). “The Ubiquitous B-Tree.” ACM Computing Surveys 11(2). B-트리 배경(knowledge/research/dbms-papers/btree.md).
• Bayer, R. & Unterauer, K. (1977). “Prefix B-Trees.” ACM TODS 2(1):11-26. Suffix 절단 기반(nbtree README 인용).
• Database System Concepts (Silberschatz, Korth, Sudarshan, 7판), 14장 “Indexing” — 단일 스레드 B+-트리 기초(knowledge/research/dbms-general/).
• Database Internals (Petrov 2019), 2-6장 — B-트리 동시성, 페이지 레이아웃, WAL 프레이밍.

형제 문서 (교차 참조 — 메커니즘은 해당 문서가 관리, 여기에서 중복하지 않음)

• postgres-index-am.md — bthandler가 채우는 IndexAmRoutine 디스패치 계약.
• postgres-buffer-manager.md — nbtree의 페이지 잠금이 구축된 버퍼 핀과 콘텐츠-잠금(LWLock) 래칭.
• postgres-lock-manager.md — SQL 수준 heavyweight lock 테이블 및 (postgres-ssi-predicate-locking.md 경유) CheckForSerializableConflictIn / PredicateLockPageSplit이 연결되는 predicate lock.
• postgres-architecture-overview.md — nbtree가 기본 인덱스 AM으로 자리하는 Axis 4(플러그인 가능 접근 방법).