인덱스와 클러스터 인덱스

인덱스란

정렬된 자료구조로 탐색 범위를 최적화

인덱스도 테이블이다

쿼리가 들어오면 인덱스를 조회한 후 찾은 곳으로 이동

인덱스의 자료구조

HashMap

• 단검 검색 속도 O(N)
• 범위 탐색은 O(N)
• 전방 일치 탐색이 불가능함 -> key를 하나하나 꺼내서 확인해야 하기에

List

• 정렬되지 않은 리스트의 탐색 O(N)
• 정렬된 리스트의 탐색  O(logN)
• 정렬되지 않은 리스트의 정렬 시간 복잡도는  O(N) ~  O(N*logN)
• 삽입/삭제 비용이 매우 높음

Tree

• 트리 높이에 따라 시간 복잡도가 결정
• 트리의 높이 최소화하는 것이 중요함
• 한쪽으로 노드가 치우치지 않도록 균형을 잡아주는 트리 사용

B+ Tree

• 삽입 삭제 시 항상 균형
• 하나의 노드가 여러 개의 자식 노드를 가질 수 있음
• 리프노드에만 데이터가 존재
  • 연속적인 데이터 접근에 유리

클러스터 인덱스

1. 클러스터 인덱스는 데이터 위치를 결정하는 키 값이다.
2. MySQL의 PK는 클러스터 인덱스다.
3. MySQL에서 PK를 제외한 모든 인덱스는 PK를 가지고 있다.

클러스터 키

클러스터 키는 데이터의 위치를 결정한다.

클러스터 키 순서에 따라 데이터 저장 위치가 변경된다.

-> 클러스터 키 삽입, 갱신 시에 성능 이슈가 발생할 수 있다.

MySQL의 PK

 PK를 설정할 때 Auto Increment vs UUID 중 무엇이 나을까?

모든 인덱스는 PK를 가지고 있다.

인덱스는 모두 PK를 가지고 있다 -> PK의 사이즈가 인덱스의 사이즈를 결정한다.

PK를 제외한 모든 인덱스 즉, 세컨더리 인덱스만으로는 데이터를 찾아갈 수 없다. -> PK인덱스를 항상 찾아가야 함

클러스터 인덱스의 장점

• PK를 활용한 검색이 빠르다(특히 범위 검색)
• 세컨더리 인덱스들이 PK를 가지고 있어 커버링에 유리하다.
  • 모든 인덱스들이 PK를 가지고 있기 때문에 요청 처리에 유리