조회 성능 최적화를 위한 인덱스 (1)

인덱스를 이용한 조회 성능 최적화 테스트를 작성하다가 인덱스에 대한 개념 또한 만만치 않은 것 같아

먼저 정리한 후 이어서 작성하려고 (1)과 (2)로 분리하게 되었습니다.

 

---

인덱스

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

 

예시를 들어 보자.

A

B

C

E

F

G

H

위의 알파벳이 정렬되어 있는 표에서 D가 빠진 것을 찾는 것은 쉽다

데이터가 많더라도 정렬되어 있으면 사람이 찾기에 편할 것이다(범위 탐색이 용이)

 

A

C

B

F

G

H

E

정렬되지 않은 테이블에서 D가 빠진 것을 찾으려면 전체 테이블을 확인해봐야 하며 데이터가 많다면 사람이 찾기에도 정말 힘들 것이다

 

위의 예시를 보면 무조건 비용을 지불하여 인덱스를 사용하고 싶을 것 같다. (나는 그랬다..)

 

더 일반적인 예시로 보자

 

 

	이름	성별	나이	직업
1	홍길동	남	32	경찰
2	김유리	여	27	요리사
3	이순신	남	19	어부
4	김철수	남	45	강사

위의 테이블에서 나이가 가장 적은 사람을 찾으려면 모든 레코드의 나이 컬럼을 비교해봐야 한다

 

하지만 나이를 정렬한 값으로 가지고 있다면?

 

나이	데이터 주소
19	3
27	2
32	1
45	4

바로 맨위의 값으로 찾아낼 수 있게 된다.

 

https://coding-factory.tistory.com/746

정리하면, 우리가 자주 검색에 사용되는 컬럼을 인덱스로 설정하게 되면, 테이블에 대한 검색 성능의 속도를 높여주는 자료구조로 활용할 수 있다는 것이다

---

인덱스 관리

 

위에서 살펴본 것과 같이 정렬된 값을 이용하면 탐색에 용이하게 적용될 수 있다

따라서 인덱스를 항상 최신의 정렬 상태로 유지해야 한다 이에 따라 Insert, Update, Delete 쿼리가 수행된다면 어떤 비용이 드는지 알아둬야 인덱스를 설정할 때 다양한 방면에서 고려해 볼 수 있다

• Insert: 새로운 데이터에 대한 인덱스를 추가
• Update: 기존의 인덱스를 사용하지 않음 처리(Garbage) 갱신된 데이터에 대한 인덱스 추가
• Delete: 삭제하는 데이터의 인덱스를 사용하지 않음 처리

Delete, Update가 자주 발생하면 사용하지 않는 인덱스가 많아지고 이는 성능 저하를 야기한다

이렇게 쌓이는 Garbage인덱스를 처리하는 방법도 고려해둬야할 것이다

 

인덱스 사용이 적합한 경우

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

---

인덱스의 자료구조

인덱스를 저장하고 관리하기 위해선 효과적인 자료구조를 사용해야 한다. 왜냐하면 항상 정렬시켜서 저장해야 하며, 범위 탐색을 해야 하니까.. 다양한 자료구조를 비교해 보자!

 

HashMap

• 단건 검색 속도 O(1) -> `=`연산에만 용이
• 범위 탐색은 O(N)
• 전방 일치 탐색 불가 -> `like`구문

List

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

Tree

• 트리 높이에 따라 시간 복잡도가 결정됨
• 트리의 높이를 최소화하는 것이 성능에 매우 중요
• 한쪽으로 노드가 치우치지 않도록 균형을 잡아주는 트리 -> Red-Black Tree, B Tree, B+ Tree

B-Tree

• 각 노드에는 Key-Value 쌍 데이터가 저장되며, 1개의 노드에는 여러 Key를 저장할 수 있음 -> BST, Red-Black Tree와의 차이점
• 탐색 성능을 높이기 위해 깊이를 유지하는 Balanced Tree의 일종
• 브랜치 노드에도 데이터가 있어 리프 노드까지 내려가지 않고 데이터를 찾을 수 있음

B+ Tree

• 삽입, 삭제 시 항상 균형을 이룸 -> merge 비용이 존재
• 하나의 노드가 여러 개의 자식 노드를 가질 수 있음 -> 트리 높이를 감소
• 리프노드에만 데이터 존재 -> B-Tree와의 차이점, 선형 탐색이 가능!
  • 리프노드들은 LinkedList로 연결
  • 연속적인 데이터 접근 시 유리

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

B+ Tree Visualization

위의 사이트에서 직접 데이터를 넣어보며 B+Tree를 이해해 보자

범위를 탐색할 때 B+Tree를 이용하게 되면 특정 범위가 있는 리프노드에 빠르게 접근하여 연속된 데이터에 접근할 수 있도록 구현되어 있다 하지만 단점이라면 무조건 리프노드에 가야 한다는 것 (제일 Best 상황은 리프까지 안 가고 접근하는 것이 더 좋겠지?)

 

MySQL의 InnoDB는 B+Tree 자료구조를 사용하고 있음

https://velog.io/@evelyn82ny/B-Tree-index-feat-difference-from-B-plus-Tree#:~:text=%EC%9D%BC%EB%B0%98%EC%A0%81%EC%9D%B8%20Binary%20Tree%EB%8A%94%202,%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%A5%BC%20%EA%B0%80%EC%A7%88%20%EC%88%98%20%EC%9E%88%EB%8B%A4.

B-Tree라고 나와있는데, B+Tree가 맞는 거 아닌가?..

 

---

클러스터 인덱스와 세컨더리 인덱스

 

MySQL의 InnoDB는 테이블의 레코드 주소로 PK를 사용하며 PK 값으로 정렬된 테이블을 클러스터링 테이블이라고도 한다

만약 PK를 변경했다면 테이블 내에서 위치가 변경될 수 있으며 이는 레코드 주소가 변경되었음을 의미

 

따라서 특정 컬럼을 PK로 지정한다는 것은 해당 컬럼에 클러스터 인덱스가 생성되며 이 인덱스가 곧 레코드의 주소를 의미한다

• 클러스터 인덱스(Clustered Index)
  • InnoDB 엔진에서 table의 Primary Key를 정의하면 Clustered Index가 됨
  • 테이블당 하나만 가질 수 있음
  • Insert시 data가 정렬되고 index는 data block의 첫 번째 레코드의 주소값을 갖게 되며 index가 곧바로 data block에 접근해 Secondary Index보다 동작이 빠른 편

세컨더리 인덱스는 우리가 원하는 데이터를 얻기 위해 검색에 사용하는 컬럼에 대한 인덱스를 추가하는 것

마찬가지로, 테이블엔 인덱스가 정렬되어 있고, 주소 값으론 PK 값을 담고 있음

• 세컨더리 인덱스(Secondary Index or Non-Clustered Index)
  • 한 테이블에 여러 개의 세컨더리 인덱스를 가질 수 있음
  • 탐색 과정에서 원하는 데이터를 접근하기 위해선 세컨더리 인덱스를 통해 알아낸 PK로 한 번 더 페이지에 접근
    • 얻어낸 PK를 가지고 데이터가 저장되어 있는 페이지를 읽어야 함  
    • 더 많은 I/O 작업이 발생

클러스터 인덱스와 세컨더리 인덱스는 복합적으로도 사용될 수 있고, 클러스터 인덱스로 탐색하기 어려울 경우 세컨더리 인덱스로 탐색하는 방법으로도 사용된다. 이는 여러 방면으로 QA를 진행해서 상황에 따라 알맞게 적용하는 것이 좋다

 

항상 데이터가 많아지면 어떻게 변하게 될지, 데이터의 크기가 커서 많은 페이지에 접근하게 되는 문제는 없을지, 꼭 인덱스를 사용해야 하는지 여러 트레이드 오프를 따져가면서 결정할 수 있도록 하자

---

참고

https://steady-coding.tistory.com/565

[데이터베이스] 클러스터링 인덱스, 유니크 인덱스, 외래 키

https://velog.io/@evelyn82ny/B-Tree-index-feat-difference-from-B-plus-Tree#:~:text=%EC%9D%BC%EB%B0%98%EC%A0%81%EC%9D%B8%20Binary%20Tree%EB%8A%94%202,%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%A5%BC%20%EA%B0%80%EC%A7%88%20%EC%88%98%20%EC%9E%88%EB%8B%A4.

[MySQL 8.0] B-Tree Index (feat. B+Tree와의 차이)

https://sihyung92.oopy.io/database/mysql-index