데이터베이스 인덱싱이란? B-tree 구조로 살펴보는 인덱스의 원리
1. 인덱싱이란?
인덱스는 데이터베이스에서 검색 성능을 높이기 위한 도구입니다.
-
테이블에 인덱스를 추가하면, 특정 열(칼럼)에 대해 빠르게 검색할 수 있게 도와주는 자료 구조(B-tree, 해시 테이블 등)를 생성합니다.
-
이 과정에서 인덱스는 일종의 "목차" 역할을 하며, 데이터베이스는 인덱스를 통해 테이블의 위치를 빠르게 찾아갈 수 있습니다.
2. 인덱스와 일반 SELECT 문 비교
인덱스 없는 경우 (일반 SELECT):
-
일반적으로 데이터베이스는 모든 행을 처음부터 끝까지 스캔해서 원하는 조건을 만족하는 데이터를 찾습니다.
-
이를 풀 테이블 스캔이라 부르며, 테이블이 클수록 시간이 많이 걸립니다.
예시:SELECT * FROM table WHERE age >= 15;
→ 테이블의 모든 데이터를 스캔해age >= 15인 데이터를 찾음.
인덱스가 있는 경우:
-
인덱스를 사용하면, 인덱스 테이블에서 먼저 조건을 만족하는 데이터의 위치(id)를 찾고, 그
id값을 바탕으로 실제 테이블에서 데이터를 가져옵니다. -
이로 인해 데이터베이스는 전체 테이블을 스캔하지 않고도 빠르게 필요한 데이터를 찾아낼 수 있습니다.
3. 인덱스는 단순한 복사본이 아니다
- 처음에는 인덱스를 특정 칼럼을 따로 복사해둔 것처럼 생각할 수 있지만, 실제로는 B-tree 같은 효율적인 자료 구조로 관리됩니다.
- B-tree는 데이터를 중간값을 기준으로 나누는 구조이기 때문에, 원하는 값을 찾을 때 전체 데이터를 하나하나 확인하지 않고도 빠르게 접근할 수 있습니다.
4. B-tree 구조의 장점
B-tree는 이진 탐색을 기반으로 하여 중간값을 기준으로 왼쪽 또는 오른쪽으로 이동하면서 데이터를 찾습니다.
- 이렇게 절반씩 나눠가며 데이터를 검색하기 때문에, 최악의 경우라도 탐색 횟수를 크게 줄일 수 있습니다.
- 탐색 복잡도는 O(log n): 데이터가 많아져도 인덱스를 사용한 검색은 선형 검색(O(n))보다 훨씬 빠릅니다..
- 정렬된 상태 유지: 인덱스는 항상 정렬된 상태로 유지되므로, 검색할 때 효율적입니다.
5. 예시로 보는 인덱스의 작동 방식
다음과 같은 테이블이 있다고 가정해봅시다:
| id | name | age |
|---|---|---|
| 1 | 철수 | 10 |
| 2 | 영희 | 15 |
| 3 | 맹구 | 11 |
| 4 | 짱구 | 50 |
- 여기서 age 열에 인덱스를 추가하면, 데이터베이스는 age 값에 대한 B-tree 인덱스를 생성합니다.
B-tree 인덱스는 대략 다음과 같습니다:
| age | id |
|---|---|
| 10 | 1 |
| 11 | 3 |
| 15 | 2 |
| 50 | 4 |
- 만약
age >= 15조건으로 검색하면, B-tree 구조에서 중간값(예: 15)을 기준으로 절반씩 필터링이 되면서 검색을 시작해 필요한 데이터를 보다 빠르게 찾습니다.
6. 인덱스가 항상 빠르진 않다?
-
인덱스는 대부분의 경우 검색 성능을 크게 향상시킵니다. 하지만 특정 상황에서는 인덱스가 효율적이지 않을 수도 있습니다.
-
예를 들어, age <= 10을 찾을 때는 B-tree 구조가 중간부터 시작해 계속 왼쪽으로 내려가야 합니다.
이 경우 최악의 상황에서는 트리의 마지막 노드까지 탐색할 수 있습니다. 하지만 이런 상황에서도 여전히 전체 테이블을 스캔하는 것보다는 빠릅니다.
7. 인덱스가 필요한 이유
-
인덱스는 데이터를 많이 처리하는 환경에서 쿼리 성능을 극대화하는 중요한 역할을 합니다.
-
특히, 테이블이 커지면 인덱스를 사용하지 않은 검색은 시간이 오래 걸릴 수 있기 때문에,
대용량 데이터 처리나실시간 시스템에서는 필수적으로 사용됩니다.
