[MySQL] MySQL의 인덱스 탐구하기 1 (feat. B-Tree)

---

개요

 

저번 포스팅, MySQL의 아키텍처와 성능 핵심에서 우리는 디스크 I/O를 줄이는게 중요하다는 걸 알았다. 하지만 디스크 I/O를 줄이기 위한 캐시 사용, 인메모리 적용이 애매한 경우가 분명 존재한다. 이럴때 유용하게 사용할 수 있는 방법이 있는데, 그게 바로 인덱스다. 

 

인덱스는 어플리케이션단 코드를 바꿀 필요도 없고, 새로운 기술 스택을 도입할 필요가 없어 아키텍처에 변화가 생기지도 않는다. 따라서 성능 최적화 작업을 할 때 참 유용해보인다. 하지만 이런 인덱스를 사용한다고 무조건 성능이 좋아지는건 아니라는 사실! 오늘은 인덱스에 좀 더 깊게 공부해보자.

---

인덱스

👀 인덱스가 뭔가요?

간단하게 표현하면, 책의 목차로 비유할 수 있다. 각 데이터의 위치를 설명해주는 친구!

책의 내용이 많아지면, 우리가 원하는 내용을 찾는데 시간이 오래 걸린다. 1000페이지짜리 전공 책에서 특정 내용을 찾으려면 아주 힘든 것 처럼! 이를 해결하기 위해, 우리는 목차를 이용해 각 내용이 어느 페이지에 있는지 위치를 찾을 수 있다.

 

DB도 마찬가지로, 칼럼의 값과 해당 레코드가 저장된 주소를 Key-Value 쌍의 인덱스로 만들어 데이터 조회 성능을 개선할 수 있다.

 

🤩 그럼 모든 컬럼에 인덱스를 추가하면 되겠네요!

고건 아니다! 트레이드 오프를 고려해야 한다.

인덱스는 SortedList와 같은 자료구조를 사용한다. 즉, SortedList와 동일한 장단점을 가진다.

• SortedList (정렬 리스트) : 저장되는 값을 특정 기준으로 정렬하여 유지하는 자료구조.
  • 장점 : 데이터가 이미 정렬되어 있으므로, 원하는 값을 아주 빨리 찾을 수 있다. (O(logN))
  • 단점 : 데이터를 저장할 때마다 새롭게 정렬해야 하므로, 쓰기 과정이 복잡하고 느리다. (O(N))

정리하자면 DBMS의 인덱스는 쓰기 성능 (INSERT, UPDATE, DELETE) 성능을 희생하고 읽기 성능을 높이는 도구다. 따라서 인덱스를 추가할 때는 읽기가 쓰기보다 많은 데이터인지, 데이터 저장 속도를 어디까지 희생할 수 있는지를 고려하고 신중하게 설계해야 한다.

 

🙄 인덱스에는 어떤 자료 구조를 사용하는게 좋을까요?

인덱스는 인덱스가 걸린 필드와 그 필드의 주소로 이루어진 일종의 테이블이다. 따라서 이 테이블 안에서 원하는 데이터를 빠르게 찾기 위해 아래 두 요소를 고려해야 한다.

• 어떻게 탐색 범위를 최소화할 수 있는가?
• 어떻게 탐색 속도를 최적화할 수 있는가?

탐색에 자주 활용되는 자료구조들을 톺아보고, 인덱스에 적절한 것을 찾아보자.

	HashMap	List	Tree
정의	Key-Value 쌍을 저장하고 관리하기 위한 Hash table 기반 자료구조	데이터를 순서대로 저장하고 관리하는 선형 데이터 자료구조	데이터 사이의 계층 구조를 표현하기 위한 비선형 자료구조
장점	고유한 Key 값을 이용, 빠른 검색이 가능하다 (단건 검색 속도 O(1))	정렬된 리스트의 경우, 바이너리 서치를 이용해 빠르게 검색할 수 있다 (O(logN))	데이터 사이의 계층을 표현할 수 있다. 바이너리 서치를 이용할 경우, 트리 높이에 따라 시간 복잡도가 결정되며, O(logN)이 소요된다. 균형 트리의 경우, 데이터의 삽입 및 삭제시 O(logN)이 소요된다.
단점	범위 탐색에 O(N) 소요 전방 일치 탐색 불가 (ex. like ‘AB%’ 의 경우, 모든 키를 전부 꺼내서 비교해야 함)	정렬되지 않은 리스트의 검색은 O(N)이 소요된다. 리스트를 정렬할 때, 정렬 알고리즘에 따라 O(N) ~ O(N*logN)이 소요된다. 삽입 / 삭제 비용이 최악의 경우 O(N)으로 매우 높다.	불균형한 트리의 경우, 검색 및 삽입, 삭제 작업에 최악의 경우 O(N)이 소요된다.

 

탐색 범위를 최소화하고, 새로운 데이터를 추가할 때도 빠르게 정렬하기 위해서는 트리가 제일 적합해보인다. 따라서 MySQL InnoDB 엔진은 인덱스의 자료구조로 Tree 중에서도 다음을 고려한 B-Tree를 사용한다.

1. 트리 높이의 최소화 : 검색 시간 복잡도를 줄이기 위해 높이를 작게 잡는다.
2. 노드의 균형 : 한 쪽으로 노드가 치우치지 않도록, 균형을 잡아주는 트리를 이용해야한다.

 

---

MySQL InnoDB 엔진의 인덱스 자료구조, B-Tree

B-Tree는 Balanced Tree의 약자로, 항상 균형을 유지하는 트리를 의미한다. 일반적으로 DBMS는 B+-Tree 혹은 B*-Tree 알고리즘을 사용하며, 그만큼 B-Tree는 일반적인 용도의 인덱스에 적합한 자료구조이다. 

 

MySQL의 경우, 인덱스를 기능별로 크게 1) 전문 검색용 인덱스와 2) 공간 검색용 인덱스로 나눌 수 있다. 이런 특별한 인덱스에 쓰이는 자료구조, 알고리즘은 따로 있으며, 특수하지 않은 - 즉 일반적인 용도의 인덱스에는 B-Tree 인덱스를 사용한다.

 

B-Tree (Balanced Tree)

• 루트부터 리프까지의 경로 길이가 일정한 균형 트리
  • 트리구조의 최상위에 하나의 루트 노드 (Root node)가 존재하고, 그 하위에 자식 노드가 이어지는 형태.
  • 가장 하위의 노드를 리프 노드 (Leaf node), 루트와 리프 사이의 노드를 브랜치 노드 (Branch node)라고 한다.
  • 한 노드에 자식을 2개 이상 가질 수 있다는 점에서 BST와 차이를 가진다.

 

• 모든 노드에 key와 data를 담을 수 있다.
  • 인덱스의 리프 노트는 항상 실제 데이터 레코드를 찾기 위한 주솟값을 갖는다.
  • 인덱스의 키 값은 모두 정렬되어 있지만, 데이터 파일의 레코드는 정렬되어 있지 않다.

 

위에서 정리했듯, InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 땐 데이터 파일을 바로 찾을 수 없다. 인덱스에 저장된 PK 값을 이용해 PK 인덱스를 검색하고 -> PK 인덱스의 리프 페이지에 저장된 레코드를 읽는 식으로 데이터 파일을 찾아야 한다. 즉, InnoDB 스토리지 엔진에서는 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해 반드시 PK를 저장하고 있는 B-Tree를 검색해야 하는 것! 

 

B-Tree 인덱스에서 고려할 점?

B-Tree 인덱스는 트리 특성에 의해, read와 write 성능이 아래 항목들의 영향을 받는다.

1️⃣ 인덱스 키 값의 크기

InnoDB 스토리지 엔진에서 디스크에 데이터를 저장하는 기본 단위는 페이지로, 이 단위가 읽기 & 쓰기 작업의 최소 단위가 된다. 동시에 페이지는 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위다. 인덱스도 동일하다. InnoDB 엔진에서 인덱스도 마찬가지로 페이지 단위로 관리된다. B-Tree 구조에서 루트, 브랜치, 리프 노드를 구분하는 기준이 바로 페이지 단위다! 

 

MySQL의 B-Tree는 인덱스의 페이지 크기와 키 값의 크기에 따라 최대 자식 노드의 수가 정해진다. 예를 들어보자.

• InnoDB 스토리지 엔진의 페이지 크기 기본값 16KB
• 인덱스 키 크기를 16바이트라고 가정
• 인덱스 페이지에서 자식 노드 주소 영역이 평균 12바이트라고 가정
• 하나의 인덱스 페이지에 저장할 수 있는 키 수 = 16 * 1024 / (16 + 12) = 585개 = 가질 수 있는 최대 자식 노드의 수

따라서, 인덱스 키 값이 커질 수록 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 인덱스 성능이 저하됨을 알 수 있다.

 

2️⃣ B-Tree의 깊이 (높이)

B-Tree의 높이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다. 위에서 정리했듯, 인덱스 키 값의 크기가 커지면 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어진다. 

 

인덱스 키 값의 개수가 적어지면, 같은 레코드 건수라고 해도, B-Tree의 깊이가 깊어진다. 왜? 자식 노드 수가 적어지니까! 따라서 깊이가 깊어진만큼 디스크 읽기가 더 많이 발생하고, 그만큼 인덱스 성능이 저하된다. 

 

따라서 B-Tree 높이를 고려했을 때도 인덱스 키 값의 크기는 가능하게 작게 만드는 것이 좋다.

 

3️⃣ Cardinality

Cardinality (기수성)은 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미하는 단어로, Selectivity (선택도)와 거의 같은 의미를 갖는다.

 

인덱스 키 값 중 중복된 값이 많아지면 유니크한 값의 수가 줄어들기 때문에 카디널리티가 낮아진다. 당연히 인덱스는 유니크한 값이 많을 수록 검색 대상이 줄어들기에 성능이 좋아진다. 따라서 인덱스에서 유니크한 값의 수는 인덱스, 쿼리의 효율에 큰 영향을 미치며, 카디널리티가 높을 수록 인덱스로 설정하기 좋은 컬럼임을 참고하자.

 

(물론 인덱스는 Read 작업 외에도 사용되므로, 여러 용도를 고려해 적절히 설계해야 한다!)

 

4️⃣ 레코드 건수

인덱스를 통해 레코드를 읽는 것은 인덱스 없이 바로 레코드를 읽는 것보다 높은 비용이 드는 작업이다. 예를 들어, 테이블에 100만건의 레코드가 있을 때, 인덱스를 통해 필요한 50만건만 읽는게 효율적일지, 또는 테이블을 전부 읽고 필요 없는 50만건을 지우는게 효율적인 건지를 비교해야 한다.

 

이 판단 과정은 인덱스를 이용한 read 작업의 손익 분기점을 판단하는 것과 동일한 작업이다. DBMS의 옵티마이저는 대부분 인덱스를 통해 레코드 1 건을 읽는 것이 테이블에서 직접 1건의 레코드를 읽는 것보다 4~5배는 비용이 더 많이 든다고 예측한다고 한다. 따라서 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스 없이 직접 테이블을 읽는 필터링 방식이 더 효율적이게 된다.

 

정리하자면, 테이블의 전체 레코드 수의 20~25% 이상을 읽는 경우엔 인덱스로 얻을 수 있는 성능상 이점이 없어, 옵티마이저는 기본적으로 테이블 필터링 방식을 사용한다.

 

---

마무리

 

오늘은 인덱스의 개념, InnoDB 엔진에서 사용되는 인덱스의 자료구조, 그리고 인덱스에서 고려할 점을 찾아봤다. 데이터 구조가 복잡해 질 수록, 도메인 컨텍스트에서 요구하는 것이 분명해질 수록 인덱스를 설계할 때도 공들여야겠다는 생각이 든다 🤔

 

본문에서 언급했듯, MySQL에는 인덱스의 종류가 많다. 전문 검색 인덱스, 공간 검색 인덱스 이외에도 수 많은 인덱스의 종류가 있고, 그 친구들을 잘 알아야 효율적인 쿼리를 짤 수 있다. 다음 포스팅에선 인덱스의 종류를 좀 더 깊게 공부해보자!

 

---

레퍼런스

• Real MySQL 8.0 : https://www.yes24.com/Product/Goods/103415627 

Real MySQL 8.0 (1권) - 예스24

• [MySQL] B-Tree, B+Tree란? : https://zorba91.tistory.com/293

[MySQL] B-tree, B+tree란? (인덱스와 연관지어서)

• What are the differences between B trees and B+ trees? : https://stackoverflow.com/questions/870218/what-are-the-differences-between-b-trees-and-b-trees

What are the differences between B trees and B+ trees?