데이터베이스 인덱스에 대해서 설명해주세요.

데이터베이스 인덱스는 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 특정 컬럼에 대한 값과 해당 레코드의 위치를 매핑하여 빠른 데이터 접근을 가능하게 한다. 인덱스는 추가적인 저장 공간을 사용하지만, 대량의 데이터에서 검색 성능을 크게 개선한다. 인덱스는 ORDER BY, GROUP BY, WHERE 절의 효율적인 처리를 돕는다. 하지만 INSERT, UPDATE, DELETE 작업시 인덱스 갱신으로 인한 성능 저하가 발생할 수 있다.

 

1. 인덱스의 자료구조

인덱스는 주로 해시 테이블과 B+Tree가 사용된다. 해시 테이블은 O(1)의 시간 복잡도로 빠른 검색이 가능하지만, 범위 검색에는 적합하지 않는다. B+Tree는 균형 잡힌 트리 구조로, O(log N)의 시간 복잡도를 가지며 범위 검색에 효율적이다. B+Tree는 리프 노드에만 데이터를 저장하고, 리프 노드들이 연결 리스트로 연결되어 있어 순차적 접근이 용이하다. 이러한 특성으로 인해 B+Tree가 데이터베이스 인덱스에 널리 사용된다.

2. MySQL InnoDB의 인덱스 자료 구조

MySQL InnoDB의 인덱스 자료구조는 주로 B-Tree(Balanced Tree)를 사용한다. B-Tree는 데이터베이스 시스템에서 널리 사용되는 균형 잡힌 트리 구조이다.

 

2 - 1. B-Tree 인덱스의 주요 특징

• 루트 노드, 브랜치 노드, 리프 노드로 구성된다.
• 인덱스 키는 항상 정렬된 상태를 유지한다.
• 인덱스는 페이지라는 단위로 저장된다.
• O(log N)의 시간 복잡도로 빠른 검색이 가능하다.
• 정렬된 구조로 인해 범위 검색에 효과적이다.

 

2 - 2. InnoDB에서 두 가지 주요 인덱스 유형

 

2 - 2 - 1. 클러스터링 인덱스

주로 PK에 대해 생성되며, 실제 데이터가 인덱스의 리프 노드에 저장된다.

 

2 - 2 - 2. 세컨더리 인덱스

PK가 아닌 컬럼에 대해 생성되며, 리프 노드에는 인덱스 키와 해당 레코드의 PK 값이 저장된다.

 

3. MySQL에서의 스캔 방식

MySQL에서는 주로 두 가지 스캔 방식이 사용된다. 

옵티마이저는 쿼리의 조건과 테이블 상태를 고려하여 가장 효율적인 스캔 방식을 선택한다.

 

3 - 1. Full Table Scan

Full Table Scan 방식은 테이블의 모든 레코드를 처음부터 끝까지 읽는 방식으로,

인덱스가 없거나 인덱스 스캔 방식이 효율적이지 않을 때 사용된다.

 

 

3 - 2. Index Scan

Index Scan 방식은 인덱스를 이용하여 필요한 데이터만 빠르게 접근하는 방식이다. 인덱스 스캔은 WHERE 조건이나 ORDER BY에 인덱스 컬럼이 사용될 때 효과적이다. Index Scan은 또 3가지로 나뉜다.

 

3 - 2 - 1. Index Range Scan

검색할 인덱스 범위가 결정되었을 경우 사용하며 가장 빠르다.

 

• index seek: 인덱스에서 조건을 만족하는 값이 저장된 시작 리프 노드를 찾는다.
• index scan: 시작 리프 노드부터 필요한 만큼 인덱스를 차례대로 읽는다.
• 인덱스 키와 레코드 주소를 이용해 저장된 페이지를 가져오고 레코드를 읽어온다.

 

 3 - 2 - 2. Index Full Scan

인덱스를 사용하지만 인덱스를 처음부터 끝까지 모두 읽는 방식이다.

주로, 쿼리의 WHERE 절에 인덱스의 선두 컬럼이 포함되지 않는 경우 사용된다.

예를 들어, 인덱스를 ABC 순서대로 만들었는데, WHERE 절이 B 혹은 C로 검색되는 경우이다.

Full Table Scan 보다 효율적일 때 옵티마이저가 선택한다.

 

3 - 2 - 3. Loose Index Scan

인덱스를 효율적으로 활용하는 고급 최적화 기법이다.

 

• 선택적 읽기: 인덱스 전체를 읽지 않고 필요한 부분만 읽는다.
• 그룹별 첫 레코드: 각 그룹의 첫 번째 레코드만 읽고 다음 그룹으로 이동한다.
• 효율성: 전체 인덱스 스캔보다 훨씬 적은 수의 레코드만 읽어 처리한다. 

주로, GROUP BY절에 사용되고, WHERE 절이 있는 경우, 조건을 만족하는 각 그룹의 첫 번째 키만 찾아 처리한다. 

 

References

https://www.maeil-mail.kr/question/60

https://mangkyu.tistory.com/96

https://mangkyu.tistory.com/285

https://mangkyu.tistory.com/286

https://www.youtube.com/watch?feature=shared&v=NkZ6r6z2pBg

https://www.youtube.com/watch?v=_UI8YDU_mfg