B-Tree와 B+Tree

균형 트리 (Balanced Tree)

---

이진트리는 그 균형이 맞지 않으면 검색 성능이 선형 탐색과 유사해진다. 한 방향의 트리는 연결 리스트와 같다.

 

이러한 문제를 해결하기 위해 균형 트리가 탄생하였다. 종류는 Red-Black Tree, B-Tree등이 있는데 이러한 균형 트리는 균형을 유지하기 위해 삽입 or 삭제시 스스로 균형을 유지해 나간다. 균형을 유지한 덕분에 균형트리는 O(logN)의 탐색 성능을 보장한다.

 

 

B-Tree

---

균형트리의 한 종류로 자식 노드가 두 개로 고정된 이진 트리와 달리 자식 노드의 개수가 최대 M개인 트리로  자식 노드의 최대 개수를 차수라고 한다. 이 차수가 홀수인지 짝수인지에 따라 알고리즘이 많이 달라진다.

 

조건

B-Tree의 조건은 아래와 같다.

 

노드의 데이터 개수가 n개이면 자식 노드는 n+1개 이다.

노드의 데이터는 정렬된 상태이다.

자식 노드의 데이터는 부모 노드의 데이터보다 왼쪽에 있으면 작은 값을 오른쪽에 있으면 큰 값을 나타낸다.

Root 노드의 자식이 있다면 반드시 2개 이상이다.

Root 노드를 제외한 모든 노드는 적어도 차수/2개의 데이터를 가져야한다.

Leaf노드(자식 노드가 존재하지 않는 노드들)의 레벨이 모두 같아야 한다.

입력 자료는 중복할 수 없다.

 

 

B+Tree

---

B+Tree는 인덱스 노드와, 데이터 노드를 분류하고 모든 데이터 노드는 Leaf 노드이며 데이터 노드들은 서로 연결리스트로 연결되어 있다.

이러한 특성 덕분에 빠른 탐색 성능을 가지고 있다.