인덱스에 대해 알고 있는 정보를 정리합니다.
잘못된 정보가 있으면 지적 부탁드립니다.
Overview
인덱스는 "목차" 라고 할 수 있습니다.
예를 들어 책에서 어떤 단어의 위치를 찾으려면 책을 전부 다 봐야하지만 가나다순으로 목차를 만들어두면 쉽게 찾을 수 있습니다.
목차는 순서대로 정렬되어 있기 때문에 데이터를 더 빠르게 찾을 수 있게 도와줍니다.
하지만 목차를 넣으면 별도 페이지를 만들어야 하기 때문에 책이 조금 더 두꺼워집니다.
그리고 새로운 단어가 추가되면 목차에도 추가해줘야 하고 중간 단어를 넣는다면 순서를 조정해서 페이지도 다시 만들어야 합니다.
1. 인덱스란
인덱스는 위에서 설명한 목차와 비슷합니다.
어떤 데이터를 찾을 때 DB 테이블을 찾는 대신 미리 만들어둔 인덱스를 먼저 탐색합니다.
인덱스를 설정하면 특정 컬럼들을 키 값으로 메모리 영역에 트리 구조로 저장해둡니다.
그리고 디스크 저장소에 바로 접근하는 대신 메모리 저장소에 있는 인덱스를 먼저 조회해서 빠르게 데이터를 가져올 수 있습니다.
인덱스가 데이터를 빠르게 가져올 수 있는 이유는 항상 정렬된 상태를 유지하기 때문입니다.
이를 위해 데이터가 추가/삭제 될 때마다 자료구조를 정렬하기 때문에 인덱스는 SELECT 성능을 향상시키는 대신 INSERT, UPDATE, DELETE 의 성능이 떨어지게 됩니다.
2. 인덱스 종류
인덱스 종류는 어떤 자료구조를 사용하냐에 따라 나눌수도 있고, 데이터 저장 방식에 따라 클러스터드 (Clustered) 인덱스와 넌클러스티드 (Non Clustered) 인덱스로 나누기도 합니다.
2.1. Clustered Index vs Non-Clustered Index
- Clustered Index
- 이름 그대로 인접한 데이터들을 한곳으로 모았다는 뜻
- PK 설정 시 자동으로 클러스터드 인덱스로 만들어짐
- 테이블당 1개씩만 허용
- 물리적인 데이터를 갖고 있음
- 항상 정렬된 상태를 유지하고 노드 내에서도 정렬되어 있음
- Non Clustered 인덱스에 비해 조회 속도가 빠르지만 삽입/수정/삭제는 더 느림
- Non Clustered Index
- UNIQUE 로 설정된 컬럼에 자동으로 생성됨
- 인덱스 페이지는 로그 파일에 저장됨
- 레코드의 원본은 정렬되지 않고 인덱스 페이지만 정렬됨
2.2. Primary Index vs Secondary Index
- Primary Index
- PK (기본키) 를 기반으로 만들어진 인덱스
- PK 는 하나만 존재할 수 있기 때문에 Primary Index 도 단 하나만 존재
- Secondary Index
- 기본키는 아니지만 성능 향상을 위해 임의의 컬럼을 지정해서 만든 인덱스
- 여러 개의 Secondary Index 가 존재할 수 있음
2.3. 자료구조에 따른 분류
- B-Tree 인덱스
- Hash 인덱스
- 컬럼 값을 해싱해서 사용하며 매우 빠른 검색 가능
- 컬럼 값과 인덱스 키 값이 일치하지 않기 때문에 문자열 검색과 같이 일부 일치에 대해 검색 불가능
- Fractal-Tree 인덱스
- B-Tree 인덱스의 단점을 보완하기 위해 만듬
- 컬럼 값을 변형하지 않으며 데이터의 저장/삭제 처리 비용을 많이 줄임
- 아직 많이 사용되지는 않음
3. B-Tree 인덱스
Balanced Tree 의 약자로서 데이터베이스 인덱싱 알고리즘 가운데 가장 일반적으로 사용되는 알고리즘 입니다.
B-Tree 인덱스는 컬럼의 값을 변경시키지 않고 구조체 내에서 항상 정렬된 상태를 유지합니다.
B-Tree 는 최상위에 루트 (Root) 노드가 존재하고 하위에 브랜치 (Branch) 노드, 마지막에 리프 (Leaf) 노드로 되어 있습니다.
부모 노드를 기준으로 왼쪽 자식 노드는 더 작은 값 오른쪽 자식 노드는 더 큰값을 갖고 있습니다.
3.1. 왜 B-Tree 인가?
인덱스로 사용할 수 있는 자료구조는 여러 개가 있을 겁니다.
Tree 구조의 Worst 시간복잡도는 한쪽으로 모든 자식 노드가 쏠려있는 형태인 O(n) 입니다.
그래서 우리는 자식 노드가 양쪽에 골고루 퍼져있는 Balanced Tree 를 사용합니다.
Balanced Tree 중에는 RedBlack Tree 도 있는데 왜 사용하지 않을까요?
해시 테이블은 O(1) 인데 왜 사용하지 않을까요?
3.2. 다른 트리 구조를 사용하지 않는 이유
위에서 잠시 언급한 RedBlack Tree 는 B-Tree 와 마찬가지로 정렬된 상태와 밸런스를 유지합니다.
그럼 B-Tree 와 차이가 없을 것 같은데 왜 사용하지 않을까요?
가장 큰 차이점은 B-Tree 는 노드 하나에 여러 개의 데이터를 저장할 수 있다는 겁니다.
노드에서 배열 형태로 여러 데이터를 저장할 수 있기 때문에 트리 포인터를 참조해서 계속 depth 를 타고 들어가는 것보다 효율적이고 이는 데이터가 많아질수록 차이가 두드러집니다.
3.3. Hash 테이블을 사용하지 않는 이유
해시 테이블은 Hash 함수를 사용해서 키 값을 해싱한 후에 테이블에 저장합니다.
해시 테이블은 분명 한 가지 키에 대한 탐색은 효율적입니다.
하지만 데이터가 정렬되어 있지 않기 때문에 부등호 (<, >) 를 사용하지 못한다는 단점이 있습니다.
3.4. B-Tree 인덱스의 쿼리별 특징
SELECT
- 특정 키 값을 찾기 위해 자식 노드를 계속 타고 들어가는 방식
- 마지막 리프 노드에는 레코드의 주소가 존재하고 이 값으로 테이블 레코드를 찾을 수 있음
INSERT
- B-Tree 에 새로운 키값을 저장할 때는 우선 적절한 위치를 찾아야함
- 새로운 키값과 레코드 정보는 리프 노드에 저장
- 만약 리프 노드가 꽉찼다면 트리를 재구성하여 리프 노드를 분리
- 분리 과정에서 해당 리프 노드의 부모 노드까지 영향이 갈 수 있음
- 이러한 이유로
INSERT 작업은 상대적으로 비용이 많이 듬
- 인덱스가 많으면 많을수록 이런 비용이 추가로 들기 때문에 너무 많은 인덱스를 추가하는 건 성능에 영향을 줌
DELETE
- B-Tree 에서 키 값 삭제는 간단
- 해당 키를 찾아서 삭제 마크만 하면 작업이 완료
- 삭제 마킹된 인덱스 키 공간은 그대로 두거나 재활용 가능
UPDATE
- 인덱스는 항상 정렬된 상태로 유지됨
- 단순히 인덱스 키 값을 수정한다면 트리의 전체 구조를 바꿔야 할 수도 있음
- 그래서 B-Tree 에선 키 변경이 아닌 기존 키 삭제 (DELETE) 후 새로운 키 추가 (INSERT) 방식을 사용
- 따라서 키 값의 잦은 수정은 성능에 큰 영향을 미침
4. 인덱스 설정 시 고려사항
인덱스는 조회 속도를 향상시키지만 어느정도 오버헤드가 존재하기 때문에 아무렇게나 추가해버리면 안됩니다.
4.1. 인덱스의 갯수
인덱스의 갯수는 3 ~ 4 개가 적당합니다.
인덱스의 갯수가 너무 많으면 다음과 같은 이슈가 존재합니다.
- 데이터 삽입/수정/삭제 시마다 인덱스도 같이 추가하거나 수정/삭제 해주어야 해서 성능상 이슈가 존재
- 데이터 삽입시마다 인덱스도 같이 추가하기 때문에 인덱스가 늘어날수록 더 많은 메모리를 차지함
- 인덱스가 많아지면 옵티마이저가 잘못된 인덱스를 선택할 확률이 높아짐 (인덱스 힌트로 원하는 인덱스를 지정할 순 있음)
4.2. 인덱스를 걸기에 적절한 컬럼
인덱스의 갯수에 한계가 있다면 적절한 인덱스 컬럼을 정하는 것도 중요합니다.
인덱스는 카디널리티 (Cardinality) 가 높은 컬럼에 지정하는 게 좋습니다.
카디널리티가 높다는 말은 데이터의 중복이 적다는 뜻인데 대표적으로 ID, 주민번호 등이 있습니다.
반대로 성별 같은 중복된 데이터가 많은 경우 카디널리티가 낮다고 표현합니다.
성별에 인덱스를 거는 경우 인덱스를 타더라도 남/녀 두가지만 존재하기 때문에 결국 나머지 조건에 맞는 데이터는 직접 풀스캔을 해서 찾아야 합니다.
하지만 ID 같이 중복된 값이 없는 경우 해당하는 데이터를 빠르게 찾을 수 있습니다.
4.3. 읽어야 하는 레코드 갯수
인덱스는 일반적으로 단 하나의 데이터를 구할 때 가장 효율적입니다.
여러 개의 데이터를 구한다면 인덱스를 통해 레코드의 주소를 찾아 데이터의 레코드를 읽는 작업을 반복해야 합니다.
그래서 만약 많은 레코드를 한번에 조회한다면 오히려 인덱스를 사용하지 않고 직접 테이블을 읽는 것이 더 효율적일 수 있습니다.
예를 들어 테이블에 10 개의 데이터가 존재하고, 5건의 데이터를 읽는다고 가정한다면 인덱스를 통하는 것보다 테이블을 직접 읽는 게 효율적일 수도 있습니다.
일반적으로 DBMS 의 옵티마이저는 인덱스를 사용해 레코드 1건을 읽는 것이 테이블에서 직접 읽는 것보다 4 ~ 5배 정도 비용이 더 많이 든다고 예측합니다.
그러므로 인덱스를 통해 읽어야 할 레코드가 전체 테이블의 20 ~ 25% 이상이라면 직접 테이블을 읽는 것이 효율적입니다.
사실 인덱스가 걸려있어도 옵티마이저가 판단하여 더 효율적이라고 생각되는 방법을 선택하기 때문에 개발자가 직접 고려할 일은 없지만 기본적으로 알 고 있으면 좋습니다.
4.4. 복합 인덱스를 구성할 때
인덱스는 여러 개의 컬럼을 동시에 지정할 수도 있는데 어떤 순서로 구성하느냐에 따라 성능이 달라집니다.
위에서 인덱스는 트리 구조로 되어있다고 했는데, 여러 개의 컬럼을 함께 키 값으로 지정하는 경우 먼저 첫 번재 컬럼을 기준으로 정렬된 뒤에 두번째 컬럼이 정렬되어 있습니다.
이 말은 즉 첫 번째 컬럼 없이 두 번째 컬럼만 갖고 인덱스를 조회하면 제대로 된 위치를 찾을 수 없다는 뜻입니다.
그러므로 복합 인덱스를 구성했다면 조회할 때 앞 순서의 조건을 반드시 포함해야 인덱스를 태울 수 있습니다.
예를 들어 A, B, C 컬럼 순으로 인덱스를 구성했다면 A 라는 컬럼을 조회 조건에 포함해야 최소한의 인덱스를 태울 수 있고 B, C 컬럼만 조회 조건에 있다면 인덱스를 타지 못합니다. (정확히 말하면 인덱스 풀 스캔을 하는데 이런 경우 일반적으로 인덱스를 타지 않는다고 표현)
그리고 여러 개의 컬럼이 있다면 카디널리티가 높은 순에서 낮은 순으로 지정하는게 인덱스의 효율을 이끌어낼 수 있습니다.
그리고 과거에는 인덱스의 컬럼 순서와 조회 컬럼 순서를 맞춰야 인덱스를 탔지만 최근에는 옵티마이저가 알아서 인덱스 순서에 맞춰주기 때문에 거의 차이가 없습니다.
그래도 재배열하는 과정을 생략하기 위해 최대한 맞추는게 좋긴 합니다.
5. 인덱스 사용 시 주의사항
지금까지도 조금씩 언급했지만 인덱스는 사용할 대 주의할 점이 몇개 존재합니다.
- 다중 인덱스를 사용할 때 범위 조건은 인덱스를 타지만 이후 컬럼들은 인덱스를 타지 않음
- 인덱스로 지정한 컬럼은 그대로 사용해야 함
WHERE age * 10 > 20 처럼 조회조건에 있는 컬럼을 변경하면 안됨WHERE age > 20 / 10 처럼 컬럼을 그대로 사용해야 함
6. InnoDB Adaptive Hash Index
MySQL 은 기본으로 InnoDB 를 사용하고 InnoDB 는 B-Tree 를 사용합니다.
PK 가 아닌 컬럼으로 인덱스를 지정하면 Secondary Index 가 생성됩니다.
그래서 인덱스로 컬럼을 조회하면 Secondary 인덱스를 기반으로 PK 를 찾은 뒤 다시 Primary Index 로 데이터를 찾아냅니다.
인덱스를 두번 타기 때문에 2 * O(log n) 비용이 듭니다.
그래서 자주 사용되는 컬럼을 해시로 정의해서 B-Tree 를 타지 않고 바로 데이터에 접근할 수 있게 하는 걸 Adaptive Hash Index 라고 합니다.
미리 캐싱한 해시값으로 조회하기 때문애 O(1) 의 속도를 보여주지만 어떤 값을 해싱할지는 옵티마이저가 판단하기 때문에 제어할 수 없다는 약점이 있습니다.
7. Covering Index
일반적으로 인덱스를 설계할 때는 WHERE 절에 대해서만 이야기하지만 사실 쿼리 전체에 대해 인덱스 설계가 필요합니다.
인덱스를 사용하면 특정 컬럼 값을 키로 하여 데이터의 주소값을 구한 뒤 해당 주소값으로 다시 테이블에 접근해서 최종 데이터를 구합니다.
커버링 인덱스란 인덱스에 이미 필요한 데이터가 전부 존재해서 테이블에 접근할 필요가 없는 인덱스를 의미합니다.
예를 들어 (A, B) 컬럼으로 인덱스를 구성한 경우 SELECT * FROM table WHERE A = ? 와 같은 형식으로 쿼리를 사용하면 인덱스를 탄 후에 전체 컬럼값을 모두 구하기 위해 테이블에 접근합니다.
하지만 SELECT A, B FROM table WHERE A = ? 와 같이 구하려는 컬럼값이 모두 인덱스에 이미 존재한다면 테이블에 다시 접근할 필요가 없습니다.
인덱스는 기본적으로 Non Clustered Index 에서 먼저 값을 구하고 Clustered Index 에서 다시 데이터를 구합니다.
여기서 커버링 인덱스가 사용되었다는건 Clustered Index 까지 통하지 않고 Non Clustered Index 만으로도 데이터를 구할 수 있다는 뜻입니다.
커버링 인덱스가 적용되면 EXPLAIN 실행 시 Extra 필드에 Using index 라고 표시됩니다.
Reference
