MySQL에서 사용하는 대부분의 인덱스는 B-Tree 구조로 이루어져 있다.
B-Tree는 대용량 데이터에서 빠르게 값을 찾기 위해 설계된 트리 형태의 자료 구조다.
테이블 전체를 순차적으로 검색하면 데이터가 많아질수록 조회 속도가 급격히 느려진다.
B-Tree 인덱스는 이 문제를 해결하기 위해 데이터를 정렬된 트리 구조로 관리한다.
1. B-Tree 기본 구조
B-Tree는 루트 노드(root), 내부 노드(internal node), 리프 노드(leaf node)로 구성된다.
검색은 항상 루트에서 시작해 리프 노드까지 내려가면서 진행된다.
각 노드는 여러 개의 키 값을 가지고 있고, 값 범위에 따라 다음 노드를 가리킨다.
이 구조 덕분에 검색 시 전체 데이터를 읽지 않아도 된다.
2. 검색 과정
B-Tree 인덱스에서 데이터를 찾는 과정은 다음과 같다.
- 루트 노드에서 검색 시작
- 값 범위를 비교해 다음 노드 선택
- 리프 노드까지 이동
- 리프 노드에서 실제 데이터 위치 확인
예를 들어 id=50을 찾는 경우 루트 → 내부 노드 → 리프 노드 순으로 이동한다.
이 과정에서 탐색 깊이는 보통 3~4단계 정도다.
즉 수백만 행이 있어도 몇 번의 비교만으로 데이터를 찾을 수 있다.
3. 리프 노드의 특징
B-Tree에서 실제 인덱스 데이터는 리프 노드에 저장된다.
특히 InnoDB에서는 리프 노드가 실제 데이터 레코드를 가리키는 구조다.
리프 노드는 서로 연결되어 있기 때문에 범위 검색에도 효율적이다.
이 연결 구조 덕분에 BETWEEN, ORDER BY 같은 범위 조회가 빠르게 동작한다.
4. 시간 복잡도
B-Tree의 검색 시간 복잡도는 O(log n)이다.
데이터가 증가해도 검색 속도는 크게 증가하지 않는다.
예를 들어 다음과 같은 비교가 가능하다.
- 10만 행 → 약 3~4단계 탐색
- 100만 행 → 약 4~5단계 탐색
- 1000만 행 → 약 5~6단계 탐색
이 특성 때문에 데이터베이스 인덱스 구조로 널리 사용된다.
5. B-Tree 인덱스가 잘 동작하는 경우
다음 조건에서는 B-Tree 인덱스가 매우 효율적으로 동작한다.
- 정확한 값 검색 (=)
- 범위 검색 (<, >, BETWEEN)
- 정렬 (ORDER BY)
- 접두사 검색 (LIKE 'abc%')
이 조건들은 모두 정렬된 구조를 활용할 수 있기 때문이다.
6. 인덱스가 사용되지 않는 경우
B-Tree 인덱스가 있어도 항상 사용되는 것은 아니다.
다음과 같은 경우 인덱스를 활용하기 어렵다.
- LIKE '%abc'
- 함수 적용 (YEAR(date))
- 데이터 타입 변환
- OR 조건 남용
이 경우 MySQL은 풀테이블 스캔을 수행할 가능성이 높다.
7. 클러스터드 인덱스 (InnoDB)
InnoDB에서는 기본 키(PK)가 클러스터드 인덱스로 사용된다.
즉 테이블 데이터 자체가 B-Tree 구조로 저장된다.
보조 인덱스는 PK 값을 참조하는 구조다.
따라서 보조 인덱스를 통해 데이터를 조회하면 PK 조회가 한 번 더 발생한다.
이 구조 때문에 PK는 짧고 정렬 가능한 값이 유리하다.
8. 실무 인덱스 설계 기준
- 조회 조건에 사용되는 컬럼에 인덱스 생성
- 선택도가 높은 컬럼 우선
- 복합 인덱스는 자주 사용하는 조건 순서로 구성
- 불필요한 인덱스는 제거
인덱스는 조회 속도를 높이지만 INSERT, UPDATE, DELETE 성능은 떨어뜨린다.
따라서 필요한 곳에만 설계하는 것이 중요하다.
한 줄 요약
B-Tree 인덱스는 데이터를 정렬된 트리 구조로 관리해 O(log n) 시간에 검색할 수 있도록 만든 구조다. 루트에서 리프 노드까지 탐색하며 범위 검색과 정렬에 효율적이다.
댓글 0