인덱스(Index) 사용해 쿼리 성능 올리기 B-tree (Balanced Tree)

testdb=# explain analyze select * from users where username ='user_54321';
                                            QUERY PLAN
--------------------------------------------------------------------------------------------------
 Seq Scan on users  (cost=0.00..189.05 rows=1 width=21) (actual time=0.415..0.415 rows=0 loops=1)
   Filter: (username = 'user_54321'::text)
   Rows Removed by Filter: 10004
 Planning Time: 0.059 ms
 Execution Time: 0.436 ms
(5개 행)

 

• Seq Scan은 전체 테이블을 처음부터 끝까지 스캔하면서 조건을 일일이 검사한다.
• 조건에 맞는 row가 없더라도 전체를 다 뒤지므로 비효율적이다.
• Rows Removed by Filter: 10004는 전체 row를 검사했다는 뜻.

 

 

 

▶ 인덱스 추가

 

testdb=# create index idx_username on users(username);
CREATE INDEX

testdb=# explain analyze select * from users where username = 'user_54321';
                                                     QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
 Index Scan using idx_username on users  (cost=0.29..8.30 rows=1 width=21) (actual time=0.034..0.034 rows=0 loops=1)
   Index Cond: (username = 'user_54321'::text)
 Planning Time: 0.341 ms
 Execution Time: 0.046 ms
(4개 행)

 

 

 

인덱스 생성 전에는 filter 조건으로 전체 테이블을 순회하며 필터링하고 인덱스 생성후는 조건에 맞는 row만 빠르게 검색함  

 

 

B-tree 인덱스 작동 원리

PostgreSQL에서 기본 인덱스는 B-tree (Balanced Tree) 인덱스이다.

1. 트리 구조

• B-tree는 균형 이진 탐색 트리의 확장판으로, N진 트리이다.
• 모든 리프 노드의 깊이가 같아서 탐색 시간이 일정하다.
• 각 노드는 여러 개의 key 값을 포함할 수 있고, 자식 노드들도 여러 개 가질 수 있다.

2. 검색 과정 (WHERE username = 'user_54321')

1. 루트 노드에서 시작 → key 값들과 비교
2. 조건에 맞는 하위 노드로 내려감
3. 리프 노드에 도달하면 → 해당 key 값 찾기
4. 찾은 key가 가리키는 row 위치(=tuple pointer) 로 이동

 

 

3. 정렬 유지

• B-tree는 항상 정렬된 상태를 유지한다.
• 따라서 ORDER BY username, BETWEEN, LIKE 'abc%' 같은 쿼리도 빠르게 동작함.

 

 

4. 삽입/삭제 시

• 데이터가 추가되면 B-tree 구조가 자동으로 재조정된다.
• 노드가 가득 차면 분할(split), 삭제 시 병합(merge)되면서 균형 유지.