[DB] B-Tree (Balanced Tree): 데이터베이스 인덱스 저장 방식

 데이터베이스에서 인덱스를 저장하는 자료구조로 B-Tree를 주로 씁니다. B-Tree의 개념과 조건에 대해서 알아봅니다.

 

[ Contents ]

 

 

1. B-Tree (Balanced Tree)

한쪽으로 치우치지 않도록, 모든 leaf node가 같은 level를 유지하는 트리

 

 B-Tree는 Binary Tree(이진 트리)의 준말이 아닙니다. Balanced(균형잡힌) Tree로서, 한쪽으로 치우치지 않고 좌우가 균등한 트리를 뜻합니다.

 

선형탐색과 동일

 Tree 형태의 탐색 시간은 O(logN)의 시간복잡도를 갖지만, 극도로 치우쳐져 일자로 나열된 트리는 O(N)의 시간복잡도를 가질수도 있습니다. 따라서 트리의 탐색 효율을 보장하려면 좌우가 균등해야 합니다.

 

 

2. B-Tree가 되기위한 조건

1. 모든 노드들은 최대 m개의 자식을 갖음
2. 리프 노드를 제외하고, k개의 자식을 가진 노드는 k-1개의 키를 가진다.
3. 리프 노드를 제외하고, 최소 m//2 +1개의 자식을 가져야 한다. (최소 2개 이상)
4. 모든 리프 노드는 같은 레벨에 있어야 한다.

 

1) 모든 노드들은 최대 m개의 자식을 갖음

 

 m은 노드당 자식의 개수(degree)를 정하는 파라미터입니다.

 임의로 지정할 수 있으며, 이 글의 예시에서는 m = 3으로 설정하겠습니다.

 

 

2) 리프 노드를 제외하고, k개의 자식을 가진 노드는 k-1개의 키를 가진다.

 

 피라미드처럼 쌓이는 트리 구조를 위해서는 자식이 더 많아야 겠죠.

 부모 노드보다 자식 노드가 1개를 더 가지며, 여기서 '키'는 데이터 인덱스(식별자)를 뜻합니다. 본래 B트리는 데이터베이스의 인덱스 탐색에 이용되며, 각 노드는 하나 이상의 키를 가지고 있습니다.

 

 

3) 리프 노드를 제외하고, 최소 m//2 +1개의 자식을 가져야 한다. (최소 2개 이상)

 

 m//2 + 1 (m 나누기 2의 몫 + 1) 는 쉽게 말해 m/2를 반올림한 값입니다.

 m=3일 때, 3/2를 반올림한 값은 2입니다. 설사 m이 3보다 작더라도 B트리는 최소 2개 이상의 자식을 가져야 합니다.

 

 

4) 모든 리프 노드는 같은 레벨에 있어야 한다.

 

 B-Tree는 한쪽으로 치우치지 않은 트리이므로, 모든 리프 노드가 같은 레벨을 유지합니다.

 

 

 노드가 일정량 쌓이면 한번에 다음 Level에 쏟아내는 식으로 진행하기 때문에 모든 리프 노드가 같은 레벨에 있을 수 있습니다. 

 

2023.08.08 - [CS/DB] - [DB] B-Tree 탐색, 삽입, 삭제 과정 알아보기

[DB] B-Tree 탐색, 삽입, 삭제 과정 알아보기

(B-Tree의 탐색, 삽입, 삭제 과정은 위 글에서 보실 수 있습니다.)

 

반응형