데이터베이스 인덱싱 처리 과정
B+ Tree 인덱스를 활용한 데이터 탐색 및 삽입 성능 비교 시각화
개요
데이터베이스 인덱싱은 대규모 테이블에서 조건에 맞는 데이터를 고속으로 조회하기 위해 별도의 정렬된 자료구조를 유지 관리하는 핵심 성능 최적화 기법입니다.
왜 Full Table Scan은 느린가?
인덱스가 없는 테이블에서 특정 레코드를 조회할 때 스토리지 엔진은 테이블 전체 디스크 블록을 맨 처음부터 끝까지 전수 검사합니다.
- 임의 디스크 I/O 발생: 필요한 데이터 페이지를 확인해야 하며, 버퍼 풀에 없는 페이지는 저장장치에서 읽어야 하므로 비용이 커질 수 있습니다.
- 선형 시간복잡도 O(N): 최악의 경우 찾는 행이 마지막 블록에 있어 검색 시간이 전체 레코드 수에 비례하여 급증합니다.
B+ Tree 인덱스의 내부 저장 구조
많은 데이터베이스는 인덱스 키를 B+ Tree로 관리합니다. 인덱스 리프에 저장되는 값은 저장 엔진과 클러스터형·보조 인덱스 유형에 따라 행 데이터 또는 행을 찾는 식별자일 수 있습니다.
- 루트 및 브랜치 노드 (Non-Leaf): 탐색 분기점(이정표) 역할만 수행하며, 자식 노드를 가리키는 키와 포인터만 저장하여 단일 노드당 수용량을 극대화합니다.
- 리프 노드 (Leaf Node): 정렬된 키와 행 데이터 또는 행 식별자가 저장되며, 인접한 리프 페이지를 연결하는 구현에서는 범위 검색(Range Scan)을 효율적으로 처리할 수 있습니다.
SELECT 쿼리 실행 시 인덱스 탐색 과정
SELECT * FROM users WHERE id = 42 실행 시 옵티마이저와 스토리지 엔진의 동작 흐름입니다.
- 옵티마이저 실행 계획 수립: 비용 기반(CBO) 분석을 통해 Full Scan보다 인덱스 포인트 룩업(Point Lookup)이 유리하다고 판단합니다.
- B+ Tree 하향 탐색 (Traversal): 루트 노드에서 키 값을 비교하여 서브 브랜치를 거쳐 최하단 리프 노드로 O(log N) 단계만에 도달합니다.
- 물리 디스크 직접 점프 (RID Lookup): 리프 노드에 저장된 ROWID(페이지 번호 + 슬롯 번호)를 건네받아 해당 블록으로 직접 점프(Direct I/O)하여 대상 레코드를 메모리로 로드합니다.
INSERT 시 발생하는 노드 분할 (Node Split)
데이터가 새로 추가될 때 인덱스의 정렬 상태와 균형을 유지하기 위한 재조정 과정입니다.
- 리프 노드 용량 초과: 타겟 리프 노드에 빈 공간이 없으면 노드를 50:50으로 절반 분할합니다.
- 부모 노드 키 승격: 중앙 키 값을 상위 브랜치 노드로 승격(Promote)시키며, 필요 시 루트 노드까지 연쇄 분할되어 트리 높이가 1 증가합니다.
- 쓰기 오버헤드: 노드 분할로 인해 쓰기(INSERT/UPDATE/DELETE) 속도는 다소 느려지지만, 탐색 깊이가 균일하게 유지되어 일관된 조회 성능을 보장합니다.
핵심 단계
- 1
왜 Full Scan은 느린가? — 인덱스가 존재하지 않아 테이블 전체 레코드를 순차 검색하므로 디스크 I/O가 매 페이지마다 발생하여 조회 속도가 현저히 느려집니다.
- 2
인덱스는 어떻게 만들어지는가? — 테이블의 특정 컬럼 키들을 모아 오름차순으로 정렬한 뒤, 계층식 B+ Tree 인덱스를 저장소에 구축합니다. 접근 빈도가 높은 인덱스 페이지는 버퍼 풀에 캐시될 수 있습니다.
- 3
데이터가 추가되면 인덱스는 어떻게 갱신되는가? — 레코드가 새로 추가될 때 인덱스 리프 노드 용량이 초과되면 노드를 분할하는 Node Split이 작동해 인덱스 구조를 실시간 재조정합니다.
- 4
SELECT가 실행되면 어떤 일이 일어나는가? — 특정 키 값을 타겟으로 하는 SELECT 쿼리가 실행되면, Full Scan을 배제하고 인덱스 트리를 진입점으로 삼아 탐색에 돌입합니다.
- 5
B+ Tree는 어떻게 탐색되는가? — 메모리 상의 루트 노드에서 키 값을 비교한 뒤 해당되는 서브 브랜치를 거쳐 최하위 리프 노드까지 점진적으로 하강해 나갑니다.
- 6
실제 데이터는 어떻게 찾는가? — 도달한 단말 리프 노드의 ROWID 또는 물리 주소 값을 참조하여 디스크 상의 목표 블록 위치로 다이렉트 I/O 액세스를 수행합니다.
- 7
왜 이것이 빠른가? — 테이블 전체 블록을 검색하는 대신 트리 높이에 비례하는 인덱스 페이지 접근으로 후보 행을 좁혀 필요한 데이터 페이지만 읽을 수 있기 때문입니다. 실제 I/O 횟수는 캐시와 인덱스 구성에 따라 달라집니다.