B-Tree, Balanced Tree

B-Tree

 

정의 :

- 2개 이상의 자식 노드를 가질 수 있고, 노드에 2개 이상의 key를 넣을 수 있는 트리구조

---

특징 :

- 다른 트리 구조와는 다르게, 1개의 노드에 2개 이상의 key를 입력할 수 있다. 

 

- M차 B-Tree 구조라면, 최대 M개의 자식 노드를 가진다.

 

- Root node, Leaf node를 제외한 각 노드는 최소 ⌈M/2⌉ 개의 자식 노드를 가진다. (나눈 후 반올림)

 

- 각 노드의 최대 key 개수는 M-1개이다.

 

- 각 노드의 key는 정렬 상태이다.

 

- 모든 Leaf node는 같은 높이에 위치한다.

 

- Leaf node는 linked list로 연결되어 있다.

 

- 부모 노드의 값보다 작은 자식노드는 왼쪽, 큰 자식노드는 오른쪽, 중간 값의 자식노드는 중앙에 위치한다.

---

장점 :

- Disk operation을 감소시킬 수 있다.

 

-> Disk operation은 Tree의 높이와 비례하는데, B-Tree 구조에서 노드는 2개 이상의 key를 갖고, 자식 노드 또한 2개 이상이다. 

--> Tree 구조의 높이가 낮고, 정렬된 상태이기 때문에 특정 key를 찾는 데 범위탐색이 가능하다.

 

- 큰 용량의 데이터 처리에 용이하다

 

-> 항상 정렬되어 있는 상태의 트리 구조이고, 삽입과 삭제 과정 또한 비효율적이지 않고, 범위탐색을 통한 검색도 빠르고, 균형적이며 트리의 높이는 낮다.

--> 큰 용량의 데이터를 B-Tree화 시켜 관리한다면 얻을 수 있는 이득이 이진 트리에 비해 많다.

---

단점 :

- 삽입/삭제 과정 수행 시 Tree의 균형을 맞추기 위해 다른 노드의 변형이 일어날 수 있어 복잡한 연산이 수행된다.

 

---

- 같은 Linked list인 해시테이블에 비해 B-Tree가 더 좋은가? 

: 해시 테이블은 정렬되어 있지 않기 때문에 범위탐색이 불가능하다.

 

- 배열에 비해 B-Tree가 더 좋은가? 

: 탐색 속도는 배열 형태가 더 좋을 수 있으나, 데이터의 삽입/삭제 과정 수행 시 비효율적인 연산과정이 발생한다.

 

---

--> 따라서 대규모의 데이터 로드를 위한 접근은 B-Tree가 배열, 해시테이블에 비해 효율적이라 할 수 있다 !!