B+ tree란? - 기술 면접 준비

 
 
 

💡 B+ tree란?

자, B+ tree (Balanced+ tree)가 무엇인지 알아봅시다. 계속 언급되는 것을 아래 처럼 정리해봤습니다.

• 정렬된 구조
• 균형 잡힌 구조
• 하나의 페이지에 많은 키를 담아서, 트리의 높이가 낮은 구조
• 높은 fan-out으로 디스크 I/O 최소화
• 리프 노드가 연결 리스트라 범위 탐색 유리

 
많은 사람들이 인덱스의 구조 하면 아래와 같은 그림을 떠올립니다.

 
너무 명쾌한 그림이지만, B+ tree와는 점점 거리가 멀어지게 만드는 그림입니다.
저도, 처음에 이렇게 배워서 인덱스가 뭐 한 줄의 정렬된 목차 형태로 있는 줄 알았죠... 🤣
 
 

B+ tree 구조인 인덱스의 간략한 형태입니다.
최상단 노드가 Root node, 최하단 노드가 Leaf node 혹은 Data node.
그 사이는 몇 depth이건 상관 없이 Internal node 혹은 Branch node라고도 하고, Intermediate node라고도 합니다.
 
 

Root node, Internal node는 형태가 동일합니다. Leaf node와는 형태가 다르죠?
record pointer라고 하는 자식의 위치를 가리키는 포인터가 있습니다.
그리고, 분기 기준이 되는 key 값이 있습니다. 이 key 값은 분기를 위한 기준이 될 뿐, 해당 데이터가 있다는 걸 보장하지 않습니다.
그래서, 4라는 데이터를 탐색할 때, Root node에 4가 있네? 하고 I/O 한 번에 끝나지 않는다는 것입니다.
B+ tree의 특징으로, Leaf node에만 데이터가 있기 때문에, Leaf node에서 4를 찾아야 데이터 탐색이 종료됩니다.
 
 

Leaf node는 앞뒤로 이중 연결 리스트를 위한 pointer가 있고, 실제 데이터의 위치를 가리키는 Data pointer가 있습니다.
이중 연결 리스트로 연결되어 있어서 범위 검색이 용이합니다.
4~10이라는 데이터를 조회할 때, 4를 찾고, Root에서 시작해서 다시 5를 찾는 것이 아니라 4를 먼저 찾고 10까지 연결 리스트를 활용해 Leaf node에서만 탐색을 합니다.
 
그러면, 다시 이걸 확인해봅시다.

• 정렬된 구조
• 균형 잡힌 구조
• 하나의 페이지에 많은 키를 담아서, 트리의 높이가 낮은 구조
• 높은 fan-out으로 디스크 I/O 최소화
• 리프 노드가 연결 리스트라 범위 탐색 유리 ✅

 
 

1. 정렬된 구조

우선, Leaf node를 보면 모두 정렬된 형태인데요.
아래와 같이, Root node, Internal node도 정렬된 형태입니다. 이 구조를 영원히 유지합니다.
 

이 분기를 위한 노드의 키 값도 모두 정렬된 형태로 저장되며, 키 값을 기준으로 크고 작음에 따라 다음 노드로 분기 처리 합니다.
정렬이 되지 않고서야, 이 규칙으로 분기가 될 수가 없겠죠?
 
 

2. 균형 잡힌 구조

트리라는 자료구조가 본래, 삽입과 삭제가 일어남에 따라 균형이 무너질 수 밖에 없습니다. 이 때, DBMS 내부의 인덱스 엔진이 노드를 분할, 병합, 재분배 등을 통해 균형 트리가 되도록 계속해서 유지합니다. 그래서, 인덱스가 추가되면 삽입/삭제 연산이 느려진다는 것입니다.
 
균형을 잡는 데 적용되는 철칙은 다음과 같습니다.

B+ tree의 구조적 불변 조건

1. Root 는 Leaf 그 자체이거나 2 ~ M개의 자식 노드를 갖는다.
2. Leaf가 아닌 노드(Root 제외), 즉 Internal 노드는 반드시 자식 노드가 2 ~ M개이다.
3. 모든 Leaf는 같은 깊이(depth)이다.

 
이 때, M은 B+ tree의 차수(order)입니다. 의미는 한 노드가 가질 수 있는 최대 자식 수입니다.
아래와 같이 예제에서는 M이 3이겠네요.

 
균형을 잡는 로직에 대해서는 추후 포스팅할게요! 🤗
 
 

3. 하나의 페이지에 많은 키를 담아서, 트리의 높이가 낮은 구조
4. 높은 fan-out으로 디스크 I/O 최소화

위 3번과 4번 특징은 같은 특징입니다.
fan-out이라는 것은 한 노드가 가질 수 있는 자식 수, 즉 위에서의 M 값이고, 하나의 페이지에 많은 키를 담는다는 의미가 결국 자식 수 M이 늘어난다는 것이죠.
 
 

그러면, 예제에서는 fan-out(= M) 값이 3이고, 테이블이 커짐에 따라 fan-out이 점점 커지는 구조겠네요?

좋은 관찰이지만, 핵심적으로 그것은 아닙니다. fan-out은 고정된 값입니다.
노드 1개당 들어갈 수 있는 최대 key/pointer의 수는 페이지 크기 + 인덱스 key의 크기 + 포인터 크기 3가지에 의해 고정됩니다.
 
 

🪄 MySQL InnoDB 기반 DB 예시

1. INT (4B 정수) 컬럼의 인덱스

InnoDB 인덱스 페이지 크기	16KB (innodb_page_size)
Leaf node	key + row data or PK
Internal node	key + child pointer
Key	4 bytes
Child pointer	약 6 ~ 8 bytes
Overhead	메타 데이터, slot 등 포함

 
대략 키 하나당 16 ~ 20 bytes
= 약 800 ~ 1000개 key/pointer
= fanout = M = 800 ~ 1000
 
 
2. VARCHAR(8) 컬럼의 인덱스

InnoDB 인덱스 페이지 크기	16KB (innodb_page_size)
Key (UTF-8 기준 char당 3 bytes)	24 bytes
문자열 길이 정보	1 byte
Child pointer	약 6 ~ 8 bytes
Overhead	메타 데이터, slot 등 포함

 
대략 키 하나당 32 ~ 40 bytes
= 약 300 ~ 400개 key/pointer
= fanout = M = 300 ~ 400
 
 

🚩 결론

fan-out이 커지면 한 노드에 저장할 수 있는 데이터의 양이 많아진다는 것입니다.
 
인덱스의 노드나 데이터 테이블이나 모두 디스크에 저장이 되는데, 하나의 노드를 탐색한다는 것은 디스크를 1번 접근한다는 것입니다. 즉, 디스크 I/O 한 번이라는 뜻이죠. 물론 한 번 가져온 노드는 메모리에 적재를 하면서 캐싱을 하기 때문에 계속 디스크를 접근하는 것은 아닙니다.
 
한 노드에 저장할 수 있는 데이터의 양이 많아진다는 것은 자식 수가 그만큼 비례해서 많다는 것이고, 트리 구조를 봤을 때 데이터가 많아도, 같은 레벨에서 옆으로 계속해서 늘어나지, 깊이는 잘 늘어나지 않는다는 특성을 가진다는 것입니다.
 
따라서, 하나의 데이터를 찾을 때 많은 노드를 탐색하지 않는다는 의미입니다. 이 것이 디스크 I/O가 최소화된다는 결론입니다.
가령, 수백만 건의 데이터 중에서도 3~4번의 디스크 접근만으로 데이터를 찾을 수 있습니다.
 
 
 

👏

 

자, 이렇게 인덱스에 주로 사용되는 B+ tree에 대해서 다뤄봤습니다!
지난 포스팅이 너무 길어서 나눠봤습니다! 🤗
저도 이 포스팅을 작성하면서, 좀 더 상세하게 공부를 하게 된 것 같은데요...!
 
평비의 이 평범한 글이 여러분에게 비범한 도움이 되었으면 좋겠습니다 👍