[MySQL] Index, B-Tree란 ? ( 인덱스 키 값 계산 )

🐳 1. 인덱스란 ?

인덱스, 영어로는 색인이라는 의미이다.

우리가 책에서 필요한 내용을 찾기 위해 목차를 보는 것처럼

인덱스 또한 데이터베이스에서 우리가 찾는 데이터를 쉽게 찾을 수 있도록 해준다.

 

여기서 중요한 것은 데이터를 쉽게 찾을 수 있도록 해준다는 것이다.

데이터를 삽입, 수정, 삭제를 도와주는 것이 아니다.

 

위에서 설명한 예시처럼 인덱스는 데이터의 읽기 속도를 높이는 기능을 의미한다.

 

그렇다면 인덱스의 단점은 무엇이 있을까 ?

공학도라면 항상 해당 기술의 장단점을 생각해봐야 할 것이다.

 

인덱스는 저장하려는 Column 값을 항상 정렬된 상태로 유지해야 한다.

그렇다는 것은 새로운 데이터를 삽입하는 경우 다시 데이터를 정렬해야 한다는 것이다.

즉 인덱스는 저장 성능을 저하시킨다.

 

결론적으로 인덱스는 저장 성능을 희생해 데이터의 읽기 속도를 높이는 기능이다.

 

# 인덱스가 쓰이지 않는 경우가 궁금하신 분들은 

[데이터베이스] - [MySQL] Index가 사용되지 않는 6가지 경우 ( with 10만 건 예제 데이터를 통한 실습 )

🐳 2. B-Tree 인덱스

인덱스 얘기를 들어 봤다면 B-Tree라는 말도 많이 들어보았을 것이다.

B-Tree는 인덱스를 저장할 때 주로 사용되는 자료구조이다.

그래서 인덱스의 동작을 이해하기 위해서는 B-Tree 자료구조를 이해해야 한다.

 

B-Tree란 Balanced-Tree 의 약자로 ( Binary-Tree 가 아니다 ! ) 균형 잡힌 트리라는 의미이다.

그렇다면 왜 Balanced Tree 일까 ?

 

📝 2.1 B-Tree의 특징

B-Tree 가 Balanced-Tree (균형 잡힌 트리)라는 것을 이해하기 위해서는 여기서 의미하는 균형의 의미를 알아야 한다.

여기서 의미하는 균형은 모든 Leaf 가 같은 Level에 있다는 것을 의미한다.

 

아래의 일반적인 Tree를 살펴보자.

2,10,5,11,4는 Leaf Node이다.

하지만 이들은 Level 3, Level 4에 분포해 있다.

모든 Leaf Node들이 같은 Level에 있는 것은 아니다.

 

위키피디아 Tree 사진

 

 

이번엔 아래의 B-Tree를 살펴보자

B-Tree는 Leaf Node들이 모두 같은 Level 3에 있는 것을 확인할 수 있다.

 

위의 내용을 바탕으로 B-Tree의 특징을 정리하면 아래와 같다.

1. 구성 : 루트노드 / 브랜치노드 / 리프노드 
   • Root: 트리의 최상위 노드입니다.
   • Branch: 중간 노드로, 루트와 리프 사이의 데이터 경로를 제공합니다.
   • Leaf: 가장 하위 레벨에 위치한 노드로, 실제 데이터의 주소를 포함하고 있습니다.
2. 리프노드에 저장되는 주소
   1. MyISAM, MEMORY 같은 스토리지 엔진에는 ROWID (데이터의 물리적 주소)가 저장되어 있어 실제 데이터에 바로 접근할 수 있다.
   2. InnoDB 의 경우 데이터의 Primary Key 값이 (데이터의 논리적 주소) 저장되어 있다. 인덱스를 통해 얻은 PK 값을 이용해 클러스터드 인덱스 테이블에서 실제 데이터를 조회해야 한다. 결국 실제 물리적 주소를 저장할 때보다 인덱스 조회를 한 번 더 해야한다. 인덱스를 한번더 조회함으로 인해 발생하는 성능저하가 있지만 클러스터드 인덱스를 사용함으로 인해 얻는 장점과 성능적 이점이 더 크기 때문에 InnoDB는 리프 노드에 PK 값을 저장한다.
3. 모든 리프는 같은 Level을 가진다.
4. 리프가 꽉 차게 되면 리프 노드를 Split 해야 한다.
   • 이 과정에서 Level 이 1 늘어나게 되고 그에 따라 새로운 브랜치 노드들이 생성된다. 즉 새로운 데이터 추가로 인해 발생하는 리프노드의 생성이 상위 계층에 까지 영향을 주게 된다. 이러한 특성 때문에 옵티마이저는 실제로 데이터를 추가하는 비용보다 인덱스를 추가하는 비용이 평균적으로 1.5~2배 정도의 더 소요될 것으로 추정한다.

 

📝 2.2 B-Tree 노드에 저장되는 정보

❗️중요 : 루트 / 브랜치 / 리프 노드에 이르기까지 모든 노드는 한 개의 데이터를 가지는 것이 아니라 한 개의 Page를 가진다 !!

 

근데 Page가 뭔가요 ... ?

인덱스를 이해하기 위해서는 B-Tree를 알아야 하고 B-Tree를 알기 위해서는 Page를 알아야 한다... ( 참으로 쉽지 않다 인덱스 이놈.. )

 

Page란 ?

• InnoDB 스토리지 엔진이 데이터를 저장하는 기본 단위
• 디스크 Input/Output의 기본 단위
• 4~64KB 사이의 크기를 가짐 ( MySQL 8.0 버전의 기본값 : 16KB 
• Page 내에 여러 데이터들이 존재한다.

즉 B-Tree의 노드에는 한 개의 Page를 저장하고 그 Page 내에는 여러 데이터들을 저장하고 있다.

 

아래의 그림을 보자

 

 

 

 

루트 노드에는 한 개의 Page가 저장되어 있다. 그리고 Page 내에 여러 Record가 저장되어 있다.

해당 Record는 자식 노드 주소 ( 자식 Page 번호 )를 저장한다.

브랜치 노드도 루트 노드와 같은 형식을 사용한다.

리프 노드만 조금 다른 점이 있다.

리프 노드에는 다음 Page 정보가 저장되는 것이 아니라 해당 레코드의 주소가 저장된다.

여기서 스토리지 엔진의 종류에 따라 ROWID(물리적 주소)가 저장되거나 Primary Key 값이 저장된다.

 

 

🐳 3. B-Tree 인덱스의 성능에 영향을 미치는 네 가지 요소

이제 B-Tree 까지도 알아보았으니 인덱스 성능에 영향을 미치는 네 가지 요소에 대해 알아보자.

 

📝 3.1 인덱스 키(Index Key) 값의 크기

여기서 Index Key 값이라는 것은 인덱스를 구성하는 필드의 데이터 타입과 길이에 따라 결정되는 값이다.

예를 들어서 우리가 '이름' Column에 인덱스를 생성하게 되면 '이름' Column의 크기가 인덱스 키 값이 된다.

 

그런데 이 인덱스 키 값이 왜 성능에 영향을 미치는 것일까 ?

왜냐하면 인덱스 키 값의 크기에 따라 한 Page 내에 저장될 수 있는 레코드의 수가 달라지기 때문이다.

 

한 Page 내에 저장되는 데이터 수를 구하는 방법은 아래와 같다.

Page에 저장 가능한 레코드 수 = Page 크기 / (인덱스 크기 + 메모리 주소 크기)  -- 메로리 주소 크기는 6~12B의 값을 가진다.

 

예시와 함께 살펴보자 ! ( 메모리 주소 크기 = 12B 라고 가정하자 )

상황 1. 인덱스 키 값의 크기가 32B인 경우

 

한 Page의 크기는 16KB라고 하자. ( 4~64KB이지만 16KB라고 가정하자 )

Page에 저장 가능한 레코드 수 = 16*1024 / (32 + 12 ) = 약 372

 

상황 2. 인덱스 키 값의 크기가 16B인 경우

 

한 Page의 크기는 16KB라고 하자.

Page에 저장 가능한 레코드 수 = 16*1024 / (16 + 12 ) = 약 585

 

즉 인덱스 키 값의 크기가 32B인 경우에는 한 Page 내에 372개의 데이터가 저장되고

덱스 키 값의 크기가 16B인 경우에는 한 Page 내에 585개의 데이터가 저장된다.

 

이런 상태에서 한 번에 500개의 데이터를 읽어야 한다고 가정해 보자.

상황1 에서는 한 페이지에 372개의 데이터가 저장되기 때문에 500개의 데이터를 읽기 위해서는 2 Page에 걸쳐 데이터를 읽어야 한다.

( Page는 디스크 Input/ Output의 기본 단위이기도 하다 ! )

상황2 에서는 한 페이지에 585개의 데이터가 저장되기 때문에 500개의 데이터를 읽기 위해서는 1 Page의 데이터만 읽으면 된다.

 

결론

인덱스 키 값이 커지면 한 Page에 저장 가능한 데이터의 수가 줄어든다.

이는 같은 양의 데이터를 저장하기 위해서는 인덱스 키 값이 작을 때에 비해서 인덱스 키의 깊이가 더 깊어져야 한다는 것을 의미한다. ( 디스크 I/O 비용이 증가한다. )

한 페이지에 읽을 수 있는 데이터가 줄어들기 때문에 같은 양의 데이터를 읽기 위해서 더 많은 Page를 조회해야 한다. ( 디스크 I/O 비용 증가 )

그렇기 때문에 인덱스 키 값의 크기가 커지면 성능이 저하된다.

 

 

추가 : 인덱스 키 값을 계산하는 방식은 아래와 같다.

1. 필드의 데이터 타입: 각 데이터 타입(예: INT, VARCHAR, DATE)은 저장할 때 정해진 바이트 수를 차지합니다.
   • Int : 4Byte
   • Date : 3Byte
   • Char : 1Byte
2. 가변 길이 필드: VARCHAR와 같은 데이터 타입은 저장된 데이터의 길이에 따라 크기가 변할 수 있습니다. 이 경우, 최대 길이를 기준으로 계산할 수 있습니다. 또한 Charset 도 key_len에 영향을 미칩니다. Charset이 utf8mb3인 경우에 1 글자당 3Byte, utf8mb4의 경우에는 한 글자당 4Byte를 사용합니다.
3. 필드의 수: 인덱스에 여러 필드가 포함된 경우, 모든 필드의 크기를 합산해야 합니다.
4. 메모리 주소 크기: 각 인덱스 항목은 해당 레코드를 가리키는 포인터를 포함하므로, 이 포인터의 크기(보통 6~12바이트)도 고려해야 합니다.

정리 : 인덱스 키 값의 크기 계산 방법:

인덱스 키 값의 크기 = ∑(각 필드의 크기)+메모리 주소 크기

 

예시 1. INT와 DATE를 인덱스 키로 사용할 경우 

• 메모리 주소 크기 = 8Byte로 가정
• INT: 4바이트
• DATE: 3바이트
• 메모리 주소 크기: 8바이트
• 인덱스 키 값의 크기: 4+3+8=154+3+8=15바이트 

예시 2. 복합 키 (VARCHAR(50), DATE)

• 메모리 주소 크기 = 8Byte로 가정
• VARCHAR(50): 최대 50바이트
• DATE: 3바이트
• 메모리 주소 크기: 8바이트
• 총 크기: 50+3+8=61바이트

 

📝 3.2 인덱스 키의 깊이

인덱스 키의 깊이는 직접 제어할 수 없다.

인덱스 키의 깊이는 총 저장할 수 있는 데이터의 양을 의미한다.

가령 1 Page에 372개의 데이터를 저장할 수 있고 Depth = 3 이면

총 저장할 수 있는 데이터의 양은 = 372*372*372 = 약 5천만

 

1 Page에 585개의 데이터를 저장할 수 있고 Depth = 3 이면

총 저장할 수 있는 데이터의 양은 = 585*585*585 = 약 2억

 

인덱스 키 값의 크기가 커서 한 Page 내에 저장할 수 있는 데이터가 적다면

인덱스 키 값이 작아 한 Page 내에 저장할 수 있는 데이터가 클 때보다

같은 양의 데이터를 저장하기 위해서 깊이가 더 깊어져야 한다.

 

깊이가 깊어지면 탐색시간이 더 길어지게 되고 이는 성능의 저하를 의미하게 된다.

 

 

📝 3.3 선택도 / 기수성

인덱스의 성능에 영향을 주는 세 번째 요인인 선택도와 기수성이다.

둘은 거의 비슷한 의미를 가진다.

• 모든 인덱스 가운데 유니크한 값의 수를 의미
• ex) 총 데이터 1000개, 유니크한 값은 10개 -> 기수성/선택도 = 10
• 중복된 데이터가 많아질수록 선택도/기수성 낮아짐

그렇다면 선택도와 기수성이 인덱스의 성능에 왜 영향을 줄까 ?

선택도가 높을수록 검색 대상이 줄어들기 때문이다 !

이는 읽어야 하는 레코드의 수가 줄어든 다는 것이고 이는 성능이 향상됨을 의미한다.

 

📝 3.4 읽어야 하는 레코드의 수

 

인덱스의 성능에 영향을 미치는 네 번째 요소는

읽어야하는 레코드의 수이다.

 

예를 들어 <학생> 테이블에 1000개의 데이터가 있다고 하자.

 

나는 그중 250 건의 데이터를 읽어와야 한다.

 

이때 옵티마이저는 어떤 인덱스를 사용해서 테이블을 읽을까 ??

 

정답은 인덱스를 사용하지 않는 것이다.

 

왜일까 ?

옵티마이저는 인덱스를 통해 데이터를 읽는 것을 직접 레코드 1건 읽는 것보다 4~5배 비용이 드는 것으로 추정한다.

그러므로 조회하는 데이터가 전체 데이터의 20~25% 이상이라면 인덱스를 사용하지 않는 것이 더 빠를 수 있음
전체 테이블 스캔 후 필터링 하는 것이 효율적일 수 있다.

 

 

위에서 설명한 네 가지 요소가 인덱스의 성능에 영향을 주는 요소이다.

1. 인덱스 키 값의 크기
2. 인덱스 키의 깊이
3. 선택도 / 기수성
4. 읽어야 하는 레코드의 수

 

 

🐳 참고

• Real MySQL 8.0