B-Tree란? 구조와 연산 과정을 살펴보자

B-Tree란?

B-Tree란 RDBMS에서 가장 많이 사용되는 Self Balanced Tree (자가 균형 이진 검색 트리)로

대량의 데이터를 효율적으로 저장하고 검색하기 위해 고안된 O(logN)의 시간 복잡도를 갖는 자료 구조이다.

 

B-Tree는 이진 트리(Binary Search)에서 여러 가지 면에서 확장된 구조이다.

이진 트리와 b-tree의 차이를 한번 가볍게 살펴보자.

 

이진 트리 vs B-Tree

이진 트리	각 노드는 최대 두 개의 자식(왼쪽, 오른쪽)을 가질 수 있다.
B-Tree	각 노드는 최대 m개의 자식을 가질 수 있으며, m은 B-Tree의 차수(각 노드가 지닌 가지의 수)이다.

위 비교를 보면 B-Tree는 더 많은 자식을 가질 수 있는 것을 볼 수 있다.

이는 곧 B-Tree가 노드당 하나의 키만 저장하는 이진 트리에 비해 더 효율적인 I/O 작업이 가능하고,

각 노드에 여러 개의 키를 저장할 수 있어 데이터 밀도가 높아 메모리와 저장 공간을 효율적으로 사용할 수 있다는 것을 알 수 있다.

---

InnoDB의 B-Tree의 자식 노드 개수와 깊이

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 기본 단위를 ‘페이지’라고 한다.

이는 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다.

또한 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 하다.

인덱스도 페이지 단위로 관리된다.

인덱스가 사용하는 자료구조인 B-Tree는 자식 노드 개수가 가변적이 구조이다.

이 자식 노드의 개수는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다.

 

페이지 크기는 4KB ~ 64KB의 크기로 설정할 수 있지만 기본 값은 16KB이다.

 

클러스터링 인덱스 기준 인덱스 키 크기와 자식 노드 주소 영역의 크기는 다음과 같다.

(논 클러스터링 인덱스의 경우 인덱스 키와 PK 값을 모두 저장하기 때문에 16 + 16 = 32 바이트의 크기를 갖는다.)

 

자식 노드의 개수는 아래의 공식으로 구할 수 있다.

페이지 크기 KB * 1024 / (인덱스 키 크기 BYTE + 자식 노드 주소 영역 크기 BYTE)

 

위 공식을 바탕으로

인덱스 키 값의 크기가 클 수록 가질 수 있는 자식 수가 적어지고, 이 때 더 많은 데이터를 저장하기 위해 B-Tree의 깊이가 깊어진다.

깊이가 깊어진다는 것은 많은 키 값을 담는 다는 것이고 이는 곧 랜덤 I/O가 더 많이 일어나는 문제와 직결된다.

인덱스 키 값의 크기는 작게 만들어 인덱스의 깊이가 깊지 않게 만드는 것이 가장 좋은데

보통 깊이가 5단계 이상으로는 늘어나지 않는도록 한다고 한다.

---

B-Tree 규칙

B-Tree를 유지하기 위한 몇 가지 규칙을 살펴보자.

 

B-Tree의 차수 m에 따라 각 노드는 최소 m / 2개의 자식 노드를 가져야 하며, 최대 m개의 자식 노드를 가질 수 있다.

즉, 각 노드는 최소한 차수 절반 이상의 자식을 가져야 한다.

 

각 노드는 최소 (m / 2) - 1개의 키를 가지고 있어야 하며, 최대 m - 1개의 키를 가질 수 있다.

위 규칙으로 노드가 비어있지 않도록 보장한다.

 

각 노드의 키는 오름차순으로 정렬되어 있어야 하며, 자식 노드는 부모 노드의 키 값에 따라 구분된다. (아래는 차수가 3인 트리)

 

모든 리프 노드는 동일한 깊이에 위치해야 한다.

이로 인해 B-트리는 항상 균형을 유지한다.

 

 

이러한 규칙들로 인해 B-Tree가 효율적으로 동작하고 데이터를 균형 있게 저장할 수 있다.

---

B-Tree 구조

 

구성 요소

• 노드(Node) : 각 노드는 키와 자식 노드를 포함한다.
• 키(Key) : 노드 안에 저장된 데이터 식별자로, 정렬된 순서로 배치된다.
• 자식 노드(Child Node) : 부모 하위의 노드로, 자식 노드는 부모 노드의 키 값을 기반으로 구분된다.

 

구조

B 트리 구조를 간단하게 그리면 위와 같다.

각 층마다 하나의 큰 네모칸은 노드, 노드 안의 숫자는 Key를 나타내며, 빨간색 부분은 자식 노드들을 가르키는 Pointer이다.

Key들은 노드안에서 항상 정렬된 값을 가지고 있다.

 

그리고 노드의 시작점인 루트 노드와 노드의 마지막 지점인 리프 노드로 구분되어 있다.

---

B-Tree 연산

 

탐색 과정

루트노드에서 부터 하향식으로 탐색한다.

자식 노드의 데이터는 부모 노드의 데이터에 따라 오름차순으로 배치되고

이를 활용해 대소비교를 통해 원하는 Key를 찾을 때까지 하향 탐색한다.

 

삽입 과정

위에서 언급한 B-Tree 규칙에서 "각 노드는 최대 m - 1개의 키를 가질 수 있다" 규칙이 적용되는 상황으로

삽입 과정은 다음과 같이 2가지로 나뉜다.  "리프 노드에 키가 가득 찼을 때와 아닐 때"

 

리프 노드에 키가 가득 차지 않았을 때 (리프 노드의 키 수가 m - 1 개를 넘지 않을 때)

루트 노드에서 시작해 삽입하는 키가 들어가기 적절한 노드를 찾아 하향식으로 탐색 후 추가 한다.

 

리프 노드에 키가 가득 찼을 때 (리프 노드의 키 수가 m - 1 개 이상 일 때)

키를 추가할 때는 위 과정과 동일하게 하향식으로 적절한 리프 노드를 찾고 추가한다.

하지만 리프 노드에 키를 추가 후 데이터가 가득 찼다면 해당 리프 노드의 중앙값을 기준으로 분할을 수행한다.

이 분할은 상향식으로 올라가며 "각 노드는 최대 m - 1개의 키를 가질 수 있다" 규칙을 만족할 때 까지 분할되며 올라간다.

루트 노드까지 분할이 필요하다면 새 루드 노드가 생길 수 있다.

 

삭제 과정

키를 삭제하기 위해선 다음과 같은 3가지 과정이 필요하다.

1. 삭제할 키가 있는 노드를 탐색해

2. 키 삭제

3. 필요한 경우 트리 균형 조정

 

삭제 과정의 경우 삽입 과정에 피해 더 복잡하다.

삭제 과정의 여러 상황을 살펴보자.

현재 노드의 키 수가 "최소 (m / 2) - 1개 규칙" 이상인 경우

루트 노드에서 시작해 삭제할 키가 있는 노드를 찾아 하향식으로 탐색 후 제거 한다.

 

현재 노드의 키 수가 "최소 (m / 2) - 1개 규칙" 보다 작을 경우

부모 키 값으로 삭제한 키 값을 대체한다.

이 경우 최소 키 개수( (m / 2) - 1개) 보다 많은 키를 가진 형제 노드가 왼쪽이냐 오른쪽이냐에 따라 다르다.

왼쪽이라면 형제 노드의 가장 큰 값을 부모 키 값으로 대체한다.

오른쪽이라면 형제 노드의 가장 작은 값을 부모 키 값으로 대체한다.

 

왼쪽, 오른쪽 형제 노드의 key가 (m / 2) - 1개이고, 부모 노드의 key가 (m / 2) - 1 보다 많을 경우

키 값을 삭제후, 부모 노드의 key를 자식 노드로 하나 내어줘 B-Tree 균형을 유지한다.

---

위 삭제 과정에서 더 많은 여러 상황이 있지만 크게 중요하지 않다고 생각해 다루지 않았다.

중요한 부분은 각 과정을 봤을 때 삽입과 삭제 과정에서 비효율적인 작업이 일어난다는 부분이다.

그렇기 때문에 B-Tree 구조를 사용하는 RDBMS의 Index의 장단점으로 검색은 빠르지만 CUD 연산은 느리다고 하는 것이다.

 

이번 포스팅에서는 Index의 기반이 되는 B-Tree 구조에 대해 알아보았다.

Index란 무엇인지 궁금하다면 아래 포스팅을 참고할 것을 추천한다.

2024.08.19 - [◼ CS 기초 지식/[데이터베이스]] - [DB] Index(색인)란? 특징, 종류, 주의할 점 등을 쉽게 알아보자.

[DB] Index(색인)란? 특징, 종류, 주의할 점 등을 쉽게 알아보자.