[데이터베이스] 인덱스(index) 정리

인덱스

 

 
 
목차, 색인, 책갈피와 같은 기능을 하는 인덱스는, 데이터베이스 분야에서는 어떤 데이터를 검색할 때 속도를 높여주는 자료 구조로
메모리 영역에 생성되는 일종의 책갈피이다.
 
 
 
 

인덱스 구조

보통 Hash, B-Tree, B+Tree가 있다.

실제 사용하고있는 MySQL MYISAM의 인덱스 일부

 

Hash

우리가 알고있는 Key, Value형태의 자료 구조다.
해시 함수로 키 값을 해시값으로 변환하고, 이 해시 값을 기반으로 데이터를 빠르게 조회할 수 있다. - O(1)
 

 
 
하지만 이런 해시구조의 특성상 범위 검색에 효율이 떨어진다. 키 값이 조금이라도 변하게 되면 완전히 다른 해시 값을 반환하기 때문이다.
범위 검색에서의 부등호 연산을 포함한 범위 조건(BETWEEN, LIKE 등)에는 적합하지 않다.
 
 
 

B-Tree

B-Tree는 이진 트리를 확장한 트리 구조이다. 자식 노드를 2개보다 더 많이 가질 수 있다.
 

 
 
Root, Branch, Leaf의 구조로 되어있으며 Branch가 곧 리프가 되는 경우도 있다.
B-Tree의 주요 특징 중 하나는 모든 리프 노드가 동일한 깊이에 있다는 점이다.
이는 트리의 균형을 유지하여 연산 시간의 복잡도 logN으로 보장하여 효율적인 검색을 가능하게 한다.
 
B-Tree의 구조가 효율적인 이유는 위에서 언급한 균형 잡힌 구조와 더불어 대수 확장성에 있다.
대수 확장성이란 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것을 의미한다.
4차 B-Tree구조가 있다고 가정해보자. 각 노드는 최대 4개의 자식노드를 가질 수 있다. 즉 트리의 깊이가 1씩 증가할 때마다 최대 4배의 인덱스가 추가될 수 있다. 따라서 깊이가 d인 4차 B-Tree는 최대 4^d의 리프 노드를 가질 수 있다. 깊이가 10만 되어도 리프 노드수는 100만 개가 넘는다.

트리의 깊이가 낮기 때문에 I/O작업이 적고 연산이 빠르게 일어날 수 있다.

 
 
 

B+Tree

B-Tree를 개선시킨 자료 구조로 각 노드에는 인덱스 키만 저장되고, 실제 데이터는 리프 노드에 저장된다.
 

 
 
리프 노드들은 서로 연결 리스트 형태로 연결되어 있어 범위 검색에 효율적이다. 하지만 데이터를 조회하기 위해선 반드시 리프 노드까지 탐색(log2N)이 되어야 한다.
 
 
 
 

주의사항

 

DML의 성능 저하

DML(insert, update, delete) 명령에 따라 레코드에 해당하는 인덱스를 생성, 삭제, 변경해야 하기 때문에 성능 저하가 발생한다.
또한 인덱스의 개수가 너무 많으면 레코드 당 인덱스 변경의 횟수가 많아지기 때문에 성능 저하를 발생시킬 수 있다.
인덱스의 개수가 많아지면 옵티마이저가 잘못된 인덱스를 선택하여 조회 성능에 영향을 미치지 못하는 경우도 있다.
 
 

페이지 크기와 레코드 저장

MySQL에서는 디스크와 메모리에 데이터를 읽고 쓰는 최소 작업의 단위를 페이지라 한다.

인덱스를 포함해 PK와 테이블 모두 페이지 단위로 관리된다.

 
우리는 하나의 레코드를 읽기 위해서 여러 레코드가 포함된 페이지를 읽어서 그 중 일치하는 레코드를 읽는 것이다.
(당연히 페이지에는 여러 레코드가 기록되어 있을 수 있다.)
만약 레코드를 찾기 위해 1개의 페이지로 해결이 되지 않는다면 다른 페이지들을 읽어야 하는 추가적인 디스크 I/O가 발생하게 된다. 
 
(참고)
InnoDB의 경우 페이지 크기는 16KB로 고정되어 있었지만, 공식 문서에 따르면 MySQL 5.7.6 이후부터는 페이지 크기를 32KB, 64KB로 설정하는 것이 가능하다고 한다. 하지만 한 레코드의 크기는 16KB로 여전히 제한된다고 한다.
 

 
 
인덱스 역시 페이지 단위로 관리가 된다. 인덱스로 사용되는 PK, 컬럼의 크기가 크면 클수록 인덱스 페이지가 줄어들게 된다. 그럼 인덱스를 활용한 조회 시에도 여러 인덱스 페이지를 읽어야 하는 문제가 발생한다. 그렇기에 인덱스 키는 길면 길수록 성능 저하를 발생시킨다.
 

InnoDB의 경우 하나의 레코드 크기가 페이지 크기의 절반 이상일 경우 레코드에서 외부에 저장할 가변 길이 컬럼을 선택해서 외부 페이지(off-page)에 데이터를 저장하고 기존의 페이지에는 off-page를 가리키는 포인터를 저장한다.

 
 
 
 

인덱스 컬럼 기준

 

단일 인덱스

단일 인덱스를 생성할 때는 카디널리티(Cardinality)가 가장 높은 것을 잡아야 한다.

카디널리티란 중복된 수치를 얘기한다. Unique 한 값일수록 카디널리티가 높다.
예를 들어 성별은 카디널리티가 낮고, 주민등록번호는 카디널리티가 높다.

 
카디널리티가 높은 컬럼을 인덱스로 생성해야 하는 이유는 인덱스로 많은 부분을 걸러낼 수 있어야 하기 때문이다. 인덱스를 통해 많이 걸러내면 걸러낼수록 조회 성능이 올라간다.
 
 

복합 인덱스

복합 인덱스를 최적화하기 위해서는 카디널리티를 포함하여 다음 상황들을 고려해야 한다.

• 공통으로 사용되는 필수 조건
• =, IN 연산
• 정렬
• 범위 비교 연산 (BETWEEN, LIKE, 비교연산자)

여러 자료를 통해 학습을 했을 때, 인덱스는 범위 비교 시에는 다음 인덱스 컬럼은 사용되지 않는다고 했다.
인덱스를 지정할 때 위의 상황들을 오름차순으로 생성하는 게 효율적이라는 자료도 있었다.
 
 
 

복합 인덱스를 통한 현업에서의 튜닝 시도

최대 5초가 걸리는 쿼리 개선하기

 

 

 

종류

인덱스는 분류에 따라 여러 종류의 인덱스가 있다.

• Unique - Non-Unique Index
• Single - Composite Index
• Clustered - Non-Clustered Index
• Function-Based, Bitmap, Reverse key, Hash Index

등등 여러 인덱스들이 있지만 여기서는 클러스터의 분류에 따른 인덱스를 살펴보자
 
 

Clustered Index

클러스터드 인덱스는 데이터가 테이블에 물리적으로 저장되는 순서를 정의한다. 이 뜻은 인덱스가 되는 컬럼을 기준으로 데이터들을 정렬시킴을 의미한다.

primary key의 제약 조건은 클러스터드 인덱스를 자동 생성하기 때문에 일반적인 상황에서는 PK가 곧 클러스터드 인덱스가 된다.
 
테이블당 하나의 클러스터드 인덱스만 존재할 수 있고 인덱스 페이지의 리프 노드에 실제 데이터의 페이지가 들어있다.
 

출처: https://gwang920.github.io/database/clusterednonclustered/

 
 
 
실제 데이터가 인덱스 순서에 따라 정렬되어 검색 시 매우 빠른 성능을 보일 수 있다. 하지만 위에서 말한 것처럼 정렬된 상태여야 한다. no, id값의 일반적인 auto_increment값을 가진 PK라면 문제가 되지 않겠으나, UUID 같은 정렬되지 않은 키를 사용한다면 정렬을 위해 추가적인 리소스를 발생시킬 수 있다. 성능이 저하될 수 있다는 의미이다.

 

PK의 보안 때문에 UUID를 고려한다면 UUIDv7을 사용해 보는 것도 괜찮을 것 같다.
UUIDv7은 UNIX_TIMESTAMP를 ms 단위로 인코딩하여 효율적인 색인화가 가능하다고 한다.

 
 
 
 

Non-Clustered Index

논-클러스터드 인덱스는 테이블에 저장된 물리적 순서에 따라 데이터를 정렬하지는 않는다.
 
클러스터드 인덱스와 달리 리프 노드에는 데이터 페이지에 대한 포인터가 있어 포인터를 통해 데이터 페이지를 조회할 수 있는 형태이고 데이터 페이지는 정렬되어있지 않다.
 

출처: https://gwang920.github.io/database/clusterednonclustered/

 
 
클러스터드 인덱스와 달리 데이터를 찾는 데 여러 개의 인덱스를 생성할 수 있다.
 
데이터를 찾을 때 추가적인 스텝 (리프 레벨에서 데이터 페이지에 접근)이 필요하기 때문에, 클러스터드 인덱스보다는 속도가 느리고 데이터 입력 시 별도의 공간에 인덱스를 생성해야 하기 때문에 추가 작업이 요구된다. 별도의 공간도 따로 할당되어야 한다. (약 10%)
 
 
 
 

마무리

블로그를 돌아보니 DB 포스팅이 SQLD를 취득하기 위한 학습 이후에 멈춰있었는데, 사실상 현재 해나가고 있는 모든 것들을 포스팅하는 내 성격상 현재 가장 많이 다루고 있는 것이 데이터베이스인데, 네트워크와 PS에 빠져서 소홀했다는 생각이 들었다. 
 
리팩토링 과정에서 단순히 실행 계획을 바탕으로 튜닝을 이것저것 많이 처리하고, 일의 양이 많아 바로 다음 작업으로 넘어가다 보니 정확히 쿼리 튜닝을 위해 관련된 지식들을 학습할 필요를 느껴 다시 하나하나 시작해보려 한다. DB의 여러 부분들의 공부를 깊게 해 보면서 실제로 적용시켜 보며 정리를 위한 포스팅을 계속 이어나갈 수 있도록 해야겠다.
 
 
 
 

참조

Real MySQL 시즌 1 - Part 1 강의 | 이성욱 - 인프런

CS 지식의 정석 | 디자인패턴 네트워크 운영체제 데이터베이스 자료구조 강의 | 큰돌 - 인프런

[Database] 인덱스(index)란?

MySQL Ascending index vs Descending index - tech.kakao.com

MySQL :: MySQL 5.7 Release Notes :: Changes in MySQL 5.7.6 (2015-03-09, Milestone 16)

[mysql] 인덱스 정리 및 팁

2. 페이징 성능 개선하기 - 커버링 인덱스 사용하기

[MySQL] B-Tree로 인덱스(Index)에 대해 쉽고 완벽하게 이해하기

 

Goodbye to sequential integers,  hello UUIDv7!