(KO) PostgreSQL GiST — 일반화 탐색 트리와 Opclass 지원 함수

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

학술적 배경

B-트리(postgres-nbtree.md)는 *전체 순서(total order)*가 있는 데이터에 적합한 인덱스다. 정수·문자열·타임스탬프처럼 임의의 두 키를 <로 비교할 수 있는 데이터가 그 대상이다. B-트리의 모든 구성 요소—구분 키(separator key), “오른쪽 이동 복구”, 페이지 내 이진 탐색—는 이 가정 위에 서 있다. 그런데 흥미로운 데이터 중 상당수는 자연스러운 전체 순서가 없다. 기하학적 박스는 다른 박스보다 “작지” 않고, 평면의 점은 근접성을 보존하는 단일 선형 순위가 없으며, IP 서브넷, 정수 범위, 어휘소의 tsvector, 문자열의 트라이그램 집합도 마찬가지다. 이런 데이터 타입에는 순서 대신 포함(containment) 또는 겹침(overlap) 개념이 있다. 쿼리 박스가 인덱싱된 박스와 겹치거나, 쿼리 포인트가 인덱싱된 경계 직사각형에 포함되는 식이다. 순서 대신 겹침으로 탐색 트리를 가지치기하는 인덱스라면 이 모든 타입을 처리할 수 있다.

B-트리를 순서에서 겹침으로 일반화한 구조가 R-트리다(Guttman 1984; PostgreSQL이 공간 키에서 사실상 구현한 변형은 Beckmann, Kriegel, Schneider & Seeger 1990의 R*-트리에 가깝고, dbms-papers/rstar-tree.md에 수록). R-트리는 모든 항목이 경계 술어(bounding predicate)—공간 데이터에서는 최소 경계 직사각형(MBR)—와 포인터로 이루어진 균형 트리다. 리프 항목의 MBR은 단일 객체를 감싸고, 내부 항목의 MBR은 자신이 가리키는 서브트리의 모든 MBR을 포함한다. 이 구조를 탐색 트리로 만드는 두 불변식은 다음과 같다.

Coverage(포함 관계). 내부 항목의 술어는 그 아래 모든 자식의 술어를 포함한다. 따라서 쿼리 술어가 내부 항목과 분리(disjoint)되면 해당 서브트리 전체를 안전하게 건너뛸 수 있다.
Balance(균형). 모든 리프가 같은 깊이에 있으므로 조회·삽입·R*-트리의 강제 재삽입이 O(log N)을 유지한다.

B-트리와 달리 R-트리는 형제 사이에 경계 술어가 겹칠 수 있다. 그래서 포인트 쿼리가 두 개 이상의 서브트리로 내려갈 수 있다. R-트리의 품질—겹침이 얼마나 적고, MBR이 데이터를 얼마나 촘촘히 감싸는가—은 두 가지 휴리스틱으로 결정된다. 삽입 경로 선택(“새 항목을 수용하려면 어느 자식 MBR을 가장 적게 확장해야 하는가”)과 노드 분할(“페이지가 넘칠 때 항목을 어떻게 나눠 전체 면적/겹침을 최소화하는가”)이 그것이다. Guttman의 2차·선형 분할 휴리스틱과 R*-트리의 마진 최소화 분할·강제 재삽입은 직사각형에 맞게 조정한 이 두 매개변수의 구체적 구현이다.

GiST를 만들어낸 개념적 도약은 트리 골격, 균형 유지, 동시성 프로토콜, 충돌 복구 로직이 키가 직사각형인지에 전혀 의존하지 않는다는 관찰이다. Hellerstein, Naughton & Pfeffer 1995, “Generalized Search Trees for Database Systems” (SIGMOD; src/backend/access/gist/README 맨 위에 인용된 기초 참조 문헌)이 이를 명시했다. 핵심 주장은 B-트리와 R-트리 모두 하나의 균형, 다방향, 경계-술어 트리의 인스턴스이며, (a) “키”가 무엇인지와 (b) 키에 대한 네 가지 추상 연산만 다르다는 것이다. 그 네 연산을 사용자 공급 인터페이스로 분리하면, 포함 개념이 있는 모든 데이터 타입에 특화할 수 있는 단일 재사용 가능 인덱스 템플릿이 나온다. 1995년 논문이 정의한 네 가지 GiST 메서드는 다음과 같다.

Consistent(E, q) — 인덱스 항목 E(술어)와 쿼리 술어 q가 주어질 때, 어떤 객체도 E와 q를 동시에 만족할 수 없음이 증명 가능하면 false를 반환한다. 가지치기 기본 연산이다. false이면 E의 서브트리를 건너뛰고, true(과도하게 낙관적일 수 있음)이면 하강을 강제한다.
Union(E1..En) — E1..En 중 어느 것이든 만족하는 모든 객체에 성립하는 단일 술어를 반환한다. 내부 다운링크가 저장하는 값이다. 자식들의 경계 술어다.
Penalty(E1, E2) — E2를 E1 루트의 서브트리에 삽입하는 비용을 나타내는 수치다(보통 직사각형의 경우 면적 증가). 삽입 경로 선택을 구동한다.
PickSplit(P) — 넘친 항목 집합 P를 두 그룹으로 나눈다. 노드 분할을 구동한다.

실용적인 인터페이스를 완성하는 두 메서드가 추가된다(논문이 암시하고 PostgreSQL이 형식화). Compress/Decompress는 디스크 키를 인덱싱된 값의 손실 또는 압축 표현으로 만들고(다각형 대신 MBR), Equal은 다운링크 유지 중에 재계산된 union이 변경되지 않았는지 감지한다. PostgreSQL은 Distance(최근접 이웃 ORDER BY), Fetch(인덱스 전용 스캔을 위한 원래 값 재구성), Options(opclass 파라미터 파싱), SortSupport(바텀업 정렬 빌드 활성화)를 추가한다.

이 설계의 이점은 막대하다. PostgreSQL의 box_ops, range_ops, inet_ops, tsvector_ops, PostGIS 공간 인덱스, pg_trgm 유사도 인덱스, btree_gist 순서 에뮬레이션 opclass가 모두 같은 액세스 메서드이며, 소수의 C 함수만 다르다. 대가는 AM이 키의 의미를 직접 추론할 수 없다는 점이다. AM은 페이지 내 이진 탐색을 할 수 없고(순서 없음), 모든 가지치기 결정에 사용자 함수를 호출해야 한다. 허술한 opclass(너무 자주 true를 반환하는 Consistent, 겹치는 그룹을 만드는 PickSplit)는 조용히 순차 스캔으로 격하된다. GiST는 B-트리의 자기 완결적 효율성 대신 확장성을 선택하며, 이 문서의 나머지는 PostgreSQL이 그 교환을 충돌 안전하고 동시성 있게 구현하는 방식을 다룬다.

DBMS 공통 설계 패턴

PostgreSQL의 심볼을 읽기 전에, 확장 가능하고 겹침 기반의 균형 트리가 공통으로 채택하는 설계 패턴을 먼저 이름 붙여두면 유용하다.

템플릿 메서드 인덱스: 엔진의 골격, 플러그인의 의미론

정의적인 패턴은 고전 Template Method다. 데이터베이스 엔진이 알고리즘 골격(하강, 분할, 전파, 잠금, 로그, 복구)을 소유하고, 데이터 타입 의미론을 공급하는 소수의 훅을 호출한다. 모든 확장 가능 인덱스는 대략 같은 훅 집합—가지치기용 match 술어, 다운링크용 bounding 연산, 경로 선택용 cost 함수, 분할용 partition 함수—으로 수렴한다. 균형 경계-술어 트리가 내려야 하는 네 결정 지점이 정확히 그것이고, 키의 의미에 의존하는 부분도 그 네 지점뿐이기 때문이다. Oracle의 Extensible Indexing(ODCIIndex 인터페이스), Informix의 Datablade 가상 인덱스, Microsoft의 CLR 기반 공간 인덱스 모두 이름만 다른 같은 아이디어다. GiST는 그 오픈소스 표준형이고, 1995년 논문이 명세다.

겹침, 순서 아님: 파생되는 결과들

형제 술어가 겹칠 수 있기 때문에 B-트리와 세 가지가 다르다.

검색이 팬아웃될 수 있다. 단일 쿼리가 한 페이지의 여러 자식에서 Consistent 테스트를 통과할 수 있다. 검색은 단일 루트-리프 경로가 아니라 프론티어 순회다. 구현은 단일 하강 포인터 대신 방문할 페이지의 작업 큐를 유지한다.
“오른쪽 이동”을 위한 high key가 없다. B-트리는 검색 키를 페이지의 high key와 비교해 동시 분할에서 복구한다. 순서가 없으면 그 테스트를 쓸 수 없으므로, 복구 신호를 키에서 파생하는 대신 명시적(페이지당 시퀀스 번호)으로 만들어야 한다.
분할 품질은 보장이 아닌 휴리스틱이다. B-트리 분할은 자명하게 균형 잡힌다(정렬된 런을 반으로 자름). 겹침 트리의 분할은 미래의 잘못된 하강을 최소화하는 분할을 선택해야 하며, 그 선택은 데이터 타입에 따라 다르다. PickSplit이 사용자 훅인 이유다. 나쁜 PickSplit은 느린 인덱스를 만들 뿐, 틀린 인덱스를 만들지는 않는다.

하강 중 다운링크 조정 삽입

단순한 경계-술어 삽입은 리프까지 하강해 삽입한 뒤, 다시 올라가며 모든 조상의 술어를 새 항목을 포함하도록 확장한다. 두 번의 패스가 필요하며, 중간에 충돌하면 조상이 서브트리를 과소 포함하는 상태가 남는다. PostgreSQL이 채택한 견고한 대안은 하강 중에 선택된 다운링크를 확장하는 것이다. 각 내부 페이지에서, 선택된 자식으로 재귀하기 전에 자식의 다운링크를 이전 다운링크와 새 키의 union으로 교체한다. 리프에 도달하면 모든 조상이 이미 새 항목을 포함하므로, 삽입은 단일 패스이고 리프를 쓴 뒤 트리는 자기 일관적이다. 위로 올라가는 fix-up이 없으므로 충돌 복구가 단순하다.

Right-link + 시퀀스 번호를 이용한 경량 잠금 동시성

B-link 트리의 핵심 트릭(postgres-nbtree.md)—각 레벨은 right-link 연결 리스트, 검색은 한 번에 페이지 래치 하나, 방금 분할된 페이지에 도달하면 right-link를 추적—은 겹침 트리에도 그대로 적용된다. 단, 분할 감지 신호가 다르다. high key가 없으므로, 겹침 트리는 각 페이지에 **노드 시퀀스 번호(NSN)**를 찍는다. 분할이 부모에 다운링크를 올릴 때, 부모 갱신의 LSN을 자식의 NSN으로 복사한다. 검색은 다운링크를 읽을 때 부모 페이지의 LSN을 기억하고, 자식에 도달하면 기억한 LSN을 자식의 NSN과 비교한다. 자식의 NSN이 더 크면 부모를 읽은 후 자식이 분할됐으므로, 검색은 자식의 right-link도 따라야 한다. 이것이 GiST에 L&Y를 적용한 Kornacker(“Access Methods for Next-Generation Database Systems”, README의 동시성 참조 문헌)의 방식이며, PostgreSQL이 구현한 메커니즘이다.

WAL 원자 단계를 통한 충돌 안전 다중 페이지 변경

WAL 엔진에서 N개 페이지에 걸친 분할은 각각 유효한 트리를 남기는 원자 로그 레코드로 분해된다. 표준 분해 방식은 다음과 같다. (1) 새 오른쪽 페이지를 원자적으로 쓰고, 이전 페이지의 right-link를 설정하며, “오른쪽 형제의 부모 다운링크가 아직 없다”는 플래그를 세운다. (2) 원자적으로 부모에 다운링크를 올리고 플래그를 지우며 NSN을 찍는다. (1)과 (2) 사이에 충돌이 발생해도 트리는 완전히 검색 가능하다. 플래그가 검색과 다음 삽입자에게 right-link를 추적하라고 알리고, 다음 하강이 지연 방식으로 불완전한 분할을 복구한다.

대량 적재: 정렬 vs. 버퍼링

수십억 튜플을 하나씩 디스크 트리에 삽입하면 무작위 I/O에 구속된다. 각 삽입이 대부분 캐시되지 않은 루트-리프 경로를 탄다. 두 가지 표준 가속이 적용된다. 정렬 빌드(B-트리 스타일): 키를 지역성을 보존하는 정렬 순서로 선형화할 수 있으면, 정렬 후 리프를 바텀업으로 채우고 각 부모 레벨을 아래 레벨에서 구성한다. 버퍼링 빌드(Arge, Hinrichs, Vahrenhold & Vitter, README의 빌드 참조 문헌): 내부 노드에 메모리/임시 파일 버퍼를 붙이고, 들어오는 튜플을 첫 번째 버퍼링 노드까지만 밀어 넣고, 버퍼가 꽉 차면 한 레벨씩 내려 플러시한다. 깊이 우선 무작위 하강을 캐시 크기에 맞는 너비 우선 배치로 변환한다.

이론 ↔ PostgreSQL 대응표

이론 / 관행	PostgreSQL 이름 (gist)
Consistent (가지치기 술어)	`GIST_CONSISTENT_PROC` → `giststate->consistentFn`, `gistindex_keytest`에서 호출
Union (자식들의 경계 술어)	`GIST_UNION_PROC` → `unionFn`, `gistMakeUnionItVec` 경유
Penalty (삽입 경로 비용)	`GIST_PENALTY_PROC` → `penaltyFn`, `gistpenalty` / `gistchoose` 경유
PickSplit (노드 분할)	`GIST_PICKSPLIT_PROC` → `picksplitFn`, `gistUserPicksplit` / `gistSplitByKey` 경유
Compress / Decompress (디스크 키 형식)	`GIST_COMPRESS_PROC` / `GIST_DECOMPRESS_PROC` → `compressFn` / `decompressFn`
Equal (변경 없는 union 감지)	`GIST_EQUAL_PROC` → `equalFn`, `gistgetadjusted` 경유
Distance (k-NN ORDER BY)	`GIST_DISTANCE_PROC` → `distanceFn`, `gistget.c`의 k-NN 큐
Fetch (인덱스 전용 재구성)	`GIST_FETCH_PROC` → `fetchFn`, `gistFetchTuple` 경유
SortSupport (바텀업 빌드)	`GIST_SORTSUPPORT_PROC`, `GIST_SORTED_BUILD` 활성화 조건
경계-술어 다운링크	키가 union인 내부 `IndexTuple`; `t_tid`가 자식 블록 번호
하강 중 다운링크 조정	`gistdoinsert` 내부의 `gistgetadjusted` + `gistinserttuple`
노드 시퀀스 번호 (분할 신호)	`GistPageGetNSN` / `GistPageSetNSN`, `GistNSN` = `XLogRecPtr`
Right-link	`GISTPageOpaqueData.rightlink`
”오른쪽 형제에 다운링크 없음” 플래그	`F_FOLLOW_RIGHT` (`GistFollowRight` / `GistMarkFollowRight`)
분할 1단계 / 2단계	`gistplacetopage` (연결+플래그) / `gistfinishsplit` (다운링크 올리기, NSN 설정)
지연 불완전 분할 복구	`gistfixsplit` (`F_FOLLOW_RIGHT`에 의해 트리거됨)
이동된 부모 재탐색	`gistFindCorrectParent` / `gistFindPath`
팬아웃 검색용 작업 큐	`GISTScanOpaque->queue` (`pairingheap`)
정렬 대량 빌드	`gist_indexsortbuild` (`GIST_SORTED_BUILD`)
버퍼링 대량 빌드	`gistInitBuffering` + `GISTBuildBuffers` (`GIST_BUFFERING_ACTIVE`)
AM 디스패치 테이블	`gisthandler`가 `IndexAmRoutine` 반환 (`postgres-index-am.md` 참조)

PostgreSQL의 구현

PostgreSQL의 src/backend/access/gist/는 README 표현대로 “GiST 인덱싱의 구현”이며, Kornacker 방식으로 동시성을 강화하고 Arge et al. 방식으로 대량 적재를 가속한다. 디스크 트리는 BLCKSZ 페이지로 이루어진 균형 잡힌 right-link 트리다. AM이 하강·분할·WAL·동시성을 소유하고, opclass가 최대 12개의 지원 함수로 데이터 타입 의미론을 공급한다. AM의 모든 특성은 하나의 핸들러에서 선언된다.

AM 핸들러: GiST가 할 수 있는 것과 없는 것

// gisthandler — src/backend/access/gist/gist.c
Datum
gisthandler(PG_FUNCTION_ARGS)
{
    IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);

    amroutine->amstrategies = 0;          // strategy numbers are opclass-defined
    amroutine->amsupport = GISTNProcs;    // 12 support procs (consistent..sortsupport)
    amroutine->amcanorder = false;        // no total order -> can't drive ORDER BY col
    amroutine->amcanorderbyop = true;     // CAN drive ORDER BY <-> (k-NN)
    amroutine->amcanmulticol = true;      // multi-column GiST
    amroutine->amoptionalkey = true;
    amroutine->amsearchnulls = true;
    amroutine->amstorage = true;          // on-disk key type != indexed type (compress)
    amroutine->amclusterable = true;
    amroutine->ampredlocks = true;        // SERIALIZABLE predicate locking supported
    amroutine->amcanparallel = false;
    amroutine->amcaninclude = true;       // INCLUDE columns
    // ... method pointers ...
    amroutine->ambuild = gistbuild;
    amroutine->aminsert = gistinsert;
    amroutine->ambulkdelete = gistbulkdelete;
    amroutine->amgettuple = gistgettuple;
    amroutine->amgetbitmap = gistgetbitmap;
    amroutine->amcanreturn = gistcanreturn;     // index-only scans (if Fetch defined)
    amroutine->amtranslatecmptype = gisttranslatecmptype;
    PG_RETURN_POINTER(amroutine);
}

핵심 플래그 두 개를 보면, amcanorder = false는 GiST 키에 전체 순서가 없으므로 GiST 인덱스가 평범한 ORDER BY col을 절대 만족할 수 없음을 뜻한다. amcanorderbyop = true는 Distance 지원 함수가 하한 메트릭을 제공하므로 ORDER BY col <-> point(최근접 이웃 연산자)는 만족할 수 있음을 뜻한다. amstorage = true는 Compress를 반영한다. 저장된 키 타입이 인덱싱된 타입과 다를 수 있다. amsupport = GISTNProcs(12)는 opclass가 채울 수 있는 지원 함수 배열 크기다.

Opclass 캐싱: GISTSTATE

GiST 인덱스에 대한 모든 연산은 GISTSTATE 위에서 실행된다. GISTSTATE는 initGISTstate가 한 번 구축하고 IndexInfo->ii_AmCache에 저장하는 지원 함수 FmgrInfo의 문(statement)당 캐시다.

// initGISTstate — src/backend/access/gist/gist.c
for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(index); i++)
{
    fmgr_info_copy(&(giststate->consistentFn[i]),
                   index_getprocinfo(index, i + 1, GIST_CONSISTENT_PROC), scanCxt);
    fmgr_info_copy(&(giststate->unionFn[i]),
                   index_getprocinfo(index, i + 1, GIST_UNION_PROC), scanCxt);

    /* opclasses are not required to provide a Compress method */
    if (OidIsValid(index_getprocid(index, i + 1, GIST_COMPRESS_PROC)))
        fmgr_info_copy(&(giststate->compressFn[i]), ... , scanCxt);
    else
        giststate->compressFn[i].fn_oid = InvalidOid;
    // ... penalty, picksplit, equal are mandatory; decompress/distance/fetch optional ...
}

consistent, union, penalty, picksplit, equal은 필수다. compress, decompress, distance, fetch는 선택 사항이며 OidIsValid로 감지하고, 없으면 InvalidOid로 남긴다. nonLeafTupdesc는 INCLUDE 컬럼 없이 키 컬럼만 있는 인덱스 튜플 디스크립터의 잘린 복사본으로, 다운링크(내부) 튜플을 형성할 때 사용된다. 내부 키는 키 컬럼만 운반하고 페이로드는 포함하지 않는다.

두 가지 키 형태: 리프 항목 vs. 다운링크

GiST 리프 IndexTuple은 힙 행 하나에 대한 (Compress된 가능성이 있는) 키를 저장하며, t_tid가 힙 튜플을 가리킨다. 내부 IndexTuple은 union 키—자식 페이지의 경계 술어—를 저장하며, t_tid가 자식 블록 번호를 담는다. Consistent 함수는 리프 항목(정확한 객체)을 보는지 내부 항목(경계 술어)을 보는지 알려주는 플래그와 함께 호출된다. “쿼리가 이 박스와 겹치는가”는 양쪽 모두에 물어보지만 답의 의미가 다르기 때문이다.

최소 penalty로 하강하며 다운링크 조정

gistdoinsert는 한 번에 페이지 하나를 잡으며 루트에서 내려간다. 각 내부 페이지에서 gistchoose를 호출해 모든 다운링크의 penaltyFn을 평가하고, 최소 penalty의 오프셋을 반환한다(동점은 공간/캐시 균형을 위해 약간의 무작위화로 처리). 재귀하기 전에 선택된 다운링크가 새 키를 이미 포함하는지 확인하고, 그렇지 않으면 제자리에서 확장한다.

// gistdoinsert — src/backend/access/gist/gist.c (internal-page case)
downlinkoffnum = gistchoose(state.r, stack->page, itup, giststate);
iid = PageGetItemId(stack->page, downlinkoffnum);
idxtuple = (IndexTuple) PageGetItem(stack->page, iid);
childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));

/* Does the child's downlink already cover the key we're inserting? */
newtup = gistgetadjusted(state.r, idxtuple, itup, giststate);
if (newtup)
{
    /* No: enlarge the downlink in place (may itself split this page). */
    if (gistinserttuple(&state, stack, giststate, newtup, downlinkoffnum))
    {
        /* the parent split; retry from the parent */
    }
}

gistgetadjusted는 unionFn을 호출해 union(이전 다운링크, 새 키)를 계산하고, equalFn으로 union이 실제로 변경됐는지 확인한다. 다운링크가 이미 키를 포함하면 NULL을 반환해 갱신을 건너뛴다. 하강 중에 실행되므로, 리프에 도달하면 모든 조상이 새 항목을 포함한다. README가 강조하는 단일 패스 속성이다.

서브트리 선택: gistchoose / gistpenalty

// gistpenalty — src/backend/access/gist/gistutil.c
float
gistpenalty(GISTSTATE *giststate, int attno,
            GISTENTRY *orig, bool isNullOrig,
            GISTENTRY *add, bool isNullAdd)
{
    float penalty = 0.0;
    if (giststate->penaltyFn[attno].fn_strict == false ||
        (isNullOrig == false && isNullAdd == false))
    {
        FunctionCall3Coll(&giststate->penaltyFn[attno],
                          giststate->supportCollation[attno],
                          PointerGetDatum(orig), PointerGetDatum(add),
                          PointerGetDatum(&penalty));
        if (isnan(penalty) || penalty < 0.0)   // sanitize a misbehaving opclass
            penalty = 0.0;
    }
    else if (isNullOrig && isNullAdd)
        penalty = 0.0;
    else
        penalty = get_float4_infinity();        // avoid mixing null and non-null
    return penalty;
}

box_ops에서 penalty는 경계 박스의 면적 증가다. gistchoose는 가장 작은 확장을 가진 다운링크를 선택하며, 다중 컬럼 인덱스에서는 앞쪽 컬럼이 우선한다.

NSN, right-link, F_FOLLOW_RIGHT 플래그

페이지 헤더의 불투명 영역이 동시성 메커니즘을 담는다.

// gist.h — page flags, NSN type, and accessors
#define F_LEAF          (1 << 0)    /* leaf page */
#define F_DELETED       (1 << 1)    /* the page has been deleted */
#define F_FOLLOW_RIGHT  (1 << 3)    /* page to the right has no downlink */

typedef XLogRecPtr GistNSN;         /* node sequence number == a special LSN */

#define GistFollowRight(page)   (GistPageGetOpaque(page)->flags & F_FOLLOW_RIGHT)
#define GistPageGetNSN(page)    (PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn))
#define GistPageSetNSN(page, val) (PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val))

GistNSN은 문자 그대로 XLogRecPtr이다. 자식의 NSN은 부모에 다운링크를 삽입한 WAL 레코드의 LSN으로 설정된다. 검색은 “기억한 부모 LSN”과 “이 자식의 NSN”을 비교한다. NSN이 더 크면, 내가 부모를 읽은 후 분할됐으므로 right-link를 추적해야 한다. B-트리의 high key 테스트를 순서 없이 대체하는 방법이다.

페어링 힙을 이용한 프론티어 순회로서의 검색

술어가 겹치므로 검색은 단일 하강이 아니다. gistgettuple이 큐에 루트를 넣고 항목을 꺼낸다. gistScanPage는 한 페이지를 스캔하고, 각 항목에 Consistent를 실행하며, 일치하는 자식(k-NN의 경우 거리와 함께 힙 튜플도 포함)을 큐에 다시 넣는다. 평범한 스캔에서는 큐가 힙 튜플을 앞에 놓아 깊이 우선, LIMIT 친화적 출력을 낸다. ORDER BY <-> 스캔에서는 pairingheap이 거리 순으로 큐를 정렬하므로 가장 가까운 튜플이 항상 먼저 나온다.

flowchart TD
  A["gistgettuple<br/>(root pushed to queue)"] --> B{"pull next<br/>queue item"}
  B -->|"heap tuple"| C["return heapPtr<br/>(recheck if lossy)"]
  B -->|"index page"| D["gistScanPage(page)"]
  D --> E{"NSN > remembered<br/>parent LSN?"}
  E -->|"yes: concurrent split"| F["push right sibling<br/>to front of queue"]
  E -->|"no"| G["scan entries"]
  F --> G
  G --> H{"Consistent(entry, query)?"}
  H -->|"false"| I["skip subtree"]
  H -->|"true, leaf"| J["enqueue heap tuple<br/>(+ distance for k-NN)"]
  H -->|"true, internal"| K["enqueue child page<br/>(remember this page's LSN)"]
  J --> B
  K --> B
  I --> B
  C --> B

이것은 nbtree와 같은 “한 번에 페이지 하나 잠금, 동시 분할 시 right-link 추적” 관용구다. 겹침 모델로 인한 세 가지 차이가 있다. 하강이 포인터가 아닌 큐이고, 분할 신호가 high key가 아닌 NSN이며, 가지치기가 키 비교가 아닌 사용자 함수 호출이다.

소스 코드 가이드

이 섹션은 gist.c, gistget.c, gistsplit.c, gistbuild.c의 호출 흐름을 안정적인 심볼 이름에 고정해 추적한다. 줄 번호는 끝의 위치 힌트 테이블에만 있다.

지원 함수 계약 (`gist.c`, `gist.h`)

12개의 지원 프로시저 번호는 gist.h의 매크로다. GIST_CONSISTENT_PROC(1)부터 GIST_SORTSUPPORT_PROC(11), GIST_OPTIONS_PROC(10)이며, GISTNProcs = 12다. gisthandler가 AM을 노출하고, initGISTstate가 각 프로시저의 OID를 FmgrInfo로 해석해 GISTSTATE에 캐싱하며, 없는 선택적 프로시저는 InvalidOid로 표시한다. gistvalidate(여기서는 인용하지 않음)는 CREATE OPERATOR CLASS가 opclass의 일관성을 검사하기 위해 실행하는 amvalidate 훅이다.

Consistent 함수는 gistindex_keytest에서 호출되며, 모든 스캔의 문자 그대로의 가지치기 게이트다.

// gistindex_keytest — src/backend/access/gist/gistget.c
recheck = true;     // safest assumption if Consistent forgets to set it
test = FunctionCall5Coll(&key->sk_func, key->sk_collation,
                         PointerGetDatum(&de),        // index datum as GISTENTRY*
                         key->sk_argument,            // the query value
                         Int16GetDatum(key->sk_strategy),
                         ObjectIdGetDatum(key->sk_subtype),
                         PointerGetDatum(&recheck));
if (!DatumGetBool(test))
    return false;          // provably disjoint: prune this entry/subtree
*recheck_p |= recheck;     // lossy match: caller must recheck against heap

두 가지 미묘한 점이 있다. 첫째, recheck: 손실 opclass(예: pg_trgm, 또는 다각형의 경계 박스를 저장한 Compress)는 recheck = true로 true를 반환한다. “일치할 수 있으니 실제 힙 값으로 확인하라”는 의미다. 실행기가 힙 튜플에 원래 연산자를 직접 재평가한다. 둘째, NULL 처리: 내부 페이지에서 NULL 키는 서브트리가 null이 없음을 증명할 수 없으므로(union(VAL, NULL) = VAL이 GiST 규칙), SK_SEARCHNULL은 리프 페이지에서만 가지치기한다. README의 NULL 안전성 보장이 코드로 표현된 지점이다.

삽입: `gistinsert` → `gistdoinsert` → `gistplacetopage`

gistinsert는 얇은 래퍼다. GISTSTATE를 지연 구성하고, gistFormTuple로 리프 IndexTuple을 형성하며(Compress 실행), t_tid에 힙 CTID를 찍고, gistdoinsert를 호출한다. gistdoinsert는 하강 엔진이다. GIST_ROOT_BLKNO에서 시작해 낙관적으로 공유 잠금을 잡고, 각 페이지에서 순서대로 (a) 복구할 불완전 분할, (b) 부모에서 재시도할 동시 분할/삭제, (c) 리프 vs. 내부를 확인한다.

// gistdoinsert — src/backend/access/gist/gist.c (concurrency checks)
/* (a) crashed mid-split? finish it before touching the page. */
if (GistFollowRight(stack->page))
{
    gistfixsplit(&state, giststate);
    state.stack = stack = stack->parent;     // retry from parent
    continue;
}
/* (b) page split or was deleted since we read its parent downlink? */
if ((stack->blkno != GIST_ROOT_BLKNO &&
     stack->parent->lsn < GistPageGetNSN(stack->page)) ||
    GistPageIsDeleted(stack->page))
{
    state.stack = stack = stack->parent;     // rechoose best child
    continue;
}

리프에 도달하면 gistinserttuple/gistinserttuples가 핵심 함수 gistplacetopage를 호출한다. 튜플을 페이지에 맞추거나 분할한다. 분할 경로가 opclass PickSplit과 WAL 원자 분해가 만나는 곳이다.

// gistplacetopage — src/backend/access/gist/gist.c (split path)
is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
if (is_split && GistPageIsLeaf(page) && GistPageHasGarbage(page))
{
    gistprunepage(rel, page, buffer, heapRel);   // reclaim LP_DEAD first
    is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
}
if (is_split)
{
    itvec = gistextractpage(page, &tlen);          // all existing tuples
    itvec = gistjoinvector(itvec, &tlen, itup, ntup);
    dist  = gistSplit(rel, page, itvec, tlen, giststate);   // calls PickSplit
    if (npage > GIST_MAX_SPLIT_PAGES)
        elog(ERROR, "GiST page split into too many halves (%d, maximum %d)", ...);
    // ... allocate buffers, distribute tuples, set rightlinks ...
}

순서가 중요하다. GiST는 분할 전에 죽은 튜플을 먼저 제거(gistprunepage, LP_DEAD 회수)한다. nbtree가 분할 전에 삭제-또는-중복 제거하는 것과 같다. GIST_MAX_SPLIT_PAGES 가드도 눈여겨볼 지점이다. 키가 가변 길이이고 PickSplit에 크기 정보가 없으므로, 하나의 분할이 두 페이지 이상을 생성해야 할 수 있다. gistSplit의 재귀가 이를 처리한다.

분할 연결과 F_FOLLOW_RIGHT / NSN 프로토콜

PickSplit이 분할을 결정한 후, gistplacetopage는 새 페이지를 right-link 체인으로 연결하고 가장 오른쪽이 아닌 모든 페이지에 플래그를 세운다.

// gistplacetopage — src/backend/access/gist/gist.c (linking + flagging)
/* Set up rightlinks */
if (ptr->next && ptr->block.blkno != GIST_ROOT_BLKNO)
    GistPageGetOpaque(ptr->page)->rightlink = ptr->next->block.blkno;
else
    GistPageGetOpaque(ptr->page)->rightlink = oldrlink;   // tail keeps old rightlink

/* Flag all but the rightmost: "my right sibling has no parent downlink yet" */
if (ptr->next && !is_rootsplit && markfollowright)
    GistMarkFollowRight(ptr->page);
else
    GistClearFollowRight(ptr->page);

/* Copy the original page's NSN to every fragment so scans chase rightlinks */
GistPageSetNSN(ptr->page, oldnsn);

이것이 분할의 1단계다. 새 기하 구조가 내구성 있고 검색 가능하다(F_FOLLOW_RIGHT가 설정돼 있으므로 독자가 right-link를 추적한다). 부모에는 아직 새 페이지의 다운링크가 없다. gistplacetopage는 *splitinfo에 새 다운링크 튜플을 담아 호출자에게 반환한다. 2단계는 gistfinishsplit이다. 부모에 다운링크를 올리고(부모 자체가 분할되면 재귀), 각 자식의 NSN을 다운링크 삽입 레코드의 LSN으로 설정하며 F_FOLLOW_RIGHT를 지운다. 두 단계 사이에 충돌이 발생하면, 검색이 올바르게 순회하고 다음 하강이 gistfixsplit으로 복구한다.

flowchart TD
  A["gistplacetopage:<br/>page full"] --> B["gistSplit ->gistSplitByKey<br/>(opclass PickSplit)"]
  B --> C["allocate right pages,<br/>distribute tuples"]
  C --> D["set rightlinks,<br/>GistMarkFollowRight,<br/>copy NSN — STEP 1"]
  D --> E["XLogInsert split record<br/>(WAL-atomic)"]
  E --> F["return *splitinfo<br/>(new downlinks) to caller"]
  F --> G["gistfinishsplit:<br/>post downlinks to parent"]
  G --> H{"parent full?"}
  H -->|"yes"| A
  H -->|"no"| I["set child NSN = downlink LSN,<br/>GistClearFollowRight — STEP 2"]
  I --> J["split complete"]
  D -.->|"crash here"| K["F_FOLLOW_RIGHT left set;<br/>next descent calls<br/>gistfixsplit to repair"]

이동된 부모 재탐색: `gistFindCorrectParent` / `gistFindPath`

위쪽으로 다운링크를 삽입하는 과정에서, 하강 스택에 기록된 부모 페이지가 분할돼 오른쪽으로 이동했을 수 있다. gistFindCorrectParent는 하강 이후 부모의 LSN이 변경됐는지 확인한다. 변경됐으면 부모 레벨의 right-link를 따라가며 자식의 다운링크를 가진 페이지를 탐색하고, right-link 탐색이 불충분하면 README의 findPath 의사 코드를 따르는 루트에서의 너비 우선 재탐색인 gistFindPath로 폴백한다. nbtree의 _bt_getstackbuf에 해당하는 GiST 구현이다.

PickSplit과 다중 컬럼 / 보조 분할 메커니즘

gistSplit(재귀 분할기)은 gistSplitByKey를 호출해 어느 컬럼에서 분할할지 결정하고, gistUserPicksplit이 사용자 PickSplit을 직접 호출한다.

// gistUserPicksplit — src/backend/access/gist/gistsplit.c
FunctionCall2Coll(&giststate->picksplitFn[attno],
                  giststate->supportCollation[attno],
                  PointerGetDatum(entryvec),   // entries to partition
                  PointerGetDatum(sv));        // GIST_SPLITVEC out-param
if (sv->spl_nleft == 0 || sv->spl_nright == 0)
{
    /* opclass PickSplit put everything on one side: complain, then cope */
    ereport(DEBUG1, (errmsg("picksplit method for column %d of index \"%s\" failed", ...)));
    genericPickSplit(giststate, entryvec, sv, attno);   // fall back to a 50/50 split
}

여러 견고성 레이어가 보인다. 모든 항목을 한쪽에 넣는 퇴화 PickSplit을 잡아 genericPickSplit(크기 균등 이분)으로 교체한다. 버그 있는 opclass가 느리지만 올바른 인덱스를 만들 수 있도록 한다. 다중 컬럼 GiST에서 gistSplitByKey는 재귀한다. 컬럼 0에서의 분할이 왼쪽·오른쪽 union 키를 동등하게 남기면(gistKeyIsEQ) 그 컬럼에서의 분할이 무의미하다. findDontCares로 무관 튜플(어느 쪽에 배치해도 무방한 튜플)을 식별하고 다음 컬럼에서 재분할한다. README의 “보조 분할”이다. NULL 키는 한쪽으로 몰아 페이지가 NULL과 비-NULL 키를 섞지 않도록 한다. union(VAL, NULL) = VAL 불변식을 보존하기 위해서다. 재귀 후 gistunionsubkey가 모든 컬럼의 왼쪽/오른쪽 union 데이텀을 재계산해 두 새 다운링크가 페이지를 올바르게 경계 짓도록 한다.

검색: `gistgettuple`, `gistgetbitmap`, k-NN

gistgettuple이 순서 있는 스캔과 평범한 스캔을 구동하고, gistgetbitmap이 비트맵 스캔을 구동한다. 양쪽 모두 앞서 보인 gistScanPage를 경유한다. k-NN 경로가 독특하다. gistindex_keytest가 각 ORDER BY x <-> q 절의 Distance 지원 함수도 평가해, 힙 항목에는 정확한 거리를, 내부 항목에는 하한 거리를 부여한다. pairingheap이 큐를 거리 순으로 정렬하므로 힙 순서로 항목을 꺼내면 증가하는 실제 거리 순으로 튜플이 나온다. 전체 결과를 구체화하거나 정렬할 필요 없이 증분 최근접 이웃 스캔이 된다. Distance가 recheck 플래그를 설정하면 거리가 하한에 불과하므로 실행기가 정확한 값으로 재정렬한다.

gistgettuple은 지연 죽은 튜플 표시도 수행한다. 실행기가 kill_prior_tuple을 보고하면 오프셋이 so->killedItems에 저장되고, 나중에 gistkillitems가 플러시해 인덱스 항목에 LP_DEAD를 설정한다. nbtree의 _bt_killitems와 같은 힌트 비트 회수 계층이다.

빌드: `gistbuild`의 세 가지 전략

gistbuild는 앞에서 세 전략 중 하나를 선택한다.

// gistbuild — src/backend/access/gist/gistbuild.c (strategy selection)
if (options && options->buffering_mode == GIST_OPTION_BUFFERING_ON)
    buildstate.buildMode = GIST_BUFFERING_STATS;       // forced buffering
else
    buildstate.buildMode = GIST_BUFFERING_AUTO;        // decide later

if (buildstate.buildMode != GIST_BUFFERING_STATS)
{
    /* Use the sorted build if EVERY key column has a sortsupport proc. */
    bool hasallsortsupports = true;
    for (int i = 0; i < keyscount; i++)
        if (!OidIsValid(index_getprocid(index, i + 1, GIST_SORTSUPPORT_PROC)))
            { hasallsortsupports = false; break; }
    if (hasallsortsupports)
        buildstate.buildMode = GIST_SORTED_BUILD;
}

정렬 빌드(GIST_SORTED_BUILD): 모든 키 컬럼의 opclass가 GIST_SORTSUPPORT_PROC를 제공할 때 선택된다. 힙을 tuplesort(tuplesort_begin_index_gist)로 스캔해 opclass의 선형화(포인트의 경우 보통 공간 충전 곡선)로 정렬한다. gist_indexsortbuild가 리프를 바텀업으로 채우고 각 부모 레벨을 아래 레벨에서 구성한다. B-트리 스타일 바텀업 빌드다. point_ops와 PostGIS의 현대적 기본값으로 가장 빠른 경로다.
버퍼링 빌드(GIST_BUFFERING_ACTIVE): SortSupport가 없는 opclass에서 인덱스가 effective_cache_size를 초과하면 사용된다. gistbuild가 평범한 삽입 모드로 시작해, gistBuildCallback에서 인덱스 크기를 감시하고, 캐시에 더 이상 맞지 않으면 gistInitBuffering으로 전환한다. 내부 노드에 붙은 버퍼(GISTBuildBuffers)가 들어오는 튜플을 흡수한다. gistProcessEmptyingQueue가 절반 찬 버퍼를 한 레벨씩 플러시해 무작위 하강을 캐시 크기의 너비 우선 배치로 변환한다(Arge et al.).
평범한 삽입 빌드: 폴백이다. gistBuildCallback이 힙 튜플마다 gistdoinsert를 직접 호출한다. 런타임 삽입과 동일하지만 WAL을 건너뛴다(is_build = true, 페이지에 GistBuildLSN 찍음).

// gistBuildCallback — src/backend/access/gist/gistbuild.c (per-heap-tuple)
itup = gistFormTuple(buildstate->giststate, index, values, isnull, true);
itup->t_tid = *tid;
if (buildstate->buildMode == GIST_BUFFERING_ACTIVE)
    gistBufferingBuildInsert(buildstate, itup);     // push into node buffers
else
    gistdoinsert(index, itup, buildstate->freespace,
                 buildstate->giststate, buildstate->heaprel, true);  // direct

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

심볼	파일	줄
`gisthandler`	src/backend/access/gist/gist.c	59
`gistinsert`	src/backend/access/gist/gist.c	165
`gistplacetopage`	src/backend/access/gist/gist.c	230
`gistdoinsert`	src/backend/access/gist/gist.c	639
`gistFindPath`	src/backend/access/gist/gist.c	914
`gistFindCorrectParent`	src/backend/access/gist/gist.c	1027
`gistformdownlink`	src/backend/access/gist/gist.c	1140
`gistfixsplit`	src/backend/access/gist/gist.c	1200
`gistinserttuple`	src/backend/access/gist/gist.c	1260
`gistSplit`	src/backend/access/gist/gist.c	1466
`initGISTstate`	src/backend/access/gist/gist.c	1537
`gistindex_keytest`	src/backend/access/gist/gistget.c	125
`gistScanPage`	src/backend/access/gist/gistget.c	328
`gistkillitems`	src/backend/access/gist/gistget.c	38
`gistgettuple`	src/backend/access/gist/gistget.c	612
`gistgetbitmap`	src/backend/access/gist/gistget.c	745
`gistcanreturn`	src/backend/access/gist/gistget.c	797
`gistunionsubkey`	src/backend/access/gist/gistsplit.c	80
`findDontCares`	src/backend/access/gist/gistsplit.c	113
`supportSecondarySplit`	src/backend/access/gist/gistsplit.c	258
`genericPickSplit`	src/backend/access/gist/gistsplit.c	344
`gistUserPicksplit`	src/backend/access/gist/gistsplit.c	415
`gistSplitHalf`	src/backend/access/gist/gistsplit.c	585
`gistSplitByKey`	src/backend/access/gist/gistsplit.c	623
`gistbuild`	src/backend/access/gist/gistbuild.c	179
`gist_indexsortbuild`	src/backend/access/gist/gistbuild.c	400
`gistInitBuffering`	src/backend/access/gist/gistbuild.c	626
`gistBuildCallback`	src/backend/access/gist/gistbuild.c	822
`gistProcessItup`	src/backend/access/gist/gistbuild.c	925
`gistbufferinginserttuples`	src/backend/access/gist/gistbuild.c	1056
`gistchoose`	src/backend/access/gist/gistutil.c	374
`gistpenalty`	src/backend/access/gist/gistutil.c	724
`gistMakeUnionItVec`	src/backend/access/gist/gistutil.c	155
`gistdentryinit`	src/backend/access/gist/gistutil.c	547
`gistFetchTuple`	src/backend/access/gist/gistutil.c	667
`GIST_CONSISTENT_PROC`..`GISTNProcs`	src/include/access/gist.h	32–44
`F_LEAF` / `F_DELETED` / `F_FOLLOW_RIGHT`	src/include/access/gist.h	49–53
`GistNSN` / `GistBuildLSN`	src/include/access/gist.h	65 / 72
`GistFollowRight` / `GistPageGetNSN`	src/include/access/gist.h	185 / 189
`GISTSTATE` (지원 FmgrInfo 캐시)	src/include/access/gist_private.h	75

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

아래 모든 사항은 커밋 273fe94의 REL_18_STABLE 작업 트리에서 검증했다.

12개 지원 프로시저, GISTNProcs == 12. src/include/access/gist.h 검증: GIST_CONSISTENT_PROC(1)부터 GIST_SORTSUPPORT_PROC(11), GIST_OPTIONS_PROC(10), #define GISTNProcs 12. gisthandler가 amsupport = GISTNProcs를 설정한다.
amcanorder = false, amcanorderbyop = true. gisthandler에서 문자 그대로 검증. GiST는 ORDER BY col을 만족할 수 없지만 Distance 프로시저로 ORDER BY col <-> q는 만족할 수 있다.
필수 vs. 선택 프로시저. initGISTstate가 consistentFn, unionFn, penaltyFn, picksplitFn, equalFn을 무조건 복사한다. compressFn, decompressFn, distanceFn, fetchFn은 OidIsValid(index_getprocid(...))로 보호되며 없으면 InvalidOid로 남긴다.
GistNSN이 XLogRecPtr임. gist.h에서 typedef XLogRecPtr GistNSN; 검증. gistdoinsert의 분할 감지기 stack->parent->lsn < GistPageGetNSN(...)과 gistScanPage의 대칭 테스트 모두 기억된 부모 LSN을 자식 NSN과 비교한다.
F_FOLLOW_RIGHT 생명 주기. gistplacetopage가 가장 오른쪽이 아닌 분할 조각에 GistMarkFollowRight를 호출한다(1단계). gistfinishsplit/다운링크 삽입이 지우고 NSN을 설정한다(2단계). gistdoinsert와 gistScanPage 모두 이를 준수한다. gistfixsplit이 충돌로 플래그가 남은 페이지를 복구한다. gist.c/gistget.c에서 모두 검증.
분할 전 가비지 제거. gistplacetopage가 분할 결정 전에 gistprunepage를 호출해 GistPageHasGarbage LP_DEAD 튜플을 회수한다. 분할 경로에서 검증.
GIST_MAX_SPLIT_PAGES 가드. gistplacetopage가 elog(ERROR, "GiST page split into too many halves ...") 발생시킨다. 검증 완료. 키가 가변 길이이므로 하나의 분할이 합법적으로 두 페이지 이상을 생성할 수 있다.
퇴화 PickSplit 폴백. gistUserPicksplit이 opclass가 빈 쪽을 반환하면 genericPickSplit으로 폴백하고 DEBUG1 “picksplit method … failed”를 내보낸다. gistsplit.c에서 검증.
다중 컬럼 보조 분할. gistSplitByKey가 퇴화 분할 시 다음 컬럼으로 재귀해 findDontCares를 사용하고 gistunionsubkey로 union을 재계산한다. 검증 완료.
세 가지 빌드 전략. gistbuild가 모든 키 컬럼에 GIST_SORTSUPPORT_PROC가 있으면 GIST_SORTED_BUILD를 선택한다. 없으면 gistInitBuffering으로 버퍼링(GIST_BUFFERING_AUTO/ACTIVE) 또는 gistBuildCallback → gistdoinsert로 평범한 삽입이다. 검증 완료.
술어 잠금 / SERIALIZABLE. gistScanPage가 PredicateLockPage를 호출하고, gisthandler가 ampredlocks = true를 설정한다. 검증 완료.
페어링 힙을 이용한 k-NN. gistgettuple이 numberOfOrderBys > 0을 getNextNearest로 라우팅한다. gistScanPage가 Distance 프로시저 결과로 정렬된 pairingheap인 so->queue에 항목을 넣는다. 검증 완료.
병렬 스캔/빌드 없음. gisthandler가 REL_18에서 amcanparallel = false와 amcanbuildparallel = false를 설정한다. 검증 완료. (병렬 빌드를 지원하는 nbtree/BRIN과 구별되는 점.)

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

GiST 1995 vs. 프로덕션 구현. Hellerstein, Naughton & Pfeffer의 논문은 인터페이스(Consistent / Union / Penalty / PickSplit, 검색·삽입 템플릿)를 명세하지만 동시성·복구·대량 적재에 대해서는 침묵한다. 원본 버클리 프로토타입(Hellerstein & Aoki, README 주석)은 단일 사용자 “대학 프로젝트”였다. PostgreSQL GiST를 프로덕션 인덱스로 만드는 모든 것—NSN + right-link 프로토콜, 두 단계 WAL 원자 분할, gistfixsplit 지연 복구, 버퍼링 빌드—은 1995년 논문 바깥에 있다. 각 프로덕션 메커니즘을 논문이 미처 명세하지 않아 새로 발명해야 했던 보장으로 매핑하면 “B-트리를 일반화한다”는 말이 무엇을 미명세 상태로 남기는지 명확해진다. 논문: Hellerstein/Naughton/Pfeffer 1995 (README 기초 참조).
NSN 동시성 vs. Lehman & Yao의 high key. GiST의 분할 감지 신호는 Kornacker의 NSN, 즉 명시적인 페이지당 시퀀스 번호다. 겹침 트리에 “오른쪽 이동”의 근거가 되는 high key가 없기 때문이다(postgres-nbtree.md는 high key 테스트를 사용). 두 프로토콜은 동형이다—한 번에 페이지 하나 래치, 동시 분할 시 right-link 추적, 불완전 분할 지연 복구—하지만 GiST는 nbtree가 이미 저장하는 구분 키를 재사용하는 대신 페이지당 8바이트 NSN을 지불한다. _bt_moveright(키 비교)와 gistScanPage의 parentlsn < GistPageGetNSN 테스트를 나란히 놓으면 “순서 없는 B-link 트리”의 비용이 가장 명확하게 보인다. 논문: Kornacker, “Access Methods for Next-Generation Database Systems” (README 동시성 참조).
R-트리 휴리스틱은 전적으로 opclass에 있다. Guttman의 2차·선형 분할과 R*-트리의 마진 최소화 분할·강제 재삽입은 gistsplit.c에 없다. box_ops/point_ops PickSplit이 선택할 수 있는 것들이다. PostgreSQL의 인코어 기하 PickSplit은 Guttman 스타일 이중 정렬이다. R*-트리의 강제 재삽입은 구현되지 않았다(GiST는 넘친 페이지의 항목을 재삽입하지 않는다). R*-트리 스타일 재삽입이나 Hilbert/Z-order 선형화로 분할을 사용하는 opclass는 프레임워크가 허용하지만 제공하지 않는 미실현 품질 개선이다. 논문: Beckmann, Kriegel, Schneider & Seeger 1990, R*-트리 (dbms-papers/rstar-tree.md).
버퍼링 빌드 vs. 정렬 빌드 vs. STR 대량 적재. PostgreSQL의 두 고속 빌드는 대량 적재 문헌의 양 끝을 포괄한다. 정렬 빌드(GIST_SORTED_BUILD, SortSupport 조건)는 공간 충전 곡선 선형화에서 공간 트리의 Sort-Tile-Recursive(STR) 대량 적재에 근접하는 GiST 판 바텀업 B-트리 패킹이다. 버퍼링 빌드는 선형화가 불가능한 opclass를 위한 Arge/Hinrichs/Vahrenhold/Vitter의 캐시 인식 알고리즘이다. 전환 지점—버퍼링이 평범한 삽입을 이기는 시점—은 gistInitBuffering이 감시하는 effective_cache_size 임계값이다. GiST의 휴리스틱 전환과 STR의 일회성 타일링을 비교하면 “한 번 정렬, 바텀업 패킹”이 “버퍼링·배치”를 이기는 조건이 드러난다. 논문: Arge et al., “Efficient Bulk Operations on Dynamic R-trees” (README 빌드 참조).
GiST vs. SP-GiST vs. BRIN — “전체 순서 없음”에 대한 세 가지 답. GiST는 균형, 겹침-경계-술어 답이다. SP-GiST(postgres-spgist.md)는 공간 분할, 비겹침 답으로(쿼드트리, k-d 트리, 기수 트라이), 분할이 분리돼 포인트 쿼리가 단일 경로를 따른다. BRIN(postgres-brin.md)은 트리를 완전히 포기하고 작은 최솟값/최댓값 맵만 남기는 손실 블록 범위 요약 답이다. 셋 모두 “엔진이 골격을 소유하고 opclass가 의미론을 소유한다”는 템플릿을 공유하지만, 분할이 겹치는지(GiST: 예, SP-GiST: 아니오)와 트리가 있는지(BRIN: 아니오)가 다르다. 확장 가능 인덱스 패밀리에 대한 통합 노트가 세 문서 모두의 자연스러운 부모 문서다.
CUBRID에는 GiST 유사 기능이 없다. CUBRID는 B+-트리와 전문화된 공간 지원을 제공하지만 범용 확장 키 인덱스 프레임워크는 없다. CUBRID에서 범위·전문 검색·트라이그램 인덱스를 원하는 확장 개발자에게는 “네 개의 C 함수를 공급하라”는 경로가 없다. PostgreSQL의 opclass 플러그 가능 AM과 CUBRID의 고정 인덱스 집합을 대조하면 GiST 추상화가 생태계에 무엇을 제공하는지 가장 명확하게 드러난다. (CUBRID 인덱스 분석은 cubrid 트리 참조.)

출처

인트리 README 및 소스 파일 (REL_18_STABLE, 커밋 273fe94)

src/backend/access/gist/README — 설계 문서: GiST 인터페이스(Consistent/Union/Compress/Decompress/Penalty/PickSplit/Equal/Distance/Fetch), findPath 재탐색 의사 코드, NSN + F_FOLLOW_RIGHT 동시성 프로토콜, 불완전 분할 복구, 버퍼링 빌드, 정렬 빌드. 섹션 6에 인용된 기초 논문들 포함.
src/include/access/gist.h — GIST_CONSISTENT_PROC..GIST_SORTSUPPORT_PROC 및 GISTNProcs, F_LEAF/F_DELETED/F_FOLLOW_RIGHT 페이지 플래그, GistNSN(typedef XLogRecPtr), GistBuildLSN, GistFollowRight/GistPageGetNSN/GistPageSetNSN 접근자.
src/include/access/gist_private.h — GISTSTATE(문당 지원-FmgrInfo 캐시), GISTScanOpaque(pairingheap 큐 및 killedItems), GISTBuildBuffers, 분할/삽입 헬퍼 프로토타입.
src/backend/access/gist/gist.c — gisthandler, gistinsert, gistdoinsert, gistplacetopage, gistfinishsplit, gistfixsplit, gistFindCorrectParent, gistFindPath, gistformdownlink, gistinserttuple(s), gistSplit, initGISTstate.
src/backend/access/gist/gistget.c — gistindex_keytest(Consistent 게이트), gistScanPage, gistgettuple, gistgetbitmap, getNextNearest(k-NN), gistkillitems, gistcanreturn.
src/backend/access/gist/gistsplit.c — gistSplitByKey, gistUserPicksplit, genericPickSplit, findDontCares, supportSecondarySplit, gistunionsubkey, gistSplitHalf.
src/backend/access/gist/gistbuild.c — gistbuild(전략 선택), gist_indexsortbuild, gistInitBuffering, gistBuildCallback, gistProcessItup, gistbufferinginserttuples.
src/backend/access/gist/gistutil.c — gistchoose, gistpenalty, gistMakeUnionItVec, gistgetadjusted, gistFetchTuple, gistdentryinit.

논문 및 교과서 챕터

Hellerstein, J. M., Naughton, J. F. & Pfeffer, A. (1995). “Generalized Search Trees for Database Systems.” Proc. VLDB 1995, 562-573. GiST 인터페이스와 검색/삽입 템플릿. README 기초 참조.
Kornacker, M. “Access Methods for Next-Generation Database Systems.” PostgreSQL이 구현한 NSN + right-link 동시성 프로토콜. README 동시성 참조.
Arge, L., Hinrichs, K., Vahrenhold, J. & Vitter, J. S. “Efficient Bulk Operations on Dynamic R-trees.” 캐시 인식 버퍼링 빌드. README 빌드 참조.
Guttman, A. (1984). “R-Trees: A Dynamic Index Structure for Spatial Searching.” SIGMOD 1984, 47-57. GiST가 일반화한 겹침-MBR 트리. 배경: knowledge/research/dbms-papers/btree.md / rstar-tree.md.
Beckmann, N., Kriegel, H.-P., Schneider, R. & Seeger, B. (1990). “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles.” SIGMOD 1990, 322-331. 기하 opclass가 구현할 수 있는 분할/강제 재삽입 휴리스틱. knowledge/research/dbms-papers/rstar-tree.md 수록.
Database Internals (Petrov 2019), 2-7장 — B-트리 동시성, WAL 프레이밍, 빌드 전략을 설명하는 대량 적재 논의. (knowledge/research/dbms-general/)

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

postgres-index-am.md — gisthandler가 채우는 IndexAmRoutine 디스패치 계약 (amgettuple/amgetbitmap/ambuild/aminsert).
postgres-spgist.md — 확장 가능 인덱스 패밀리의 공간 분할, 비겹침 사촌.
postgres-brin.md — “전체 순서 없음”에 대한 손실 블록 범위 요약 답, 세 번째 확장 AM.
postgres-nbtree.md — GiST NSN의 순서-무관 적응 기반인 Lehman & Yao high key 동시성 프로토콜.
postgres-buffer-manager.md — GiST의 한 페이지씩 하강이 구축된 버퍼 핀과 콘텐츠 잠금(LWLock) 래칭.
postgres-ssi-predicate-locking.md — gistScanPage의 PredicateLockPage / CheckForSerializableConflictIn이 공급하는 술어 잠금 (ampredlocks = true).