Database 인덱스(index)란?

일단 해볼게·2023년 4월 30일

Index db

CS

목록 보기

8/10

DB 인덱스란?

추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조
데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있다.

인덱스의 장점 및 단점

장점

SELECT 성능이 향상된다.
테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
전반적인 시스템의 부하를 줄일 수 있다.

단점

인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
인덱스를 관리하기 위해 추가 작업이 필요하다.
인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.

인덱스를 사용하면 좋은 경우

규모가 작지 않은 테이블
INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
데이터의 중복도가 낮은 컬럼
기타 등등

인덱스가 적용된 컬럼의 연산

INSERT: 새로운 데이터에 대한 인덱스를 추가함
DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가함

→ 만약 어떤 테이블에 UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10만건이지만 인덱스는 훨씬 많이 존재하게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 것이다.

어떤 컬럼에 인덱스를 설정하는게 좋을까?

카디널리티가 높을 수록 인덱스 설정에 좋은 컬럼
- 한 컬럼이 갖고 있는 값의 중복 정도가 낮을 수록 좋다.
  
  예를 들어, 10개 rows를 가지는 ‘학생’ 테이블에 ‘학번’과 ‘이름’ 컬럼이 있다고 가정한다.
- ‘학번’은 학생마다 부여 받으므로 10개 값 모두 고유하다.
  - 중복 정도가 낮으므로 카디널리티가 낮다.
- ‘이름’은 동명이인이 있을 수 있으니 1~10개 사이의 값을 가진다.
  - 중복 정도가 ‘학번’에 비해 높으므로 카디널리티가 높다고 표현할 수 있다.
선택도가 낮을 수록 인덱스 설정에 좋은 컬럼
- 선택도 = 컬럼의 특정 값의 row 수 / 테이블의 총 row 수 * 100
- = 컬럼의 값들의 평균 row 수 / 테이블의 총 row 수 * 100
  
  예를 들어, 10개 rows를 가지는 ‘학생’ 테이블에 ‘학번’, ‘이름’, ‘성별’ 컬럼이 있다고 가정한다.
  
  학번은 고유하고, 이름은 2명씩 같고, 성별은 남녀 5:5 비율이다.
- ‘학번’의 선택도 = 1/10*100 = 10%
  - SELECT COUNT(1) FROM '학생' WHERE '학번' = 1; (모두 고유하므로 특정 값: 1)
- ‘이름’의 선택도 = 2/10*100 = 20%
  - SELECT COUNT(1) FROM '학생' WHERE '이름' = "김철수"; (2명씩 같으므로 특정 값: 2)
- ‘성별’의 선택도 = 5/10*100 = 50%
  - SELECT COUNT(1) FROM '학생' WHERE '성별' = F; (5명씩 같으므로 특정 값: 5)
  
  즉, 선택도는 특정 필드값을 지정했을 때 선택되는 레코드 수를 테이블 전체 레코드 수로 나눈 것

활용도가 높을 수록 인덱스 설정에 좋은 컬럼
- 해당 컬럼이 실제 작업에서 얼마나 활용되는지에 대한 값
- WHERE 절에 자주 활용되는지를 판단
중복도가 없을 수록 인덱스 설정에 좋은 컬럼

대표적인 인덱스의 종류

1. Hash

컬럼의 값으로 해시값을 계산해서 인덱싱
단일 검색(=)은 O(1)이지만 범위 검색에 좋지 않다.

2. B-Tree

컬럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱
노드 하나에 여러 데이터가 저장한다. 각 노드 내 데이터들은 항상 정렬된 상태이며, 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가진다.
참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.
- 참조 포인터로 메모리에 접근한다는 것은, 실제 메모리 상 순서대로 저장이 되었든 안 되었든 접근하려는 주소를 연산을 통해 직접 알아내어 데이터에 접근한다.주소를 알아내는데 CPU 내부적으로 많은 연산을 수행하게 될 것이다.
- 그러나 B-Tree는 배열은 데이터들이 메모리 공간에 차례대로 저장이 되어 있으므로 접근할 주소를 바로 알 수 있다. 비록 B-Tree도 자식 노드를 접근할 땐 참조 포인터로 접근을 하지만, 하나의 노드가 가지는 데이터 개수가 많아질수록 포인터 개수는 확연히 줄어들고, 트리 내에서 다루는 데이터가 많아질수록 이러한 차이는 더욱 커질 것이다.
  
  가장 상단의 노드를 '루트 노드(Root Node)', 중간 노드들을 '브랜치 노드(Branch Node)', 가장 아래 노드들을 '리프 노드(Leaf Node)'라고 한다.

인덱스 레코드를 찾아가는 과정
- 1단계. 브랜치 블록의 가장 왼쪽 값이 찾고자 하는 값보다 작거나 같으면 왼쪽 포인터로 이동
- 2단계. 찾고자 하는 값이 브랜치 블록의 값 사이에 존재하면 가운데 포인터로 이동
- 3단계. 오른쪽에 있는 값보다 크면 오른쪽 포인터로 이동
- 이 과정을 리프 블록을 찾을 때까지 반복한다. 리프 블록에서 찾고자 하는 값이 존재하면 해당 값을 찾은 것이고, 해당 값이 없으면 해당 값은 존재하지 않아 검색에 실패하게 된다.

3. B+Tree

B-tree의 확장개념으로, B-tree의 경우, 루트 노드 또는 브랜치 노드에 key와 data를 담을 수 있다. 하지만, B+tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않는다. 오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 **Linked list**로 연결되어 있다.
InnoDB 스토리지 엔진은 B+Tree를 사용

인덱스 레코드를 찾아가는 과정
- B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다. B-tree의 경우에는 모든 노드를 확인해야 한다.

구분	B-tree	B+tree
데이터 저장	리프 노드, 브랜치 노드 모두 데이터 저장 가능	오직 리프 노드에만 데이터 저장 가능
트리의 높이	높음	낮음(한 노드 당 key를 많이 담을 수 있음)
풀 스캔 시, 검색 속도	모든 노드 탐색	리프 노드에서 선형 탐색
키 중복	없음	있음(리프 노드에 모든 데이터가 있기 때문)
검색	자주 access 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울 경우, 브랜치 노드에도 데이터가 존재하기 때문에 빠름	리프 노드까지 가야 데이터 존재
링크드 리스트	없음	리프 노드끼리 링크드 리스트로 연결