(KO) PostgreSQL SP-GiST — 공간 분할 트리의 디스크 매핑

목차

• 이론적 배경
• DBMS 공통 설계
• PostgreSQL의 접근법
• 소스 탐방
• 소스 검증 (2026-06-05 기준)
• PostgreSQL 너머 — 비교 설계와 연구 프런티어
• 출처

이론적 배경

B-트리(postgres-nbtree.md 참고)는 키가 전순서(total order)를 갖는 경우에 맞는 인덱스다. 모든 노드가 키 공간을 연속 범위로 분할하고, 균형 유지 기계가 모든 리프를 같은 깊이에 놓는다. 그런데 유용한 전순서가 없는 데이터 타입이 많다. 2차원 점, IP 범위, 다각형 경계 박스, 문자 단위로 분해한 문자열 — 이것들의 자연스러운 인덱스는 범위 트리가 아니라 **공간 분할 트리(space-partitioning tree)**다. 공간 분할 트리는 도메인(평면, 주소 공간, 알파벳)을 재귀적으로 분리 영역으로 나누고 각 값을 그것을 포함하는 영역으로 라우팅한다. Database System Concepts(Silberschatz 7e) §24.4 “Indexing of Spatial Data”는 이 계열의 세 표준 구성원을 제시한다.

• 쿼드트리. 2차원 쿼드트리 노드는 중심(centroid) 점을 저장하고 중심 기준 사분면(NE, SE, SW, NW)마다 자식 하나씩 네 개를 가진다. 점은 자신이 속한 사분면으로 내려가며, 분할은 영역 기반이고 네 영역이 부모 영역을 완전히 타일링한다.
• k-d 트리. k-d 트리는 레벨마다 분할 차원을 교번한다. 짝수 레벨에서는 x(수직 절단선), 홀수 레벨에서는 y(수평 절단선)로 분할한다. 각 노드는 이진 — “선의 왼쪽” 대 “선의 오른쪽” — 이므로, k-d 트리는 레벨당 네 사분면 대신 두 절반으로 자르는 쿼드트리다.
• 래딕스 트리(트라이). 문자열 처리에서 트라이는 접두사 기반으로 분할한다. 노드는 공통 접두사를 나타내고 자식은 다음 문자로 구분된다. 리프의 깊이는 log N이 아니라 구별 접두사의 길이이므로, 트라이의 형태는 균형 불변식이 아닌 데이터를 따른다.

이 세 구조는 B-트리와 뚜렷하게 다른 세 가지 구조적 사실을 공유한다. 첫째, 불균형이다. 분기의 깊이는 데이터의 집중 정도에 따라 달라지며 재균형 기계가 없다. 둘째, 분할이 분리적이고 망라적이다. 값이 정확히 하나의 자식 영역에 속하므로, 삽입과 검색이 단일 경로를 내려간다(경계 박스가 겹쳐 다중 경로 검색을 강제하는 R-트리와 다르다). 셋째, 교과서 형태로는 각 노드가 자식 포인터를 담는 작은 힙 할당 레코드인 인메모리 포인터 체이싱 구조다. 백만 점에 대한 쿼드트리는 스무 레벨 깊이일 수 있고, 나이브하게 각 레벨이 포인터 역참조 하나 — 디스크에서는 레벨당 랜덤 I/O 하나 — 가 된다. 팬아웃 F로 log_F N에 근접하는 페이지 읽기 수가 핵심인 디스크 인덱스에서는 치명적이다.

SP-GiST가 해결하는 이론적 문제는 src/backend/access/spgist/README 첫머리에 명시된 매핑 문제다. “트리 노드를 디스크 페이지에 매핑해, 검색 알고리즘이 많은 논리 노드를 순회하더라도 적은 디스크 페이지만 접근하게 하는 것이 과제다.” 순수 노드-페이지 레이아웃은 4-포인터 쿼드트리 노드에 페이지 하나를 낭비하고, 순수 노드-포인터 레이아웃은 I/O를 흘리는 인메모리 구조다. SP-GiST의 답은 많은 논리 노드를 하나의 페이지에 패킹하고, 구조적으로 연결된 그룹(inner tuple 하나, leaf tuple 체인 하나)이 결코 페이지 경계를 걸치지 않게 요구하는 것이다. 논리 레벨 하나를 내려가는 것이 대개 같은 페이지에 머물고, 자식 페이지로 이동하는 것이 예외가 아닌 규칙이 되게 한다.

이름의 “GiST”가 두 번째 이야기다. GiST(Generalized Search Tree, Hellerstein-Naughton-Pfeffer 1995; postgres-gist.md 참고)는 균형, 겹침 검색 트리를 데이터 타입 불가지론적으로 만들었다. 타입별 로직을 소수의 opclass 메서드(consistent, union, penalty, picksplit)로 인수분해하고, 코어가 페이지 레이아웃·WAL·동시성을 담당한다. SP-GiST는 같은 아이디어를 공간 분할 계열에 적용한다. 코어가 디스크 매핑·redirect/placeholder 부기·래칭·WAL을 담당하고, 다섯 opclass 메서드 — config, choose, picksplit, inner_consistent, leaf_consistent — 가 쿼드트리, k-d 트리, 래딕스 트라이의 의미를 인코딩한다. PostgreSQL은 point에 point_ops(쿼드트리)와 kd_point_ops(k-d 트리), text에 text_ops(래딕스 트리), 그리고 inet_ops, range_ops, box_ops/poly를 동일한 다섯-메서드 계약으로 제공한다.

두 설계 축이 나머지 문서를 구성한다.

1. 포인터 연결 트리를 단일 경로 하강 속성을 잃지 않고 페이지에 매핑하는 방법 — inner tuple, 노드, leaf 체인이 물리적으로 무엇이고, 체인과 inner tuple이 각각 한 페이지에 위치해야 하는 규칙.
2. 다섯 opclass 메서드가 데이터 타입(사분면 또는 공통 접두사의 의미를 아는)과 코어(지오메트리나 문자열은 모르지만 페이지·락·크래시 복구는 아는) 사이의 책임을 나누는 방법.

DBMS 공통 설계

SP-GiST의 구체적인 심볼 이전에, 공간 분할 트리를 디스크에 매핑하는 모든 엔진이 수렴하는 반복 기법을 정리한다. 다음 절의 PostgreSQL 선택은 이 공간 안에서 하나의 다이얼 세트로 읽힌다.

페이지당 다수의 논리 노드 버킷팅

디스크 상주 트라이/쿼드트리가 첫 번째로 하는 조치는 “트리 노드”와 “디스크 페이지”를 동일시하는 것을 그만두는 것이다. 4-방향 쿼드트리 노드는 약 40바이트이고, 8 KB 페이지는 약 200개를 담을 수 있다. 따라서 페이지가 논리 노드의 버킷이 되고, 디스크 포인터는 원시 메모리 주소 대신 (page, offset) 쌍이 된다. I/O 한계를 작동시키는 핵심 세부 사항은 함께 방문될 가능성이 높은 노드를 동일 위치에 배치하는 것이다. SP-GiST의 규칙은 단순하고 효과적이다. inner tuple의 전체 노드 배열이 하나의 페이지에 있는 하나의 물리 tuple에 위치하고, 하나의 노드에서 도달 가능한 leaf tuple 집합이 전체 TID 대신 2바이트 offset으로 연결된 단일 페이지 체인을 이룬다. 하나의 논리 에지를 내려가는 것이 페이지 내에 머물면 무료이고, 자식 페이지를 건너야만 I/O 비용이 든다.

묘비석(tombstone)을 통한 지연적·offset 안정적 삭제

공간 분할 트리는 불편한 속성이 있다. 자식의 주소가 inner tuple의 다운링크이고, 페이지의 다른 inner tuple은 offset 번호가 안정적이어야 한다. 그것들을 향한 모든 다운링크가 깨진다. 따라서 엔진은 단순히 페이지를 압축할 수 없다. 보편적인 답은 묘비석이다. tuple이 논리적으로 사라져야 하지만 슬롯이 이동할 수 없을 때, 해당 offset을 차지하는 placeholder를 남긴다. SP-GiST는 LIVE, REDIRECT, DEAD, PLACEHOLDER 4-state 래티스로, “이동됨, 여기 새 위치” (redirect)와 “사라졌지만 여전히 참조됨” (dead)과 “사라졌고 재사용 가능” (placeholder)을 구분한다.

락-경량 동시 검색을 위한 redirect

검색이 자식을 락하기 전에 부모의 락을 해제하면(락 체인을 보유하지 않으려고), 동시 삽입이 그 창에서 자식의 내용을 다른 곳으로 이동시킬 수 있다. B-link 스타일 설계와 공유하는 고전적인 수정은 이전 위치에 포워딩 포인터를 남기는 것이다. 이동된 tuple에 도달한 스캔은 새 주소를 알려주는 redirect를 발견한다. redirect는 스냅샷이 오래된 스캔이 아직 진행 중일 수 있는 동안만 필요하고, 그 후 VACUUM이 재활용한다.

데드락을 억제하는 조건부 래치 커플링

불균형 트리에 삽입할 때 자식을 락하는 동안 부모를 락된 상태로 유지해야 하며(부모의 다운링크를 원자적으로 업데이트하려고), 두 삽입이 역순으로 교차 링크된 분기를 내려갈 때 데드락이 발생할 위험이 있다. 엔진은 전역 락 순서(데이터 의존적인 트리 형태에서 비현실적)나 조건부 락 + 재시작으로 이를 제한한다. 자식을 블로킹 없이 락하려 시도하다 실패하면 모든 것을 놓고 전체 삽입을 재시도한다. SP-GiST는 교차 링크 패턴을 통계적으로 드물게 만드는 배치 휴리스틱인 “triple parity”를 추가한다.

pending list가 있는 순차 스캔 VACUUM

아래에서 삽입이 재형성할 수 있는 트리에서 죽은 항목을 회수하는 것은 논리적으로 트리를 걸으면 어렵다. 많은 엔진이 취하는 단순한 접근법은 모든 페이지의 물리적 순차 스캔이다. 각 페이지를 정확히 한 번 방문하고 동시 형태 변경에 영향을 받지 않는다. 단 한 가지 레이스를 제외하고. 삽입이 아직 삭제되지 않은 항목을 이미 방문한 페이지에서 아직 방문하지 않은 페이지로 이동시키는 경우다. SP-GiST는 pending list로 처리한다. 스캔이 최근 생성된 redirect를 볼 때 대상을 기록하고 페이지 사이에서 재확인해, 어떤 대상 TID도 삭제를 피할 수 없게 한다.

flowchart TB
  subgraph Logical["논리적 공간 분할 트리"]
    R["inner: centroid c0<br/>nodes: NE SE SW NW"]
    A["inner: centroid c1<br/>nodes ..."]
    L1["leaf chain:<br/>pt, pt, pt"]
    L2["leaf chain:<br/>pt, pt"]
    R -->|NE| A
    R -->|SE| L1
    A -->|SW| L2
  end
  subgraph Physical["물리적 페이지 매핑"]
    P1["inner page 1<br/>tuple R (4 nodes)<br/>tuple A (4 nodes)"]
    P2["leaf page 5<br/>chain L1: off3->off7->0"]
    P3["leaf page 9<br/>chain L2: off2->off4->0"]
    P1 -.->|"downlink TID (5,3)"| P2
    P1 -.->|"downlink TID (9,2)"| P3
  end

PostgreSQL의 접근법

PostgreSQL의 SP-GiST는 Teodor Sigaev와 Oleg Bartunov가 작성한, README에 기술된 매핑의 충실하고 신중한 구현이다. access-method 핸들러 spghandler는 다섯 개의 핵심 진입점을 일반 index-AM 디스패치 테이블에 연결한다(postgres-index-am.md가 그 계약을 다룬다). amcanorderbyop = true(SP-GiST는 nearest-neighbor 정렬 스캔을 지원), amsearchnulls = true, amcaninclude = true, amsupport = SPGISTNProc(지원 프로시저 7개)에 주목한다.

// spghandler — src/backend/access/spgist/spgutils.c
amroutine->amsupport = SPGISTNProc;          /* 7 support procs */
amroutine->amcanorderbyop = true;            /* kNN ordered scan */
amroutine->amsearchnulls = true;             /* IS NULL via nulls tree */
amroutine->amcaninclude = true;              /* INCLUDE columns */
amroutine->ambuild = spgbuild;
amroutine->aminsert = spginsert;
amroutine->ambulkdelete = spgbulkdelete;
amroutine->amgettuple = spggettuple;
amroutine->amgetbitmap = spggetbitmap;
amroutine->amcanreturn = spgcanreturn;       /* index-only scans */

두 물리 tuple 타입

디스크의 모든 것은 두 실제 tuple 형태(더하기 dead-tuple 오버레이) 중 하나다. inner tuple은 고정 헤더, 선택적 prefix datum, 압축된 node tuple 배열이다. 각 node tuple은 (label, downlink-TID) 쌍을 담는 IndexTupleData 헤더다. 비트 패킹 헤더가 형식의 핵심이다.

// SpGistInnerTupleData — src/include/access/spgist_private.h
typedef struct SpGistInnerTupleData
{
    unsigned int tupstate:2,    /* LIVE/REDIRECT/DEAD/PLACEHOLDER */
                allTheSame:1,   /* all nodes in tuple are equivalent */
                nNodes:13,      /* number of nodes within inner tuple */
                prefixSize:16;  /* size of prefix, or 0 if none */
    uint16      size;           /* total size of inner tuple */
    /* prefix datum follows, then nodes */
} SpGistInnerTupleData;

leaf tuple은 leaf datum, 그것이 인덱싱하는 heap TID, 그리고 — 결정적으로 — 같은 부모 노드 아래 같은 페이지의 다음 leaf를 체인으로 잇는 nextOffset 링크(t_info에 패킹됨)를 담는다.

// SpGistLeafTupleData — src/include/access/spgist_private.h
typedef struct SpGistLeafTupleData
{
    unsigned int tupstate:2,    /* LIVE/REDIRECT/DEAD/PLACEHOLDER */
                size:30;
    uint16      t_info;         /* nextOffset (14 bits) + flag bits */
    ItemPointerData heapPtr;    /* TID of represented heap tuple */
    /* nulls bitmap (if flagged), then leaf datum + INCLUDE datums */
} SpGistLeafTupleData;

nextOffset은 전체 6바이트 TID가 아닌 2바이트 OffsetNumber다. README의 불변식 — 체인 전체가 한 페이지에 머물러야 한다 — 이 이 설계를 올바르게 만든다. 이것이 leaf 체인을 저렴하게 만드는 불변식이다. REDIRECT/DEAD/PLACEHOLDER 슬롯은 SpGistDeadTupleData로 재해석된다. 같은 처음 두 비트에 tupstate가 alias되고, pointer/xid가 포워딩 TID와 삽입 트랜잭션을 담는다.

고정 페이지 지리와 nulls 트리

SP-GiST 릴레이션은 세 개의 고정 블록을 가진다. 메타페이지(블록 0, 매직 번호와 백엔드별 마지막-사용-페이지 캐시를 담음), 메인 트리의 루트(블록 1), nulls 트리의 루트(블록 2)다. README의 NULL 처리 규칙이 직접 구현된다. 인덱싱 연산자는 strict로 가정하므로, null은 opclass 메서드 대신 하드와이어드 로직으로 검색되는, 분리된 페이지 집합의 별도 트리에 위치한다. 삽입 경로는 키의 null 여부로 시작 블록을 선택한다.

// spgdoinsert — src/backend/access/spgist/spgdoinsert.c
current.blkno = isnull ? SPGIST_NULL_BLKNO : SPGIST_ROOT_BLKNO;

// constants — src/include/access/spgist_private.h
#define SPGIST_METAPAGE_BLKNO    (0)   /* metapage */
#define SPGIST_ROOT_BLKNO        (1)   /* root for normal entries */
#define SPGIST_NULL_BLKNO        (2)   /* root for null-value entries */
#define SPGIST_LIVE        0   /* normal live tuple */
#define SPGIST_REDIRECT    1   /* temporary redirection placeholder */
#define SPGIST_DEAD        2   /* dead, cannot be removed (still linked) */
#define SPGIST_PLACEHOLDER 3   /* placeholder to preserve offsets */

다섯 opclass 메서드

데이터 타입은 다섯 개(추가로 두 개 선택적) 지원 프로시저로 캡슐화된다. spgGetCache는 인덱스당 한 번 config를 호출하고 결과를 rd_amcache에 캐싱한다. 이것이 코어가 마샬해야 하는 네 타입 — attType(입력), attLeafType(leaf 저장), attPrefixType(inner prefix), attLabelType(node 레이블) — 과 longValuesOK(opclass가 너무 긴 leaf datum을 suffix로 줄일 수 있는가)를 선언한다. 래딕스 트리의 config가 예시다. text prefix, int2(단일 문자) 레이블, suffix 켜짐.

// spg_text_config — src/backend/access/spgist/spgtextproc.c
cfg->prefixType = TEXTOID;
cfg->labelType = INT2OID;
cfg->canReturnData = true;
cfg->longValuesOK = true;   /* suffixing will shorten long values */

삽입 시 choose가 각 inner tuple의 결정 오라클이다. 값, 현재 prefix, node 레이블을 받아 세 가지 판정 중 하나를 반환한다. spgMatchNode(레벨과 datum의 “나머지”를 조정하며 노드 N으로 내려감), spgAddNode(이 prefix는 일치하지만 노드가 없음; 레이블이 있는 노드 추가), spgSplitTuple(prefix 자체가 너무 구체적; prefix tuple과 postfix child로 분해). 쿼드트리의 choose는 중심이 임의의 점과 결코 “불일치”하지 않기 때문에 — 그저 올바른 사분면으로 라우팅할 뿐이므로 — 항상 매치만 한다.

// spg_quad_choose — src/backend/access/spgist/spgquadtreeproc.c
out->resultType = spgMatchNode;
out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
out->result.matchNode.levelAdd = 0;
out->result.matchNode.restDatum = PointPGetDatum(inPoint);

leaf 체인이 페이지를 넘칠 때 picksplit이 전체 목록을 하나의 inner tuple로 변환한다. 그것의 노드들이 leaf를 서브리스트로 팬아웃한다. 쿼드트리 버전은 중심(점들의 평균)을 계산하고 네 노드를 선언한 후 각 입력 점을 사분면에 매핑한다.

// spg_quad_picksplit — src/backend/access/spgist/spgquadtreeproc.c
out->hasPrefix = true;
out->prefixDatum = PointPGetDatum(centroid);
out->nNodes = 4;
out->nodeLabels = NULL;          /* quadrants are positional, unlabeled */
for (i = 0; i < in->nTuples; i++)
{
    Point *p = DatumGetPointP(in->datums[i]);
    int    quadrant = getQuadrant(centroid, p) - 1;
    out->leafTupleDatums[i] = PointPGetDatum(p);
    out->mapTuplesToNodes[i] = quadrant;
}

검색 시 inner_consistent와 leaf_consistent 쌍이 가지치기한다. inner_consistent는 inner tuple의 prefix와 node 집합, 스캔 키 목록을 받아 서브트리가 일치를 포함할 수 있는 노드 부분집합을 반환한다. 쿼드트리에서는 각 쿼리 연산자(left-of, contained-by, …)를 사분면 지오메트리와 교차시켜 살아남은 사분면의 비트마스크를 반환한다. leaf_consistent가 tuple 단위의 최종 결정을 내린다. k-d 트리의 choose는 레벨 교번 차원과 교번을 구동하는 levelAdd = 1을 보여준다.

// spg_kd_choose — src/backend/access/spgist/spgkdtreeproc.c
coord = DatumGetFloat8(in->prefixDatum);
out->resultType = spgMatchNode;
out->result.matchNode.nodeN =
    (getSide(coord, in->level % 2, inPoint) > 0) ? 0 : 1;
out->result.matchNode.levelAdd = 1;   /* alternate x/y each level */
out->result.matchNode.restDatum = PointPGetDatum(inPoint);

flowchart TB
  Ins["spgdoinsert: leaf datum + heap TID"] --> Loop{"현재 페이지 타입?"}
  Loop -->|leaf| Fit{"leaf tuple이<br/>페이지에 맞는가?"}
  Fit -->|yes| AddLeaf["addLeafTuple: 체인에 연결"]
  Fit -->|"no, 작은 체인"| Move["moveLeafs: 전체 체인 재배치"]
  Fit -->|"no, 큰 체인"| Pick["doPickSplit: inner tuple 생성,<br/>leaf를 서브리스트로 팬아웃"]
  Loop -->|inner| Choose["choose() 호출"]
  Choose -->|spgMatchNode| Descend["노드 N으로 하강,<br/>level += levelAdd"]
  Choose -->|spgAddNode| AddNode["spgAddNodeAction,<br/>choose 재시도"]
  Choose -->|spgSplitTuple| Split["spgSplitNodeAction:<br/>prefix + postfix, 재시도"]
  Descend --> Loop
  AddNode --> Choose
  Split --> Choose
  Pick --> Descend

소스 탐방

코드는 index-AM 표면을 따라 깔끔하게 나뉜다. 빌드와 메타페이지는 spginsert.c, 삽입 엔진은 spgdoinsert.c, 검색 엔진은 spgscan.c, 지원과 tuple 형성은 spgutils.c, opclass 메서드는 spg{quad,kd,text}treeproc.c, 회수는 spgvacuum.c다.

빌드, 메타페이지, AM 핸들러

spghandler(spgutils.c)가 IndexAmRoutine을 반환한다. spgbuild(spginsert.c)는 세 고정 페이지를 생성한다. SpGistInitMetapage로 메타페이지를, 메인 루트(블록 1)를, nulls 루트(블록 2)를 초기화하고, 힙을 스캔해 빌드 콜백에서 tuple마다 spgdoinsert를 호출한다. spgGetCache(spgutils.c)는 지연적으로 opclass config 메서드를 한 번 실행하고 네 개의 SpGistTypeDesc 항목과 spgConfigOut을 rd_amcache에 캐싱한다. 메타페이지에서 마지막-사용-페이지 캐시도 읽는다. initSpGistState가 연산별 SpGistState를 채운다.

삽입: spgdoinsert 하강 루프

spgdoinsert(spgdoinsert.c)가 핵심이다. 먼저 leaf datum을 형성하고(선택적 compress 메서드 호출, 없으면 입력을 de-toast), leafSize를 계산하고, longValuesOK가 opclass의 suffix를 허용하지 않으면 초과 크기 값을 앞에서 거부한다. current.blkno를 메인 또는 nulls 루트로 초기화하고 for(;;) 루프에 진입한다. 각 반복은 현재 버퍼를 획득하고(데드락 방지를 위해 자식 페이지를 조건부로 락 — 실패하면 false를 반환하고 호출자 spginsert가 재시도), 페이지 타입에 따라 분기한다.

• Leaf 페이지. leaf tuple을 형성하고 순서대로 세 가지를 시도한다. 공간이 있으면 addLeafTuple, 체인이 충분히 작으면 (checkSplitConditions가 SPGIST_PAGE_CAPACITY/2 미만, 64 tuple 미만으로 체인 크기를 보고) moveLeafs, 그렇지 않으면 doPickSplit.
• Inner 페이지(process_inner_tuple: 레이블). spgChooseIn을 마샬링하고, opclass choose를 호출하고(nulls 트리면 spgMatchNode를 강제), out.resultType에 따라 디스패치한다.

choose 판정의 디스패치가 삽입의 구조적 핵심이다.

// spgdoinsert — src/backend/access/spgist/spgdoinsert.c
switch (out.resultType)
{
    case spgMatchNode:
        spgMatchNodeAction(index, state, innerTuple,
                           &current, &parent,
                           out.result.matchNode.nodeN);
        level += out.result.matchNode.levelAdd;
        if (!isnull)
        {
            leafDatums[spgKeyColumn] = out.result.matchNode.restDatum;
            leafSize = SpGistGetLeafTupleSize(leafDescriptor,
                                              leafDatums, isnulls);
            leafSize += sizeof(ItemIdData);
        }
        break;                       /* loop: descend to child */
    case spgAddNode:
        spgAddNodeAction(index, state, innerTuple,
                         &current, &parent,
                         out.result.addNode.nodeN,
                         out.result.addNode.nodeLabel);
        goto process_inner_tuple;    /* retry choose on enlarged tuple */
    case spgSplitTuple:
        spgSplitNodeAction(index, state, innerTuple, &current, &out);
        goto process_inner_tuple;    /* retry choose on the prefix tuple */
}

addLeafTuple(spgdoinsert.c)은 두 체인 케이스를 처리한다. 루트 또는 체인 헤드 삽입은 nextOffset = Invalid로 설정하고, 부모가 있으면 saveNodeLink로 부모의 다운링크를 업데이트한다. 체인 중간 삽입은 README의 “두 번째로 삽입” 트릭을 활용한다. 새 tuple을 헤드가 가리키던 곳에 연결하고, 헤드가 새 tuple을 가리키게 한다. 이렇게 하면 체인 헤드 주소가 절대 바뀌지 않아 체인을 따라가지 않고도 부모 다운링크가 유효하게 유지된다.

// addLeafTuple — src/backend/access/spgist/spgdoinsert.c
SGLT_SET_NEXTOFFSET(leafTuple, SGLT_GET_NEXTOFFSET(head));
offnum = SpGistPageAddNewItem(state, current->page,
                              (Item) leafTuple, leafTuple->size, NULL, false);
/* re-get head (it may have moved on page) and link it to the new tuple */
head = (SpGistLeafTuple) PageGetItem(current->page,
                                     PageGetItemId(current->page, current->offnum));
SGLT_SET_NEXTOFFSET(head, offnum);

PickSplit: leaf 체인을 inner tuple로 변환

doPickSplit(spgdoinsert.c)은 leaf 체인이 새 tuple을 흡수하지도, 재배치되지도 않을 때 호출된다. 체인(또는 루트-as-leaf 분할의 경우 페이지의 모든 tuple)에서 모든 LIVE leaf datum을 수집하고, opclass picksplit을 호출해 prefix와 mapTuplesToNodes 할당을 얻은 후, spgFormNodeTuple/spgFormInnerTuple로 node tuple과 inner tuple을 형성한다. 미묘한 안전망이 checkAllTheSame이다. picksplit이 모든 tuple을 하나의 노드에 넣으면(무한 루프를 야기할 퇴화 분할), 코어가 allTheSame 모드로 재정의하고 무작위로 분배한다. 새 inner tuple이 체인 헤드의 부모 다운링크를 교체하고, leaf는 하나 이상의 leaf 페이지로 분배되며, 이전 슬롯은 redirect 또는 placeholder가 된다.

// doPickSplit — src/backend/access/spgist/spgdoinsert.c
innerTuple = spgFormInnerTuple(state,
                               out.hasPrefix, out.prefixDatum,
                               out.nNodes, nodes);
innerTuple->allTheSame = allTheSame;
/* re-point nodes[] into the formed tuple so downlinks can be patched */
SGITITERATE(innerTuple, i, node)
{
    nodes[i] = node;
}

SplitTuple: 지나치게 구체적인 prefix 단축

spgSplitNodeAction(spgdoinsert.c)은 inner tuple의 prefix가 새 값과 부분적으로만 일치하는 래딕스 트리 케이스를 구현한다. prefix tuple(원본보다 크지 않아야 원위치에 덮어쓸 수 있는 일치하는 앞부분)과 postfix tuple(더 짧은 새 prefix 아래의 원본 노드 배열)을 만들어, 같은 페이지에 들어가면 그곳에, 맞지 않으면(또는 페이지가 루트면) 다음 triple-parity로 페이지에 배치한다.

// spgSplitNodeAction — src/backend/access/spgist/spgdoinsert.c
if (prefixTuple->size > innerTuple->size)
    elog(ERROR, "SPGiST inner-tuple split must not produce longer prefix");
...
if (SpGistBlockIsRoot(current->blkno) ||
    SpGistPageGetFreeSpace(current->page, 1) + innerTuple->size <
    prefixTuple->size + postfixTuple->size + sizeof(ItemIdData))
{
    /* postfix is a child of prefix -> next triple parity */
    newBuffer = SpGistGetBuffer(index,
                                GBUF_INNER_PARITY(current->blkno + 1),
                                postfixTuple->size + sizeof(ItemIdData),
                                &xlrec.newPage);
}

페이지 할당, triple parity, 마지막-사용 캐시

SpGistGetBuffer(spgutils.c)가 할당자다. 백엔드별 마지막-사용-페이지 캐시(GET_LUP)에서 올바른 종류의 페이지(leaf vs. inner-by-parity, main vs. nulls)를 찾고, 조건부로 락하고, 페이지 타입과 여유 공간을 재확인하고(캐시가 오래됐을 수 있음), 없으면 allocNewBuffer로 폴백한다. SpGistSetLastUsedPage는 페이지 해제 시 가장 최신 여유 공간을 캐시에 다시 쓴다. triple-parity 규칙 — GBUF_INNER_PARITY(x) = x % 3, 자식을 parity (parent+1) % 3에 배치 — 은 서로 다른 분기를 내려가는 두 삽입이 교차 참조된 페이지 락을 보유할 가능성을 낮춰 데드락 재시작을 줄인다.

검색: spgWalk와 consistent 메서드

spgrescan/spgPrepareScanKeys(spgscan.c)가 스캔을 설정하고 null 관련 qual을 분리한다. spgWalk가 순회 드라이버다. pairing heap(scanQueue)에서 SpGistSearchItem을 꺼내고 — kNN 스캔에서는 거리 순, 그렇지 않으면 FIFO처럼 우선순위가 부여됨 — 대상 페이지를 공유 락하고 디스패치한다. 한 번에 한 페이지만 락하고 다음 스택 항목 방문 전에 해제하므로 검색이 데드락에 빠지지 않는다. 비용은 동시 삽입이 남긴 redirect tuple을 따라야 한다는 것이다.

// spgWalk — src/backend/access/spgist/spgscan.c
else                /* page is inner */
{
    SpGistInnerTuple innerTuple = (SpGistInnerTuple)
        PageGetItem(page, PageGetItemId(page, offset));
    if (innerTuple->tupstate != SPGIST_LIVE)
    {
        if (innerTuple->tupstate == SPGIST_REDIRECT)
        {
            /* transfer attention to redirect point */
            item->heapPtr = ((SpGistDeadTuple) innerTuple)->pointer;
            goto redirect;
        }
        elog(ERROR, "unexpected SPGiST tuple state: %d", innerTuple->tupstate);
    }
    spgInnerTest(so, item, innerTuple, isnull);
}

spgInnerTest(spgscan.c)가 opclass inner_consistent를 호출하고(nulls면 모든 자식을 강제), 살아남은 각 노드마다 자식 SpGistSearchItem을 만들어 큐에 넣는다. spgTestLeafTuple은 leaf 체인을 걸으며 redirect를 따르고 DEAD 항목을 건너뛰고, LIVE tuple마다 spgLeafTest → leaf_consistent를 호출한다. 일치는 정렬되지 않은 스캔이면 즉시 보고하고, 정렬된/kNN 스캔이면 heap 항목으로 큐에 넣는다. spggettuple, spggetbitmap, spgcanreturn(index-only 스캔 적격성)이 위에 위치한다.

VACUUM: 순차 스캔과 pending list

spgbulkdelete(spgvacuum.c)는 spgBulkDeleteState를 설정하고 spgvacuumscan을 호출한다. spgvacuumscan은 read stream으로 물리적 순서에 따라 모든 비-메타 페이지를 읽고 각 페이지에 spgvacuumpage를 호출한다. 각 페이지 후 pending list를 spgprocesspending으로 드레인한다. 동시 PickSplit이 이미 스캔된 페이지에 이동시킨 tuple을 잡는 메커니즘이다. vacuumLeafPage(spgvacuum.c)는 nextOffset 링크의 predecessor[] 역방향 맵을 만들어 체인 헤드를 찾고, 뮤테이션과 WAL 재생이 정확히 같은 일을 하도록 여섯 개의 작업 배열(dead/placeholder/move-src/move-dest/chain-src/chain-dest)을 계산한다. vacuumRedirectAndPlaceholder는 전역 가시성 테스트로 만료된 redirect를 placeholder로 변환하고 trailing placeholder를 잘라낸다.

// vacuumRedirectAndPlaceholder — src/backend/access/spgist/spgvacuum.c
if (dt->tupstate == SPGIST_REDIRECT &&
    (!TransactionIdIsValid(dt->xid) ||
     GlobalVisTestIsRemovableXid(vistest, dt->xid)))
{
    dt->tupstate = SPGIST_PLACEHOLDER;
    opaque->nRedirection--;
    opaque->nPlaceholder++;
    ItemPointerSetInvalid(&dt->pointer);
    itemToPlaceholder[xlrec.nToPlaceholder++] = i;
}

spgvacuumcleanup(spgvacuum.c)은 spgbulkdelete가 이미 실행됐으면 아무것도 하지 않는다. 그렇지 않으면 빈 대상 스캔을 실행해 redirect/placeholder를 재활용하고, FSM을 새로고침하고, 통계를 수집한다.

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

심볼	파일	라인
spghandler	src/backend/access/spgist/spgutils.c	44
spgGetCache	src/backend/access/spgist/spgutils.c	188
SpGistGetBuffer	src/backend/access/spgist/spgutils.c	569
SpGistSetLastUsedPage	src/backend/access/spgist/spgutils.c	673
SpGistInitMetapage	src/backend/access/spgist/spgutils.c	732
spgFormLeafTuple	src/backend/access/spgist/spgutils.c	871
spgFormNodeTuple	src/backend/access/spgist/spgutils.c	960
spgFormInnerTuple	src/backend/access/spgist/spgutils.c	1002
spgExtractNodeLabels	src/backend/access/spgist/spgutils.c	1160
spgbuild	src/backend/access/spgist/spginsert.c	73
spginsert	src/backend/access/spgist/spginsert.c	183
addLeafTuple	src/backend/access/spgist/spgdoinsert.c	203
moveLeafs	src/backend/access/spgist/spgdoinsert.c	387
checkAllTheSame	src/backend/access/spgist/spgdoinsert.c	599
doPickSplit	src/backend/access/spgist/spgdoinsert.c	677
spgMatchNodeAction	src/backend/access/spgist/spgdoinsert.c	1459
spgAddNodeAction	src/backend/access/spgist/spgdoinsert.c	1513
spgSplitNodeAction	src/backend/access/spgist/spgdoinsert.c	1715
spgdoinsert	src/backend/access/spgist/spgdoinsert.c	1914
spgPrepareScanKeys	src/backend/access/spgist/spgscan.c	208
spgLeafTest	src/backend/access/spgist/spgscan.c	516
spgInnerTest	src/backend/access/spgist/spgscan.c	667
spgTestLeafTuple	src/backend/access/spgist/spgscan.c	763
spgWalk	src/backend/access/spgist/spgscan.c	817
spggetbitmap	src/backend/access/spgist/spgscan.c	942
spggettuple	src/backend/access/spgist/spgscan.c	1026
spgcanreturn	src/backend/access/spgist/spgscan.c	1083
vacuumLeafPage	src/backend/access/spgist/spgvacuum.c	126
vacuumRedirectAndPlaceholder	src/backend/access/spgist/spgvacuum.c	494
spgvacuumpage	src/backend/access/spgist/spgvacuum.c	622
spgprocesspending	src/backend/access/spgist/spgvacuum.c	688
spgvacuumscan	src/backend/access/spgist/spgvacuum.c	800
spgbulkdelete	src/backend/access/spgist/spgvacuum.c	950
spgvacuumcleanup	src/backend/access/spgist/spgvacuum.c	981
spg_quad_choose	src/backend/access/spgist/spgquadtreeproc.c	115
spg_quad_picksplit	src/backend/access/spgist/spgquadtreeproc.c	169
spg_quad_inner_consistent	src/backend/access/spgist/spgquadtreeproc.c	227
spg_kd_choose	src/backend/access/spgist/spgkdtreeproc.c	53
spg_kd_picksplit	src/backend/access/spgist/spgkdtreeproc.c	108
spg_text_config	src/backend/access/spgist/spgtextproc.c	96
SpGistInnerTupleData	src/include/access/spgist_private.h	293
SpGistLeafTupleData	src/include/access/spgist_private.h	383
SpGistDeadTupleData	src/include/access/spgist_private.h	427

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

위의 모든 코드 발췌와 심볼은 커밋 273fe94의 REL_18_STABLE 작업 트리에서 직접 읽었다. 검증 메모:

• 5-메서드 opclass 계약. src/include/access/spgist.h는 SPGIST_CONFIG_PROC(1), SPGIST_CHOOSE_PROC(2), SPGIST_PICKSPLIT_PROC(3), SPGIST_INNER_CONSISTENT_PROC(4), SPGIST_LEAF_CONSISTENT_PROC(5)를 정의하며, 선택적으로 SPGIST_COMPRESS_PROC(6)과 SPGIST_OPTIONS_PROC(7)이 있다. SPGISTNProc = 7. spghandler가 amsupport = SPGISTNProc으로 설정한다.
• Tuple 상태. 네 개의 tupstate 값 SPGIST_LIVE/REDIRECT/DEAD/PLACEHOLDER(0..3)와 고정 블록 SPGIST_METAPAGE_BLKNO(0)/SPGIST_ROOT_BLKNO(1)/SPGIST_NULL_BLKNO(2)가 spgist_private.h에서 확인됐다.
• 비트 패킹 헤더. SpGistInnerTupleData는 tupstate:2, allTheSame:1, nNodes:13, prefixSize:16을 패킹한다. SGITMAXNNODES = 0x1FFF와 SGITMAXPREFIXSIZE = 0xFFFF가 한계를 정한다. SpGistLeafTupleData는 tupstate:2, size:30을 패킹하며 t_info의 하위 14비트에 nextOffset이 있다(SGLT_GET_NEXTOFFSET이 0x3FFF로 마스킹). 이것들은 정확한 인용이지 요약이 아니다.
• 단일 페이지 체인 불변식. nextOffset 필드는 2바이트 OffsetNumber(TID가 아님)로, README가 체인이 한 페이지에 머물도록 요구하기 때문에만 올바르다. SpGistLeafTupleData 주석에서 확인됐다.
• Triple parity. GBUF_INNER_PARITY(x) = (x) % 3이 spgist_private.h에 있다. spgSplitNodeAction과 doPickSplit은 자식 페이지에 GBUF_INNER_PARITY(blkno+1)을 요청해, README의 (N+1) mod 3 규칙과 일치한다.
• 조건부 락 재시작. spgdoinsert는 자식 페이지에 ConditionalLockBuffer를 사용하고 실패 시 false를 반환한다(호출자가 재시도). 하강 블록에서 확인됐다. spgWalk는 한 번에 한 페이지를 공유 락하고 SPGIST_REDIRECT tuple에서 goto redirect한다.
• PG18 정확성. SP-GiST는 병렬 인식이 아니다(amcanparallel = false, amcanbuildparallel = false). 병렬 vacuum에는 VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_COND_CLEANUP으로 참여한다. spgvacuumscan은 READ_STREAM_USE_BATCHING과 함께 read_stream_begin_relation을 사용하는 read-stream API를 쓴다. PG17+/PG18 형태다. PG19 전용 심볼은 참조되지 않는다.
• WAL. 리도 핸들러는 RM_SPGIST_ID 아래 spgxlog.c에 있다. XLOG_SPGIST_ADD_LEAF, XLOG_SPGIST_VACUUM_REDIRECT 같은 레코드 타입이 위에 인용된 함수에서 발행된다. WAL 재생 세부 사항은 여기서 범위를 벗어난다(postgres-xlog-wal.md와 postgres-recovery-redo.md 참고).
• 핸들러 플래그 전체 읽기. spghandler는 amcanorder = false, amcanorderbyop = true, amcanbackward = false, amoptionalkey = true, amstorage = true, amclusterable = false, ampredlocks = false, amsummarizing = false, amkeytype = InvalidOid, amoptsprocnum = SPGIST_OPTIONS_PROC으로 설정한다. SP-GiST는 SSI 술어 락 지원이 없다(ampredlocks = false). nbtree/gin/gist/hash와 달리, 락-경량 redirect 기반 동시성의 귀결이다. 스캔이 건드리는 페이지 집합이 직렬화 가능 충돌 감지를 위해 락할 만큼 안정적이지 않다. spgutils.c에서 축어적으로 읽었다.

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

SP-GiST는 단일 인덱스가 아닌 공간 분할 구조 전체 계열의 범용 호스트라는 이상한 위치를 차지한다. 더 넓은 맥락에 놓으면 무엇을 얻고 무엇을 포기하는지 명확해진다.

계보 — 원래 SP-GiST 프레임워크

PostgreSQL의 SP-GiST는 Aoki의 학술적 SP-GiST 프레임워크에서 직접 파생됐으며, 이후 Eltabakh, Eldawy, Mokbel의 포괄적인 처리(“SP-GiST: An Extensible Database Index for Supporting Space Partitioning Trees”)로 이어졌다. 이것은 1995년 Hellerstein-Naughton-Pfeffer의 GiST를 일반화했다(postgres-gist.md 참고). GiST는 균형, 겹침 트리(B-트리, R-트리)를 consistent/union/penalty/picksplit 계약 뒤에 인수분해했다. SP-GiST는 불균형, 분리적, 재귀 분할 트리에 같은 일을 한다. 둘은 의도적으로 보완적이다. 자연적 분해가 겹치지 않이 도메인을 타일링하는 데이터 타입(점에 대한 쿼드트리, 문자열에 대한 트라이)은 SP-GiST에 매핑되고, 겹치는 경계 영역이 필요한 분해(다각형에 대한 R-트리)는 GiST에 매핑된다. PostgreSQL은 두 일반화된 프레임워크를 모두 제공하는 극소수의 프로덕션 시스템 중 하나다.

분리 분할의 장점과 비용

정의적 속성 — 분리적이고 망라적인 자식 영역 — 이 SP-GiST가 삽입 시 단일 경로를 내려가고(포인트 쿼리에서도) 단일 경로를 검색하게 해주는 바로 그것이다. R-트리는 경계 박스가 겹쳐서 여러 자식을 따라야 하는 경우가 있다. SP-GiST는 포함 쿼리에서 결코 그렇지 않다. 비용은 다른 곳에서 지불된다.

• 균형 보장 없음. 깊이가 데이터 집중도를 따른다. 병리적 문자열(긴 공통 접두사)에 대한 트라이는 깊을 수 있다. prefixSize와 SplitTuple/postfix 기계가 피해를 제한하지만, B-트리의 분할-전파처럼 트리를 균형 상태로 만들 수 없다.
• 범위와 kNN 쿼리는 여전히 팬아웃. inner_consistent는 살아남은 노드의 집합을 반환하므로, 쿼드트리에 대한 윈도우 쿼리는 윈도우가 닿는 모든 사분면을 방문한다. SP-GiST의 이점은 단일 페이지 체인과 높은 팬아웃이지, 이 경우의 단일 경로 순회가 아니다.

다른 시스템의 동일 형태 인덱싱

시스템	쿼드트리 / k-d / 트라이 동등물	매핑 전략
PostgreSQL SP-GiST	quadtree, k-d, radix trie, inet, range	범용 5-메서드 opclass; inner-tuple + leaf-chain on page
Oracle	R-트리(Spatial), 범용 SP 프레임워크 없음	전용 공간 카트리지; 확장 가능한 트라이 호스트 없음
MySQL/InnoDB	R-트리(공간), 그 외 B-트리만	쿼드트리/트라이 AM 없음; 공간은 R-트리 사용
SQL Server	그리드 기반 공간(다중 레벨 테셀레이션)	선형화된 그리드에 대한 B-트리, 진정한 분할 트리 아님
SQLite	R*-트리 모듈	가상 테이블 R-트리; 트라이/쿼드트리 호스트 없음
특수 목적 (Lucene, RocksDB)	FST / radix / ART	인메모리 또는 LSM 트라이, 페이지 매핑 범용 호스트 아님

핵심 대조: 대부분의 엔진이 하나의 공간 구조(보통 R-트리)를 하드코딩하거나, 트라이를 인메모리 계층으로 밀어 넣는다(Lucene의 FST, Adaptive Radix Tree). PostgreSQL은 분할 트리 추상화 자체를 노출해, text 트라이, point 쿼드트리, inet 접두사 트리, range 2-D 쿼드 파티션이 모두 하나의 페이지 매핑, 하나의 동시성 프로토콜, 하나의 VACUUM을 공유하고, 다섯 개의 C 함수에서만 다르게 한다.

연구 프런티어

• 캐시 친화적이고 SIMD 친화적인 트라이. Adaptive Radix Tree(ART, Leis et al. 2013)와 Masstree는 인메모리 트라이가 SIMD 비교를 위해 점유율에 따라 노드 팬아웃을 조정하고 키를 패킹함으로써 B-트리에 필적할 수 있음을 보여준다. SP-GiST의 allTheSame과 prefix-suffix 기계는 ART의 노드 크기 적응성의 조잡하고 온디스크적인 유사물이지만, SP-GiST는 ART가 Node4/16/48/256 사이를 전환하는 방식으로 노드 표현을 조정하지 않는다.
• 학습 공간 인덱스. RMI 스타일과 Flood/Tsunami 학습 다차원 인덱스는 고정된 사분면/중심 분할을 데이터 분포에 맞는 모델로 대체한다. picksplit 훅이 코어 페이지 매핑을 건드리지 않고 학습 분할기를 주입할 수 있는 자연스러운 이음새다.
• redirect 없는 동시성. SP-GiST의 redirect/placeholder 래티스는 락-경량 검색에 대한 답이다. Bw-트리 스타일의 락-프리 델타와 에폭 기반 회수가 현대적 대안이다. SP-GiST의 redirect-후-VACUUM-재활용은 진정한 락-프리 구조보다는 RCU에 가깝고, 한 번에 한 페이지 공유 락 워크가 가장 단순하고 견고한 보장이다.
• SSI 통합 없음. ampredlocks = false이므로 SP-GiST 인덱스는 직렬화 가능 트랜잭션에 세밀한 술어 락을 기여할 수 없다(postgres-ssi-predicate-locking.md 참고). SP-GiST 스캔에 의존하는 직렬화 가능 쿼리는 더 거친 충돌 감지로 폴백한다. 페이지 또는 노드 세분화 술어 락으로 SP-GiST를 확장하는 것은 열린 공학 항목이다.

flowchart TB
  Domain["자연스러운<br/>재귀적 분해가 있는 데이터 타입"] --> Q{"자식 영역이<br/>겹치는가?"}
  Q -->|"no — 분리 타일링"| SP["SP-GiST<br/>단일 경로 하강<br/>quadtree / k-d / trie / inet"]
  Q -->|"yes — 경계 박스 겹침"| G["GiST<br/>균형, 다중 경로<br/>R-tree / range / fulltext"]
  SP --> M["5 메서드:<br/>config choose picksplit<br/>inner_consistent leaf_consistent"]
  G --> N["7 메서드:<br/>consistent union penalty<br/>picksplit same compress decompress"]
  M --> Core["공유 코어: 페이지 매핑,<br/>WAL, VACUUM, 동시성"]
  N --> Core

출처

PostgreSQL 소스 트리 (REL_18_STABLE, 커밋 273fe94, 2026-06-05 기준; 모든 경로는 /data/hgryoo/references/postgres 기준):

• src/backend/access/spgist/README — 디스크 매핑 문제, inner/leaf tuple 구조, 단일 페이지 체인 불변식, redirect/placeholder 상태, triple parity, 조건부 락 동시성 프로토콜의 권위 있는 설명.
• src/backend/access/spgist/spgdoinsert.c — 삽입 엔진: spgdoinsert, addLeafTuple, moveLeafs, doPickSplit, checkAllTheSame, spgMatchNodeAction, spgAddNodeAction, spgSplitNodeAction.
• src/backend/access/spgist/spgscan.c — 검색 엔진: spgWalk, spgInnerTest, spgLeafTest, spgTestLeafTuple, spgPrepareScanKeys, spggettuple, spggetbitmap, spgcanreturn.
• src/backend/access/spgist/spgutils.c — spghandler(IndexAmRoutine), spgGetCache, SpGistGetBuffer, SpGistSetLastUsedPage, SpGistInitMetapage, tuple 형성 헬퍼 spgFormLeafTuple/spgFormNodeTuple/spgFormInnerTuple.
• src/backend/access/spgist/spgvacuum.c — 회수: spgbulkdelete, spgvacuumscan, spgvacuumpage, vacuumLeafPage, vacuumRedirectAndPlaceholder, spgprocesspending, spgvacuumcleanup.
• src/backend/access/spgist/spginsert.c — spgbuild, spgbuildempty, spginsert(빌드 콜백과 조건부 락 실패 재시도 루프).
• src/backend/access/spgist/spgquadtreeproc.c, src/backend/access/spgist/spgkdtreeproc.c, src/backend/access/spgist/spgtextproc.c — 위에 인용된 쿼드트리, k-d 트리, 래딕스 트라이 예시를 위한 제공된 opclass 메서드.
• src/backend/utils/adt/network_spgist.c, src/backend/utils/adt/rangetypes_spgist.c — inet/cidr 접두사 트리와 range 쿼드 파티션 opclass(같은 5-메서드 계약의 추가 예시로만 명명; 깊이 인용하지 않음).
• src/include/access/spgist.h, src/include/access/spgist_private.h — opclass 지원 프로시저 번호(SPGISTNProc = 7), tupstate 래티스, 고정 블록 번호, 비트 패킹 SpGistInnerTupleData/SpGistLeafTupleData/SpGistDeadTupleData 헤더.

이론 기반 (knowledge/research/dbms-general/ 및 .omc/plans/postgres-paper-bibliography.md의 논문 참고):

• Database System Concepts (Silberschatz, Korth, Sudarshan, 7e), §24.4 “Indexing of Spatial Data” — 쿼드트리, k-d 트리, 영역 분할 계열.
• Hellerstein, Naughton & Pfeffer, “Generalized Search Trees for Database Systems” (VLDB 1995) — SP-GiST가 공간 분할 케이스를 위해 일반화한 GiST 프레임워크(dbms-papers/ 추적; postgres-gist.md 참고).
• Samet, Foundations of Multidimensional and Metric Data Structures — 쿼드트리/k-d 트리/트라이 이론의 표준 참고.
• Leis, Kemper & Neumann, “The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases” (ICDE 2013) — 연구 프런티어 논의에서 인용된 현대 인메모리 트라이 대조.

관련 KB 문서: postgres-gist.md(균형/겹침 자매 프레임워크와 lossy-key 모델), postgres-index-am.md(IndexAmRoutine 디스패치 계약과 amhandler 메커니즘), postgres-nbtree.md(전순서 B-트리 대조), postgres-buffer-manager.md(페이지 래칭), postgres-vacuum.md, postgres-page-layout.md(힙 측 회수와 item-pointer 레이아웃), postgres-ssi-predicate-locking.md(ampredlocks = false의 의미), postgres-xlog-wal.md/postgres-recovery-redo.md(이 문서가 명명만 하는 RM_SPGIST_ID 레코드의 WAL 재생 경로).