[DB] 인덱스 정의, 동작 방식, 종류 등 톺아보기(MySQL 기준)

인덱스란?

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.

책으로 비유하자면, 책의 맨 앞 또는 맨 뒤에 있는 색인을 데이터베이스의 index라 볼 수 있다.

 

목적

데이터베이스에서 원하는 값을 찾고자 할 때

테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에, 데이터와 데이터의 위치(주소)를 포함한 자료구조(=인덱스)를 생성하여

원하는 데이터를 빠르게 조회하기 위함이다.

 

그렇다면 인덱스 항상 많이? ㄴNO!

인덱스를 관리하기 위해서는 DB에 약 10%의 저장공간이 필요하며

인덱스를 관리하기 위해 INSERT, UPDATE, DELETE시 추가 쓰기 작업이 필요하다(자세한 내용은 인덱스 동작 방식에 서술)

 

또한 인덱스를 잘못 사용하면 오히려 성능이 저하되는 역효과가 발생할 수 있으므로

반드시 필요한 곳을 잘 고려해서 사용해야 한다

Random I/O & Sequential I/O

출처: https://haon.blog/haon/index/io/

 

우리는 하드 디스크 드라이브의 플래터(원판)을 돌려 디스크 헤더를 읽어야 할 데이터가 저장된 위치로 이동시킨 후,
디스크 헤더로 부터 데이터를 읽어온다.

이 때 디스크 읽기 방식에는 2가지 방식이 존재한다.

• Random I/O (랜덤 I/O):  페이지(Page), 즉 데이터를 디스크에 쓰기위해 매번 디스크 헤더를 움직임
  -> 읽고 쓸 위치로 이동시키는 시스템 콜을 매번 호출해야함
  - 인덱스 레인지 스캔에 주로 사용
• Sequential I/O (순차 I/O): 데이터 위치가 연속적이기 때문에 디스크 헤더를 한번만 움직이면됨
  - 풀 테이블 스캔에 주로 사용

- 디스크 원판을 가지지 않는 SSD(Solid State Drive) 또한 랜덤 I/O가 순차 I/O보다 성능(처리율)이 떨어진다

 

- 디스크의 성능은 디스크 헤더의 위치 이동 없이 얼마나 많은 데이터를 한번에 기록하느냐에 의해 결정

-> 랜덤 I/O 를 줄여 성능 개선 가능
-> 쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선시켜야함

 

인덱스 동작 방식

테이블에 레코드를 저장하거나 변경하는 경우 인덱스 키 추가나 삭제 작업이 발생한다. 이 때 인덱스가 어떻게 동작하는지 알아보자

 

인덱스 키 추가

새로운 키 값이 저장될 때, 저장될 키 값을 이용해 자료구조 내의 위치를 검색 후 결정하고,

저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 프라이머리 키를 리프 노드에 저장한다.

 

(참고: 만약 리프 노드가 꽉 차면 저장을 못하므로 분리를 시켜야 하는데 이 때 상위 브랜치 노드까지 처리하게 되면서 쓰기 작업(새로운 키 추가하는 작업) 비용이 많이 든다
보통 테이블에 레코드 추가 작업 비용을 1이라 가정하면 해당 테이블의 인덱스에 키를 추가하는 작업 비용은 1.5로 예측한다)

 

인덱스 키 삭제

해당 키 값이 저장된 리프 노드를 찾아 삭제 마크 남기기

🚨 삭제 마킹 작업 또한 디스크 I/O가 필요함 -> 지연 처리 될 가능성 존재

인덱스 키 수정

키 값을 변경하려면 기존 인덱스 키 값을 삭제한 후 새로운 인덱스 키 값을 추가해야 한다.

인덱스 키 값에 따라 리프 노드의 위치가 결정되기 때문에 단순히 인덱스상의 키 값만 변경하는 것이 불가능 하기 때문이다.

따라서 다음과 같은 쓰기 작업이 발생한다.

1. 키 값 삭제
2. 다시 새로운 키 값 추가

인덱스 키 검색

루트 노드 => 브랜치 노드 -> 리프 노드까지 이동하여 데이터를 검색하는 트리 탐색 과정이 일어난다.

자세한 내용은 아래 인덱스 스캔 방식에서 설명하겠다

(혹은 https://kyungyeon.dev/posts/66/ 참고해도 좋을 것 같다!)

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

인덱스를 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하는지에 따라 결정해야 한다

• 카디널리티가 높은 컬럼 ( == 중복도가 낮은 컬럼)
  
  • 데이터 값의 고유성이 높을 수록 성능 향상의 결과를 얻을 수 있음
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
  • 위의 인덱스 동작 방식에서 알 수 있듯이 INSERT, UPDATE, DELETE할 때 적지 않은 쓰기 작업이 발생하기 때문
• WHERE, ORDER BY 절에 자주 사용되는 컬럼
• 읽어야 하는 컬럼의 수가 전체 테이블의 20~25% 이내 일 때
  • 전체 컬럼의 25%이상을 읽어야 할 때는 인덱스를 사용해도 성능상 얻을 수 있는 이점이 없음(=테이블을 모두 직접 읽는게 더 효율적)

 

인덱스 스캔 방식

인덱스 생성 시(MySQL 기준) 선택된 컬럼의 데이터를 기반으로 B+Tree 구조를 만들며,

구조는 상위 계층=루트 노트 -> 중간 계층=브랜치 노드 -> 하위계층=리프 노드 로 이뤄져 있다

이때 리프 노드만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드들은 데이터를 위한 인덱스(Key)만을 지니고 있다

(참고: 노드란 디스크와 메모리(버퍼풀)에 데이터를 읽고 쓰는 최소 작업 단위이며 페이지라고도 한다)

출처: MYSQL 8.0 p231

 

인덱스를 통해 데이터를 찾을 때

인덱스의 접근 방법 가운데 가장 대표적인 접근 방식인 인덱스 레인지 스캔은 아래와 같은 동작이 일어난다

1. 루트 노드(페이지)에서 인덱스 키를 통해 검색할 데이터가 어느 노드(페이지)에 있는지 탐색
2. 해당 키 값이 속한 범위를 찾아 브랜치 노드를 거쳐 원하는 인덱스가 저장된 리프 노드로 이동
3. 리프 노드간의 링크를 통해 최종적으로 스캔을 멈춰야 할 위치까지 도달하면 데이터 반환 및 쿼리 종료

다음으로 인덱스를 사용하지만 인덱스의 처음부터 끝까지 모두 읽는 방식인 인덱스 풀 스캔이 있다

1. 리프 노드의 제일 앞 또는 제일 뒤로 이동
2. 인덱스의 리프 노드를 연결하는 Linked list를 따라 처음부터 끝까지 리프 노드 스캔

이 외에도 필요치 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 루스 인덱스 스캔,

where 조건 칼럼을 스킵해주는 인덱스 스킵 스캔이 존재한다

 

커버링 인덱스

커버링 인덱스는 특정 쿼리의 모든 필요한 데이터를 인덱스에서 직접 얻을 수 있게 하는 인덱스이다

따라서 테이블 자체에 접근할 필요 없이 인덱스에서 쿼리의 모든 필요한 데이터를 찾을 수 있다
=> 디스크의 레코드를 읽지 않아도 되기 때문에 랜덤 읽기가 줄어들고 성능은 향상된다 

 

* EXPLAIN 쿼리 사용했을 때 실행 계획의 extra에 Using index가 나타나면, 이는 커버링 인덱스를 활용한 것으로 해석할 수 있다

 

다중 칼럼(Multi-column) 인덱스

다중 칼럼 인덱스는 2개 이상의 컬럼으로 구성된 인덱스를 말한다

 

특징

• 인덱스의 n+1번째 컬럼은 항상 n번째 컬럼에 의존해서 정렬돼 있음
  • e.g. 2번째 컬럼의 정렬은 1번째 칼럼이 똑같은 레코드에서만 의미가 있음
  • 따라서 다중 컬럼 인덱스 내에서 각 칼럼의 위치(순서)가 상당히 중요함
  • 사진 속 emp_no 값이 "10003"인 레코드가 제일 하단에 위치하는 이유도
    첫번 째 인덱스인 dept_no로 정렬했을 때 "d004"가 정렬 순서가 제일 늦기 때문이다

 

 

 

 

 

 

 

 

B-Tree 인덱스와 B+Tree 인덱스(Balanced Tree)

B-Tree 인덱스와 B+Tree 인덱스는 데이터베이스에서 사용되는 균형 트리 기반의 자료구조이다

두 자료구조 모두 효율적인 데이터 검색을 위해 설계되었지만, 구조적 차이와 사용 목적에서 차이가 존재한다

특징	B-Tree	B+Tree
데이터 저장 위치	모든 노드에 키와 데이터 저장	리프 노드에만 저장
리프 노드 연결	리프 노드가 연결되지 않음	리프 노드가 Linked list 형태로 연결 -> 정렬된 데이터 순차적으로 읽음
범위 검색 효율	비효율적일 수 있음 (모든 노드를 순회해야하기 때문)	범위 검색에 최적화
트리 높이	높음	낮음 (노드에 데이터 없이 키 값만 저장하므로, 한 노드에 더 많은 값을 저장할 수 있기 때문)
디스크 I/O 효율	비효율적	효율적
적용 사례	단일 키 검색	범위 검색(BETWEEN, >, <), 대량 데이터 검색

 

Hash 인덱스

해시 인덱스는 (Key, Value)로 데이터를 저장하는 자료구조 중 하나이며,

key값으로 해시값을 계산해서 인덱스를 생성하므로 매우 빠른 검색을 지원한다.

 

하지만 컬럼의 값을 변형하여 해시값을 인덱싱하므로 값의 일부만 검색하거나 범위를 검색할 때는 사용할 수 없다.

해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하기 때문이다.

=> 메모리 기반의 테이블에 주로 구현되어 있으며 디스크 기반의 대용량 테이블용으로는 거의 사용되지 않는다.

장점

• 실제 키값과는 관계없이 인덱스 크기가 작고 검색이 빠름
• 검색하고자 하는 값을 주면, 해시 함수를 거쳐서 찾고자 하는 키값이 포함된 버킷을 알아내고 버킷안에서 실제 레코드가 저장된 위치를 찾아냄
  => 트리 내에서 여러 노드를 읽어야만 하는 레코드의 주소를 알아 낼 수 있는 B-Tree보다 상당히 빨리 결과를 가져올 수 있음

 

클러스터링 인덱스(클러스터링 테이블)

클러스터링 인덱스는 프라이머리 키(클러스터링 키)를 기준으로 테이블의 레코드들을 묶어서 저장하는 형태를 말한다

클러스터링 인덱스는 프라이머리 키 값에 의해 레코드의 저장 위치가 결정되므로 테이블 레코드의 저장 방식이라고도 볼 수 있다

=> 클러스터링 인덱스 = 클러스터링 테이블 

 

특징

• MySQL의 InnoDB 스토리지 엔진에서만 지원
• 테이블에 프라이머리 키를 설정할 경우, 자동으로 클러스터링이 인덱스가 생성되며 프라이머리 키 값으로 정렬되어 저장된다
  -> 테이블 당 하나의 클러스터링 인덱스만 가질 수 있음
• 리프 노드에 레코드의 모든 칼럼이 같이 저장됨
• 프라이머리 키가 없는 경우 InnoDB 스토리지 엔진이 아래 기준으로 대체 키를 선택한다
  (🚨이때 대체 키는 사용자에게 노출되지 않아 쿼리에 사용하지 못하기 때문에 아무런 이득이 존재하지 않음
        =>가능하면 AUTO_INCREMENT 컬럼을 이용해서라도 프라이머리 키를 생성하자)
  
  1. NOT NULL 옵션의 유니크 인덱스 중 첫 번째 인덱스 선택
  2. 자동으로 유니크한 값을 가지도록 증가되는 칼럼 내부적으로 추가한 후 선택

장점

• 리프 노드에 레코드의 모든 칼럼이 같이 저장되어 있어 검색 시 성능이 매우 빠름
• 테이블의 모든 세컨더리 인덱스가 프라이머리 키를 가지고 있기 때문에,
  테이블 접근 없이 인덱스만으로 처리 가능(커버링 인덱스)

단점

• 클러스터링 키 값의 크기가 클 경우 전체적으로 인덱스 크기가 커짐
  (테이블의 모든 세컨더리 인덱스가 클러스터링 키를 갖고 있기 때문)
• INSERT 할 때 프라이머리 키에 의해 레코드의 저장 위치가 결정되기 때문에 페이지 분할 또는 데이터 재정렬이 발생하여 성능이 느림
• 프라이머리 키를 변경할 때 레코드를 DELETE하고 INSERT하는 작업이 필요하기 때문에 처리 성능이 느림