PostgreSQL 인덱스 비교: GIN(pg_bigm) vs B-tree
개요
PostgreSQL에서 텍스트 검색을 위한 두 가지 주요 인덱스 방식인 GIN(pg_bigm)과 B-tree 인덱스의 특성과 성능을 비교 분석합니다.
인덱스 구조 상세 분석
1. B-tree 인덱스
내부 구조
B-tree는 균형 이진 검색 트리로, 다음과 같은 계층적 구조를 가집니다:
[루트 노드]
/ \
[내부노드] [내부노드]
/ \ / \
[리프] [리프] [리프] [리프]
| | | |
데이터 데이터 데이터 데이터
구조적 특성:
- 페이지 단위 저장: 8KB 페이지에 키-값 쌍을 정렬하여 저장
- 균형 유지: 모든 리프 노드가 동일한 깊이를 가짐
- 정렬 보장: 키 값이 항상 정렬된 상태로 유지
- 포인터 연결: 각 노드는 자식 노드에 대한 포인터 보유
데이터 저장 방식:
-- 예시: name 컬럼에 대한 B-tree 인덱스
-- 문자열 "Apple", "Banana", "Cherry"가 있을 때
리프 페이지 1: [Apple → Row ID 1] [Banana → Row ID 5]
리프 페이지 2: [Cherry → Row ID 3] [Date → Row ID 7]검색 과정:
- 루트에서 시작하여 키 값 비교
- 적절한 자식 노드로 이동
- 리프 노드에서 최종 검색
- 시간 복잡도: O(log n)
장점
- 빠른 점 조회: 정확한 키 값으로 직접 접근 (O(log n))
- 범위 검색 최적화: 정렬된 구조로 인한 순차 스캔
- ORDER BY 생략: 이미 정렬된 데이터로 정렬 작업 불필요
- 메모리 효율성: 키 값만 저장하여 공간 효율적
- 캐시 친화적: 순차적 접근 패턴
단점
- 패턴 매칭 제한: 접두사 검색(
LIKE 'abc%')만 가능 - 부분 문자열 불가:
LIKE '%abc%'형태 검색 지원 안함 - 대소문자 구분: 정확한 매칭만 지원
2. GIN 인덱스 with pg_bigm
내부 구조
GIN(Generalized Inverted Index)은 역색인(Inverted Index) 구조를 사용합니다:
토큰 테이블: 포스팅 리스트:
"ap" -----------> [Row 1, Row 15, Row 23]
"pp" -----------> [Row 1, Row 8, Row 31]
"pl" -----------> [Row 1, Row 12]
"le" -----------> [Row 1, Row 7, Row 19]
pg_bigm의 2-gram 토큰화 과정:
-- 문자열 "Apple"의 토큰화
입력: "Apple"
2-gram 토큰: [" a", "ap", "pp", "pl", "le", "e "]
※ 공백 패딩으로 시작/끝 구분구조적 특성:
- 토큰 사전: 모든 고유 2-gram 토큰을 키로 사용
- 포스팅 리스트: 각 토큰이 포함된 행의 ID 목록
- 압축 저장: 포스팅 리스트를 압축하여 공간 절약
- 병렬 처리: 여러 토큰을 동시에 검색 가능
데이터 저장 예시:
-- 테이블 데이터
Row 1: "Apple iPhone"
Row 2: "Samsung Galaxy"
Row 3: "Apple Watch"
-- GIN 인덱스 구조
토큰 " a": [1, 3] -- " Apple"에서 추출
토큰 "ap": [1, 3] -- "Apple"에서 추출
토큰 "pp": [1, 3] -- "Apple"에서 추출
토큰 "pl": [1, 3] -- "Apple"에서 추출
토큰 "le": [1, 3] -- "Apple"에서 추출
토큰 "e ": [1, 3] -- "Apple "에서 추출
토큰 " i": [1] -- " iPhone"에서 추출
토큰 "ip": [1] -- "iPhone"에서 추출
...검색 과정 (‘ppl’ 검색 시):
- ‘ppl’을 2-gram으로 분해: [“pp”, “pl”]
- 각 토큰의 포스팅 리스트 조회
- 교집합 연산으로 공통 행 찾기
- 유사도 계산 및 임계값 적용
장점
- 유연한 검색: 부분 문자열, 유사도, 정규식 검색 지원
- 언어 독립적: 2-gram 기반으로 모든 언어 지원
- 퍼지 매칭: 오타나 변형에도 검색 가능
- 병렬 처리: 토큰별 독립적 검색으로 병렬화 효과
단점
- 큰 인덱스 크기: 원본 텍스트의 2-3배 크기
- 빌드 시간: 모든 2-gram 토큰 생성으로 시간 소요
- 메모리 사용량: 토큰 사전과 포스팅 리스트로 인한 높은 메모리 사용
- 짧은 문자열 비효율: 2글자 미만 문자열에서 효과 제한
구조 비교 요약
| 측면 | B-tree | GIN(pg_bigm) |
|---|---|---|
| 기본 구조 | 균형 이진 트리 | 역색인 (토큰 → 문서) |
| 저장 단위 | 키-값 쌍 | 토큰-포스팅리스트 쌍 |
| 정렬 보장 | ✅ 항상 정렬됨 | ❌ 토큰 순서만 정렬 |
| 검색 방식 | 트리 순회 | 토큰 교집합 연산 |
| 공간 복잡도 | O(n) | O(n × 토큰수) |
| 구축 복잡도 | O(n log n) | O(n × 토큰수) |
| 캐시 효율성 | 높음 (순차 접근) | 보통 (랜덤 접근) |
| 업데이트 비용 | 낮음 | 높음 (토큰 재생성) |
부분 문자열 검색 불가능 이유 심층 분석
B-tree에서 LIKE '%abc%' 검색이 불가능한 근본적 이유
1. B-tree의 정렬 기반 구조
B-tree는 **렉시코그래피 순서(사전 순서)**로 정렬된 구조입니다:
-- B-tree 인덱스에서 문자열 정렬 예시
인덱스 저장 순서:
"Apple" → Row 1
"Application" → Row 5
"Banana" → Row 2
"Band" → Row 8
"Cherry" → Row 32. 검색 방식별 동작 차이
✅ 접두사 검색이 가능한 이유 (LIKE 'App%')
B-tree는 정렬된 구조이므로 특정 접두사로 시작하는 모든 값들이 연속적으로 배치됩니다:
-- 'App'로 시작하는 검색
검색 과정:
1. 루트에서 'App' >= 현재 노드 값 비교
2. 'App'보다 크거나 같은 첫 번째 위치 찾기
3. 'App'로 시작하지 않는 첫 번째 값까지 순차 스캔
결과: "Apple", "Application" (연속된 범위)
효율성: O(log n + k) - k는 결과 개수❌ 부분 문자열 검색이 불가능한 이유 (LIKE '%abc%')
‘abc’를 포함하는 문자열들은 B-tree에서 분산되어 저장됩니다:
-- 'abc'를 포함하는 문자열들의 실제 분포
"Alphabetic" → 위치 50 (abc 포함)
"Fabric" → 위치 200 (abc 포함)
"Keyboard" → 위치 400 (abc 포함)
"Rabcket" → 위치 800 (abc 포함)
-- B-tree에서는 이들이 완전히 다른 위치에 저장됨
-- 연속된 스캔으로는 찾을 수 없음3. 알고리즘적 제약
-- B-tree 검색 알고리즘 (의사코드)
function btree_search(target_prefix):
current = root
while current is not leaf:
if target_prefix <= current.key:
current = current.left
else:
current = current.right
// 리프에서 순차 스캔
while current.key starts_with target_prefix:
yield current
current = next_leaf_entry문제점: 부분 문자열 검색은 “시작 위치를 알 수 없음”
- ‘abc’를 포함하는 첫 번째 문자열이 어디에 있는지 예측 불가
- 전체 인덱스 스캔이 필요 → 인덱스 의미 없음
GIN(pg_bigm)에서 부분 문자열 검색이 가능한 이유
1. 역색인 구조의 장점
-- 'abc'를 포함하는 문자열 검색 과정
검색어: '%abc%'
1. 토큰화: 'abc' → ['ab', 'bc']
2. 각 토큰의 포스팅 리스트 조회:
'ab': [Row 1, Row 15, Row 23, Row 67]
'bc': [Row 1, Row 12, Row 23, Row 89]
3. 교집합 연산: [Row 1, Row 23]
4. 실제 문자열 검증으로 최종 필터링2. 토큰 기반 검색의 효율성
-- 토큰별 포스팅 리스트 (압축 저장)
토큰 'ab': [1, 15, 23, 67, 89, 123, ...] -- 'ab'를 포함하는 모든 행
토큰 'bc': [1, 12, 23, 45, 89, 156, ...] -- 'bc'를 포함하는 모든 행
-- 교집합 연산 (O(n + m) - n, m은 각 리스트 크기)
결과: [1, 23, 89] -- 'ab'와 'bc' 모두 포함하는 행성능 차이 실증 분석
시나리오: 100만 행에서 ‘%phone%’ 검색
B-tree 방식 (풀 테이블 스캔)
-- B-tree 인덱스는 사용되지 않음
EXPLAIN ANALYZE SELECT * FROM products WHERE name LIKE '%phone%';
Seq Scan on products (cost=0.00..25000.00 rows=1000 width=64)
Filter: (name ~~ '%phone%'::text)
Rows Removed by Filter: 999000
Execution time: 3200.123 msGIN(pg_bigm) 방식
-- GIN 인덱스 활용
EXPLAIN ANALYZE SELECT * FROM products WHERE name LIKE '%phone%';
Bitmap Heap Scan on products (cost=32.00..156.00 rows=1000 width=64)
Recheck Cond: (name ~~ '%phone%'::text)
-> Bitmap Index Scan on idx_products_name_gin (cost=0.00..31.75)
Index Cond: (name ~~ '%phone%'::text)
Execution time: 12.456 ms성능 차이: 257배 향상
근본적 차이점 요약
| 측면 | B-tree | GIN(pg_bigm) |
|---|---|---|
| 데이터 조직 | 전체 문자열 기준 정렬 | 부분 토큰 기준 분류 |
| 검색 시작점 | 정렬 순서로 예측 가능 | 토큰 사전에서 직접 접근 |
| 부분 검색 | 시작점 예측 불가 | 토큰 조합으로 위치 특정 |
| 스캔 범위 | 전체 또는 연속 구간 | 관련 토큰의 교집합만 |
| 알고리즘 | 이진 검색 + 순차 스캔 | 해시 접근 + 집합 연산 |
결론
B-tree에서 부분 문자열 검색이 불가능한 이유는 “정렬 기반 구조의 근본적 한계” 때문입니다:
- 위치 예측 불가: 부분 문자열이 포함된 데이터의 시작 위치를 알 수 없음
- 분산 저장: 동일한 부분 문자열을 포함하는 데이터가 인덱스 전체에 분산
- 연속성 부족: 정렬 순서와 부분 문자열 포함 여부 간 상관관계 없음
반면 GIN(pg_bigm)은 **“역색인 구조”**로 이 문제를 해결:
- 토큰 단위로 데이터를 분류하여 직접 접근 가능
- 여러 토큰의 교집합으로 정확한 위치 특정
- 부분 문자열이 어디에 있든 토큰 사전을 통해 즉시 찾기 가능
성능 비교
검색 시나리오별 성능
| 검색 유형 | B-tree | GIN(pg_bigm) | 권장 |
|---|---|---|---|
정확한 일치 (=) | ★★★★★ | ★★★☆☆ | B-tree |
접두사 검색 (LIKE 'abc%') | ★★★★★ | ★★★☆☆ | B-tree |
부분 문자열 (LIKE '%abc%') | ★☆☆☆☆ | ★★★★★ | GIN |
접미사 검색 (LIKE '%abc') | ★☆☆☆☆ | ★★★★★ | GIN |
| 유사도 검색 | ★☆☆☆☆ | ★★★★★ | GIN |
범위 검색 (BETWEEN) | ★★★★★ | ★☆☆☆☆ | B-tree |
정렬 (ORDER BY) | ★★★★★ | ★☆☆☆☆ | B-tree |
리소스 사용량
-- 샘플 테이블 (1백만 행)
CREATE TABLE products (
id SERIAL PRIMARY KEY,
name VARCHAR(255),
description TEXT
);
-- 인덱스 크기 비교
-- B-tree 인덱스
CREATE INDEX idx_products_name_btree ON products(name);
-- 크기: 약 42MB
-- GIN 인덱스 (pg_bigm)
CREATE INDEX idx_products_name_gin ON products USING gin(name gin_bigm_ops);
-- 크기: 약 128MB (3배 차이)pg_bigm 검색 방식 상세 비교
LIKE ‘%text%’ vs % ‘text’ 차이점
두 검색 방식은 완전히 다른 매칭 방식을 사용합니다:
1. LIKE '%smartphone%' (정확한 부분 문자열 검색)
SELECT * FROM products WHERE name LIKE '%smartphone%';동작 방식:
- 정확한 부분 문자열 매칭
- ‘smartphone’이 문자열에 완전히 포함되어야 함
- 대소문자 구분 (기본값)
- 토큰 교집합으로 후보 찾기 → 실제 문자열 검증
매칭 결과:
✅ "iPhone smartphone case" -- smartphone 정확히 포함
✅ "Best smartphone reviews" -- smartphone 정확히 포함
✅ "smartphone" -- 완전 일치
❌ "smart phone" -- 띄어쓰기로 분리
❌ "smartphones" -- 복수형 (s 추가)
❌ "Smartphone" -- 대문자 (collation 설정에 따라)
❌ "smatphone" -- 오타2. name % 'smartphone' (유사도 기반 퍼지 검색)
SELECT * FROM products WHERE name % 'smartphone';동작 방식:
- 유사도 기반 퍼지 매칭
- similarity() 함수로 유사도 점수 계산
- 기본 임계값: 0.3 (30% 이상 유사하면 매칭)
- 오타, 변형, 부분 일치 허용
매칭 결과:
✅ "smartphone" -- 1.0 (완전 일치)
✅ "smartphones" -- 0.91 (복수형, 높은 유사도)
✅ "smart phone" -- 0.67 (띄어쓰기, 중간 유사도)
✅ "Smartphone" -- 0.91 (대소문자, 높은 유사도)
✅ "smatphone" -- 0.78 (오타, 중간 유사도)
✅ "phone" -- 0.42 (부분 일치, 낮은 유사도)
❌ "mobile" -- 0.18 (임계값 0.3 미만)
❌ "device" -- 0.05 (전혀 다름)유사도 계산 원리
2-gram 토큰 기반 유사도 계산
-- 예시: 'smartphone' vs 'phone' 유사도 계산
'smartphone' 토큰화:
[' s', 'sm', 'ma', 'ar', 'rt', 'tp', 'ph', 'ho', 'on', 'ne', 'e '] (11개)
'phone' 토큰화:
[' p', 'ph', 'ho', 'on', 'ne', 'e '] (6개)
공통 토큰: ['ph', 'ho', 'on', 'ne', 'e '] (5개)
유사도 공식:
similarity = 공통토큰수 / (토큰1수 + 토큰2수 - 공통토큰수)
= 5 / (11 + 6 - 5)
= 5 / 12
= 0.417 (약 42%)실제 유사도 확인 방법
-- 유사도 점수 확인
SELECT
name,
similarity(name, 'smartphone') as score,
name LIKE '%smartphone%' as exact_match,
name % 'smartphone' as fuzzy_match
FROM products
WHERE name % 'smartphone' OR name LIKE '%smartphone%'
ORDER BY score DESC;
-- 결과 예시:
-- name | score | exact_match | fuzzy_match
-- "smartphone cases" | 0.75 | true | true
-- "smartphones reviews" | 0.85 | false | true
-- "smart phone guide" | 0.60 | false | true
-- "phone smart tech" | 0.45 | false | true
-- "iPhone smartphone" | 0.73 | true | true임계값 설정의 영향
기본 임계값 (0.3)
-- 현재 임계값 확인
SHOW pg_bigm.similarity_limit; -- 0.3
-- 0.3 이상인 모든 항목 매칭
SELECT 'phone' % 'smartphone'; -- true (0.42 > 0.3)
SELECT 'mobile' % 'smartphone'; -- false (0.18 < 0.3)임계값 조정 효과
-- 더 엄격하게 (높은 정확도)
SET pg_bigm.similarity_limit = 0.5;
SELECT 'phone' % 'smartphone'; -- false (0.42 < 0.5)
SELECT 'smartphones' % 'smartphone'; -- true (0.91 > 0.5)
-- 더 관대하게 (높은 재현율)
SET pg_bigm.similarity_limit = 0.2;
SELECT 'mobile' % 'smartphone'; -- true (0.18 > 0.2)
SELECT 'device' % 'smartphone'; -- false (0.05 < 0.2)실무 활용 전략
1. 단계적 검색 확장
-- 1단계: 정확한 매칭 우선
SELECT *, 1.0 as relevance
FROM products
WHERE name LIKE '%smartphone%'
UNION ALL
-- 2단계: 유사도 검색 추가 (중복 제거)
SELECT *, similarity(name, 'smartphone') as relevance
FROM products
WHERE name % 'smartphone'
AND name NOT LIKE '%smartphone%'
ORDER BY relevance DESC;2. 동적 임계값 적용
-- 검색 결과가 적으면 임계값을 낮춰서 재검색
WITH exact_search AS (
SELECT COUNT(*) as cnt FROM products WHERE name LIKE '%smartphone%'
),
fuzzy_search AS (
SELECT * FROM products
WHERE name % 'smartphone'
AND (SELECT cnt FROM exact_search) < 10 -- 결과가 10개 미만이면
AND similarity(name, 'smartphone') >=
CASE WHEN (SELECT cnt FROM exact_search) = 0 THEN 0.2 -- 0개면 0.2
ELSE 0.3 END -- 기본값 0.3
)
SELECT * FROM fuzzy_search;3. 관련도 기반 정렬
-- 유사도 점수로 관련도 정렬
SELECT
name,
CASE
WHEN name LIKE '%smartphone%' THEN similarity(name, 'smartphone') + 0.1
ELSE similarity(name, 'smartphone')
END as relevance_score
FROM products
WHERE name % 'smartphone' OR name LIKE '%smartphone%'
ORDER BY relevance_score DESC
LIMIT 20;성능 특성 비교
| 측면 | LIKE ‘%text%’ | % ‘text’ |
|---|---|---|
| 정확도 | 100% (정확한 매칭) | 가변적 (임계값 의존) |
| 재현율 | 낮음 (엄격한 매칭) | 높음 (유연한 매칭) |
| 성능 | 빠름 (단순 검증) | 약간 느림 (유사도 계산) |
| 오타 처리 | 불가능 | 가능 |
| 사용자 경험 | 정확한 검색 | 검색 친화적 |
사용 사례 및 권장사항
B-tree 인덱스 권장 상황
-
정확한 검색이 주요 용도
SELECT * FROM users WHERE email = 'user@example.com'; SELECT * FROM products WHERE category_id = 5; -
범위 검색이 빈번
SELECT * FROM orders WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31'; SELECT * FROM products WHERE price BETWEEN 100 AND 500; -
정렬된 결과가 필요
SELECT * FROM products ORDER BY name LIMIT 10;
GIN(pg_bigm) 인덱스 권장 상황
-
검색 기능이 중요한 애플리케이션
SELECT * FROM products WHERE name LIKE '%smartphone%'; SELECT * FROM articles WHERE title LIKE '%PostgreSQL%'; -
자동완성 기능
SELECT * FROM products WHERE name % 'iPhon'; -- 유사도 검색 -
다국어 콘텐츠 검색
SELECT * FROM posts WHERE content LIKE '%안녕하세요%';
결론
선택 기준
- 정확성과 성능 우선: B-tree 인덱스
- 검색 유연성 우선: GIN(pg_bigm) 인덱스
- 대용량 데이터: 인덱스 크기와 빌드 시간 고려 필요
- 실시간 검색: pg_bigm의 높은 메모리 사용량 고려
권장 가이드라인
- 소규모 애플리케이션: B-tree 우선 고려
- 검색 중심 애플리케이션: GIN(pg_bigm) 적극 활용
- 하이브리드 환경: 용도별 인덱스 분리 운영
- 성능 모니터링: 실제 워크로드 기반 최적화
이 문서는 PostgreSQL 13+ 버전을 기준으로 작성되었습니다.
댓글 (0)