데이터베이스 인덱싱
데이터베이스에서 인덱스라는 것은 특정 컬럼에 대해 색인을 생성하여 빠르게 데이터를 찾는 방법입니다.
가장 흔하게 드는 예시가 책에서의 색인인데요.
책에서 특정 단어를 찾는 경우, 처음부터 끝까지 모든 페이지를 읽을 필요가 없이, 책의 맨 앞이나 뒤에 있는 목차(색인, Index)를 활용해 단어가 나오는 페이지를 빠르게 찾을 수 있습니다.
이거처럼 데이터베이스의 인덱스도 같은 역할을 하는데요.
테이블의 특정 컬럼에 대해 색인을 생성해서 빠르게 데이터를 찾을 수 있도록 합니다.
인덱스의 작동 원리를 예시를 통해 알아보겠습니다.
아래와 같이 고객 정보를 저장한 테이블이 있다고 가정해 보겠습니다.
| ID | 이름 | 나이 | 지역 | 성별 |
| 1 | 김철수 | 30 | 서울 | 남 |
| 2 | 이영희 | 25 | 부산 | 여 |
| 3 | 박민수 | 35 | 대구 | 남 |
| 4 | 최수진 | 28 | 서울 | 여 |
| 5 | 장길동 | 40 | 인천 | 남 |
이런 데이터에 대해서 아래와 같이 조회 쿼리를 한다고 가정하면
SELECT * FROM 고객 WHERE 이름 = '박민수';
인덱스가 없다면 해당 데이터를 찾기 위해 테이블의 첫 번째 행부터 마지막 행까지 하나씩 확인하며 '박민수'라는 이름의 데이터를 찾습니다.
그렇기 때문에 데이터가 많아질수록 시간이 오래 걸리게 되는데요.
이걸 풀 테이블 스캔(Full Table Scan)이라고 합니다.
하지만 만약 `이름` 컬럼에 인덱스를 생성하면, 데이터베이스는 아래와 같은 별도 자료 구조(B-트리 또는 해시맵 등)를 사용해 `박민수`의 위치를 빠르게 찾습니다.
인덱싱을 하는 방법에는 B-트리 인덱스, 비트맵 인덱스, 함수 기반 인덱스 등이 있습니다.
B-트리 인덱스
B-트리는 데이터베이스 인덱스에서 가장 일반적으로 사용되는 자료 구조입니다.
B-트리 인덱스는 데이터를 계층적 구조로 저장하며, 각 노드는 여러 키와 포인터를 가지고 있습니다.
검색, 삽입, 삭제가 모두 효율적으로 이루어지며,
데이터는 삽입이나 삭제가 이뤄지더라도 자동으로 정렬된 상태로 유지됩니다.
- B-트리 인덱스는 루트 노드에서 시작하여 리프 노드에 도달할 때까지 검색합니다.
- 각 노드는 정렬된 상태로 키를 저장하며, 키와 키 사이의 범위를 포인터로 연결합니다.
- 리프 노드에는 데이터나 데이터가 저장된 위치를 가리키는 포인터가 포함됩니다.
예를 들어 위에 고객 정보를 예시로 들면
`이름`을 인덱스 키 값으로 잡았다고 치면
테이블 데이터: 인덱스 구조 (B-트리)
-------------------------------------------
ID 이름 나이 지역 이름 ID
1 김철수 30 서울 김철수 1
2 이영희 25 부산 박민수 3
3 박민수 35 대구 이영희 2
4 최수진 28 서울 최수진 4
5 장길동 40 인천 장길동 5 박민수
/ \
김철수 최수진
/ \ / \
ID 1 ID 2 ID 5 ID 4
이러한 형태로 B-트리가 이루어지게 되는데, 이름을 기준으로 물리적인 위치(ID)가 맵핑돼서 함께 저장되게 됩니다.
그리고
SELECT * FROM 고객 WHERE 이름 = '장길동';
이 쿼리를 실행한다고 치면 아래와 같은 순서대로 값을 찾아가게 되는데요.
- 루트 노드에서 시작: `장길동`은 루트 키 값 `박민수`보다 크므로 오른쪽으로 이동
- 오른쪽 자식 노드 `최수진`과 비교 => `장길동`은 `최수진`보다 작으므로 왼쪽으로 이동
- 리프 노드에서 키 값 `장길동`을 찾아 데이터(ID:5)를 반환
저는 여기서 "무슨 기준으로 장길동이 박민수 보다 크고, 최수진 보다 작다는 걸 비교하지?"라는 생각이 들었는데요.
답은 간단하게도 문자열이라면 사전순, 숫자라면 대소비교 등 일반적으로 사용되는 비교 방법을 통해 크고 작음을 판단하는 것이었습니다.
비트맵 인덱스
다음으로 얘기할 인덱스는 비트맵 인덱스인데요.
비트맵 인덱스는 중복 값이 많은 데이터에 적합한 인덱스입니다.
일반적인 B-트리 인덱스는 각 값의 위치를 개별적으로 저장하지만, 비트맵 인덱스는 값을 비트(bit)로 표현해 저장합니다.
비트맵 인덱스는 특정 값이 존재하는 행을 비트로 표현하며, 해당 비트의 위치를 통해 데이터를 찾습니다.
이번에도 처음에 보여드렸던 고객 데이터로 예를 들어 설명하겠습니다.
해당 고객 데이터를 비트맵 인덱스로 표현하면 아래와 같습니다.
| 성별 | 비트맵 |
| 남 | 1 0 1 0 1 |
| 여 | 0 1 0 1 0 |
`남성` 데이터를 검색하려면, 비트맵 인덱스에서 `남성`의 비트맵 (1 0 1 0 1)을 확인하고 해당 위치 (ID: 1, 3, 5)를 조회합니다.
비트맵 인덱스는 비트 단위로 데이터를 저장하므로 중복도가 높은 컬럼에서 효율적이고 AND, OR 같은 조건 검색에 빠르다는 장점이 있습니다.
반면에, 업데이트 시에 추가적인 연산이 필요하여 데이터 변경이 빈번한 테이블에는 부적합하고, 값이 너무 다양하거나 중복도가 낮은 컬럼에는 효과가 적은데요.
그럼 여기서 한 가지 의문이 생깁니다.
"B-tree도 값이 추가되면 연산이 필요할 텐데, 왜 비트맵 인덱스 방식의 단점에 추가적인 연산이 나오는 걸까?"
결론부터 이야기하면 B-tree 보다도 많은 처리가 필요하기 때문입니다.
B-tree에서의 추가적인 연산
B-tree에서 삽입/삭제 시 추가 연산은 데이터를 정렬된 상태로 유지해야 하므로, 데이터를 삽입하거나 삭제할 때 다음과 같은 연산이 필요합니다.
1) 새로운 데이터를 삽입할 위치를 찾음 (검색 연산)
2) 데이터를 삽입한 후, 트리의 균현을 맞춤 (Rebalancing)
3) 삭제 시에도 데이터 제가 후 트리를 다시 정렬하고 균형을 맞춤
즉, 필요한 추가 연산은 검색, 삽입/삭제 위치 찾기, 트리 균형 조정입니다.
이러한 연산은 비교적 효율적으로 이뤄지며, 데이터 변경이 빈번한 테이블에서 사용해도 효과적입니다.
비트맵 인덱스에서의 추가적인 연산
1) 비트 배열 업데이트
- 데이터가 삽입, 수정, 삭제될 때, 비트 배열의 특정 위치를 변경해야 합니다.
- 데이터가 변경되면 기존 비트맵 배열을 모두 읽고 수정한 뒤 다시 저장해야 합니다.
2) 병렬 처리 비효율성
- 비트맵 인덱스는 압축된 비트맵 형태로 저장되어 공간 효율적이지만, 업데이트 시 압축을 풀고 다시 압축해야 하므로 연산량이 증가합니다.
3) 변경 시 전체 데이터 영향
- 비트맵은 테이블 전체에 걸쳐 있는 데이터를 처리하므로, 한 행만 수정해도 전체 비트맵 구조에 영향을 줄 수 있습니다.
이러한 이유로 인해 데이터의 추가와 수정이 빈번한 컬럼에 대해서 비트맵 인덱스는 비효율적입니다.
함수 기반 인덱스
함수 기반 인덱스는 컬럼 값 자체가 아니라, 컬럼 값에 특정 함수가 적용된 결과를 인덱스로 저장합니다.
데이터베이스가 쿼리를 실행할 때, 동일한 함수가 포함된 조건문을 빠르게 처리할 수 있습니다.
예를 들어 설명해 보겠습니다.
아래의 고객 데이터에서 이름을 대소문자 구분 없이 검색하는 경우를 가정해 보겠습니다.
| ID | 이름 |
| 1 | Kim |
| 2 | Lee |
| 3 | kim |
| 4 | lee |
아래의 쿼리를 사용해서 검색한다고 할 때
SELECT * FROM 고객 WHERE LOWER(이름) = 'kim';
`이름` 컬럼에 대해 함수 기반 인덱스를 생성합니다.
CREATE INDEX idx_lower_name ON 고객(LOWER(이름));
이렇게 하면 특정 함수 연산이 반복적으로 수행돼야 하는 상황에서는 성능 최적화가 가능해집니다.
함수가 복잡할수록 이렇게 인덱스를 설정해 놓는 것이 유리합니다.
다만 함수 결과를 저장하므로 저장 공간이 추가로 필요하고, 데이터 변경 시 인덱스가 변경될 때 함수 실행도 필요하므로 성능 저하가 있을 수 있습니다.
인덱스 설계 시 고려사항
마지막으로 인덱스를 설계할 때 염두에 두어야 할 점을 이야기하겠습니다.
1. 필요한 컬럼만 인덱스 생성
자주 조회되거나 정렬/그룹화에 사용되는 컬럼만을 대상으로 선택해야 합니다.
인덱스가 많아질수록 데이터 변경 시 오버헤드가 증가합니다.
2. 중복도가 낮은 컬럼 선택
중복도가 낮은(값이 다양하게 분포된) 컬럼을 선택해야 검색 효율이 높아집니다.
3. 복합 인덱스
여러 컬럼을 하나의 인덱스로 설정해 복잡한 쿼리에 대해 최적화할 수도 있습니다.
만약
- `idx_이름`
- `idx_지역`
- `idx_이름_지역`
이런 식으로 인덱스들이 있는데, `이름`과 `지역`을 자주 조회한다면, 복합 인덱스(`idx_이름_지역`) 하나만 유지하고 개별 인덱스(`idx_이름`, `idx_지역`)는 삭제하는 것이 효율적입니다.