[MySQL]B-tree를 이용한 Index 동작 알아보기(Feat. 복합 인덱스)

0. 시작하며

https://nooroongzi.tistory.com/1

클러스터링 Index와 논 - 클러스터링 Index

저번 포스팅을 보셨다면 Index를 사용해야 조회 성능이 좋아진다..! 는 장점은 알아보았으니 동작 원리에대해 알아보겠습니다. 또한 MySQL을 기준으로 PJT에 적용했던 복합 인덱싱까지 포스팅을 진행해 보겠습니다

 

1. B-tree

B-tree는 Index의 자료구조 중 하나이고, MySQL은 Index를 내부적으로 B-tree구조로 저장합니다.

1-1. B-tree란?

B-tree는 Balanced Tree의 줄임말으로 균형을 갖는 트리라는 의미를 가지고 있으며 이진트리의 확장 개념입니다.

이진트리는 최대 2개의 자식 노드를 갖지만 B-tree는 N개의 자식 노드를 가지고 있을 수 있습니다. 또한 이진트리는 균형이 맞지 않는 최악의 경우 O(N)의 시간 복잡도를 가질 수 있습니다. 하지만 보통 B-tree는 리밸런싱 작업을진행하며 평균적으로 O(logN)의 시간 복잡도를 보장합니다. 따라서 이진트리보다 대용량의 데이터를 평균적으로 빠르게 찾을 수 있는 구조입니다.

 

1-2 B-tree 구조

B-tree의 구조는 루트 노드, 브랜치 노드, 리프 노드로 구성되어 있습니다.

• 루트 노드는 B-tree의 최상위 노드로, 트리의 시작점을 나타냅니다.
• 브랜치 노드는 각 브랜치 노드는 여러 개의 키(key)를 가지고 있으며, 키 값에 따라 데이터를 가진 자식 노드를 가리킵니다.
• 리프 노드는 실제 데이터가 저장되는 곳입니다.

1-3 Page.

페이지라는 개념이 등장합니다. Page는 데이터를 읽고 쓰는 최소단위로, 디스크 상의 블록을 가리킵니다. B-tree는 대용량의 데이터를 디스크에 저장하고 효율적으로 관리하기 위해 사용되는 구조입니다. 디스크에서 데이터를 읽거나 쓸 때, 일반적으로 페이지 단위로 입출력 작업을 수행합니다.

 

따라서 페이지에 저장되는 데이터의 크기를 최대한 작게 하여, 한 페이지에 많은 데이터를 저장하는것이 중요합니다. 왜냐하면 어떤 data를 찾는데 조회해야할 Page가 많아질 수록 디스크 I/O가 많아지고 이는 비효율에 직접적인 요인이 될 수 있습니다.

 

1-4 인덱스 와 data 저장 구조

먼저 클러스터링 인덱스의 저장 구조를 보시겠습니다.

클러스터링 인덱스를 PK라고 가정했을때 위와 같은 형태로 나타날 수 있습니다. PK와 Page번호를 저장합니다 예를들어 pk가 7인 data를 검색한다면 5 이상 9 미만의 범위 이므로 1001번 Page로 향하고 7번 data를 찾을 수 있습니다.

 

다음은 논 - 클러스터링 인덱스입니다.

이름을 index설정했을경우 독립된 공간에 위와 같은 저장공간이 필요할것입니다. 이름을 기준으로 오름차순 정렬되어 있으며 루트 노드는 똑같이 이름 index의 값과 Page번호가 들어있습니다.

리프 노드에는 실제 데이터가 저장되어있는 Page와 순서가 저장되어있고 이를 기반으로 실제 data를 찾게됩니다.

 

2. 인덱스 실행 계획

MySql에게 쿼리를 날리면 어떻게 쿼리를 실행할지를  옵티마이저가 판단을하고 실행하게됩니다. 이 계획중 3가지를 함께 살펴보겠습니다

1. All
   • 테이블의 모든 데이터를 스캔합니다 (즉, 성능이 안좋습니다.)
   • 인덱스를 활용할 여지가 없거나 활용 하더라도 테이블의 약 30%이상 data 조회시 적용됩니다.
2. Index Rage
   • 인덱스를 이용한 범위 검색입니다.
   • 루트 노드 > 브랜치 노드 > 리프노드 순으로 필요한 페이지의 필요한 data만 조회하게됩니다. (가장 이상적)
3. Index Full
   • 풀 테이블 스캔보다는 나은 방법이지만 Range보다는 성능이 떨어집니다.
   • 첫번째 leaf노드를 수직으로 탐색하고 이후 모든 leaf노드를 순차적으로 탐색합니다.

 

3. Index를 사용하며 주의점

1. 클러스터드 인덱스의 크기

클러스터드 인덱스(PK)는 데이터의 크기가 크면 좋지 않다. 위에서 언급했던 Page에 저장될 수 있는 행이 적어지기때문에 disk I/O의 횟수가 증가할 수 있다.

 

2.중복도(Cardinality)

중복도는 그룹내 요소의 중복되는 요소의개수에 의해 결정된다. 중복이적은 칼럼일수록 Cardinality가 높고, Cardinality가 높은 칼럼에 인덱스를 적용해야 효율이 좋다.

 

3. INSERT, UPDATE, DELETE가 자주 사용되지 않는것이 좋다.

[INSERT]

table에 여러 index설정이 되어 있을수록 write에 대한 오버헤드가 커집니다.

 

[UPDATE]

수정은 내부적으로 Delete 후 Inserte작업을 수행하게됩니다. 따라서 최소 2번의 disk작업을 수행해야하고 인덱스가 있다면 또 적절한 작업이 이루져야합니다. 따라서 PK의 경우 가능한 변경되지 않는것이 좋습니다.

 

[DELETE]

테이블의 레코드 삭제뿐만아니라 인덱스가있다면 해당 값도 삭제되어야합니다.

 

즉 각 수행마다 인덱스 저장공간에서도 필요한 작업이 일어나게되므로 가능한 일어나지 않는것이 성능상 좋다고할 수 있습니다.

 

4. 복합인덱싱

PJT를 진행하며 도메인 특성상 중복도가 높을것으로 예상되는 칼럼을 조회 기준으로 작성했던 쿼리가 있습니다. 해당 쿼리는 대시보드 형식으로서 많은 테이블을 조인해서 보여줘야하는 무거운 쿼리였습니다. 이때 인덱싱 전략을 수정하여 조금 더 효율적으로 쿼리를 수정했습니다.

 

복합인덱스는 해당 칼럼과 다른 칼럼을 묶어 인덱스로 만들 수 있습니다. 예를 들어 전국에 "누룽지"씨는 5만명이라고 할때 23살 "누룽지"씨는 100명인것과 같은 효과입니다.

 

이때 주의할점은 만약 [이름, 나이] 순서로 복합인덱스를 정의 했다면 조회시 해당 순서를 잘 고려해야합니다. 예를들어

1. 조회 조건 = [이름, 나이]

2. 조회 조건 = [이름]

3. 조회 조건 = [나이]

 

위 세가지 경우의 수에서 1,2 번의 경우 지정해둔 인덱스로 조회 성능 향상을 기대할 수 있습니다. 하지만 나이만 가지고 조회를 수행할 경우 해당 인덱스의 효과를 기대하기는 어렵습니다.