B-Tree

B-Tree 

• 탐색 성능을 높이기 위해 균형 있게 높이를 유지하는 Balanced Tree 의 일종으로, 모든 leaf node(자식X) 가 같은 level로 유지되도록 자동으로 밸런스를 맞춰줌
• 자식 node 의 개수가 2개 이상이며 node 내의 key 가 1개 이상일 수 있음
• node 의 자식 수 중 최댓값을 K 라고 하면, 해당 B-Tree 를 K차 B-Tree 라고도 함

 

---

 

B-Tree 의 조건

 

1. 노드(node) 에는 2개 이상의 데이터(key) 가 들어갈 수 있으며 항상 정렬된 상태로 저장된다.

한 노드에 2, 3개의 데이터가 들어갈 수 있고 항상 정렬된 상태로 저장

 

 

2. 내부 노드는 M/2 ~ M 개의 자식을 가질 수 있고 최대 M 개의 자식을 가질 수 있는 B-Tree 를 M차 B-Tree라고 한다.

3차 B-Tree의 리프 노드를 제외한 내부 노드는 1개~3개의 자식을 가질 수 있다

 

3. 특정 노드의 데이터(key) 가 K 개라면, 자식 노드의 개수는 K+1 개여야 한다.

특정 노드의 데이터가 2개면 자식 노드는 3개, 특정 노드의 데이터가 1개면 자식 노드는 2개이다.

 

4. 특정 노드의 왼쪽 서브 트리는 특정 노드의 데이터(key) 보다 작은 값들로, 오른쪽 서브 트리는 큰 값들로 구성된다.

10의 왼쪽 서브 트리는 10보다 작은 값인 4가 위치하고 (!0,21) 사이의 서브트리는 10보다 크지만 21보다 작은 값들이 위치한다.

 

5. 노드 내에 데이터는 floor(M/2) - 1 개부터 최대 M - 1 개 까지 포함될 수 있다.

floor() 는 내림 함수로 ex) floor(3.6) = 3 이다. 3차 B-Tree는 노드 내에 0~2개의 데이터를 가질 수 있다.

 

6. 모든 리프 노드들이 같은 레벨에 존재한다.

모든 리프 노드들은 같은 레벨에 존재해야 한다. 즉, 루트 노드에서 모든 리프 노드로 가는 경로의 길이가 같다.

 

---

 

B-Tree 탐색 과정

: B-Tree 는 루트 노드에서 탐색을 시작해 하향식으로 탐색을 진행한다. 찾으려 하는 값이 K 라면 아래의 과정을 거친다.

 

1. 루트 노드에서 탐색을 시작한다.
2. K를 찾았다면 탐색을 종료한다.
3. K와 노드의 key 값을 비교해 알맞은 자식 노드로 내려간다.
4. 해당 과정을 리프 노드에 도달할 때 까지 반복한다.
5. 리프 노드에서도 K를 찾지 못한다면 트리에 값이 존재하지 않는 것이다.

 

 

B-Tree 삽입 과정

: B-Tree 에 데이터를 삽입하는 과정은 상향식으로 진행되며 데이터 삽입은 항상 리프 노드에서 시작된다.

 

1. 트리가 비어있다면 루트 노드를 할당하고 K를 삽입한다. 
2. 트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드를 탐색한다.
3. 리프 노드에 데이터를 넣고 리프 노드가 적절한 상태에 있다면 종료한다.
4. 리프 노드가 부적절한 상태에 있다면 분리한다. 

- 적절한 상태란 해당 노드의 데이터 개수가 허용 범위 안에 있는 것이고 부적절한 상태는 해당 노드의 데이터 개수가 허용 범위를 벗어나 너무 많은 상태를 의미한다.