[DB] 인덱스 B-Tree 살펴보기!

들어가며

인덱스는 어떤 자료구조로 이루어져 있나요? 라는 질문을 들으면, B-Tree 자료 구조로 이루어져 있습니다! 라고 대답할 수는 있지만, B-Tree 가 무엇이냐는 대답할 수 없을 것 같습니다... 하지만 Real MySQL 8.0 책을 읽으면서 B-Tree 가 어떤 형태로 정렬이 되어 있고, 어떤 특징이 있는지 조금은 알게 되었습니다. 따라서 이번 기회에 글을 정리하며 제대로 이해하고자 글을 작성하게 되었습니다.

 

B-Tree 란?

다수의 자식을 가질 수 있는 정렬된 균형 탐색 트리로, 데이터 삽입/삭제 시에도 트리의 균형을 유지하며 높이를 최소화하여 검색 성능을 유지하는 자료구조.

 

 

GPT가 정리해준 B-Tree의 정의입니다. 여기서 B는 Binary가 아닌 Balance를 의미합니다. 그렇다면 왜 균형을 맞출까? 라는 의문이 들 수 있습니다. 이는 정의에 적힌 것처럼 트리의 균형을 유지하여 높이를 최소화하여 검색 성능을 유지하고자 함입니다!

 

 

예시

예시를 들기 전에 하나의 가정을 하겠습니다.1. Database 에서 캐싱 기능이 존재하지 않는다.2. 인덱스는 B-Tree 형태로 저장되어 있습니다.3. 트리의 한 높이에 접근할 때마다 디스크에 접근해야 한다.

 

 

둘 다 제가 임의로 만든 각각 B+Tree 와 Binary-Tree 입니다.

위의 가정에 따르면 제가 10이라는 인덱스 키 값에 접근하게 되면 B+Tree 는 2번의 디스크 I/O만 접근하면 되지만, 이진 트리는 3번의 디스크 I/O가 필요합니다.

 

디스크의 읽는 속도가 현저히 떨어지기 때문에 트리의 높이를 최소화함으로써, 읽기 작업을 최소화 할 수 있는 것입니다!

 

인덱스 자료형의 크기에 따른 높이 변화.

비교를 위해 Int (4Byte) 와  100Byte 크기를 가진 자료형이 있다고 가정하고 이 둘을 비교해보자!

실제로는 위의 그림과 달리 인덱스의 노드들은 페이지 형식으로 저장되어 있습니다! 그리고, DBMS는 페이지 단위로 디스크에서 데이터를 읽어옵니다.

 

즉, 디스크에 한번에 읽을 때 최대한 많은 데이터를 가져올 수 있다면 (페이지에 많은 값들을 담을 수 있다면) 트리의 높이가 줄어들 것입니다!

 

다시 가정을 하겠습니다!

1) 하나의 페이지 크기는 4KB.

2) 데이터 포인터는 8 Byte.

 

그렇다면 하나에 4Byte 의 인덱스는 총 12Byte 이고, 4KB (4096 Byte) 페이지에는 약 341 (4096 / 12)개의 인덱스 값들을 담을 수 있습니다! 마찬가지로, 100Byte 인덱스의 경우에는 약 38 (4096 / 108)개의 인덱스 값들을 담을 수 있습니다.

 

이를 그림으로 이해하기 쉽게 표현하면 다음과 같습니다.

 

B+Tree 기준 리프노드의 개수가 굉장히 많이 차이가 납니다 3개 vs 27개. 단순히 트리를 구성해도 인덱스의 자료형의 크기가 크다면, 같은 범위의 값을 표현하더라도 트리의 깊이가 커지게 되어 효율이 떨어짐을 알 수 있습니다!