[Data Structure] B-Tree 기초

트리 기본 용어에 관하여는 아래의 글을 참고.

2022.08.27 - [Data Structure/Tree] - [Data Structure] Tree 기본

[Data Structure] Tree 기본

---

B-Tree 란

• 트리 자료구조의 일종. 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조.

 

B-Tree의 특징

   1. 최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree 라고 한다.

3차 B-Tree 일 경우

   2. node 에는 2개 이상의 데이터가 들어갈 수 있고, 항상 정렬된 상태로 저장된다.

 

   3. node의 데이터 수가 k개라면, 자식 노드의 수는 k+1개다.

• 아래는 3차 b-tree 일 경우, 데이터의 수가 k 개 일 때, 자식 노드의 최대 노드의 수를 표현한 것이다.

3차 b-tree 일 경우

   4. 이진 탐색 트리와 같이 각 데이터의 왼쪽 자식은 자신보다 작고, 오른쪽 자식은 자신보다 크다

 

   5. M차 트리일 때, root 노드와 leaf 노드를 제외한 모든 노드는 최소 M/2개, 최대 M 개의 서브 트리를 갖는다.

        3차 B-Tree 일 경우, 아래와 같이 자식 노드의 수가 4개가 되는 것은 불가능하다.

3차 B-Tree 일 경우

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

 

   8. 모든 leaf 노드들은 같은 level에 있어야 한다.

같은 level에 있지 않은 경우

 

B-tree를 사용하는 이유

 

• 편향 트리의 시간 복잡도 극복을 위함. balance를 유지하기 위함
  • 일반적인 트리의 경우, 탐색에 평균 시간 복잡도는 O(logn)이다.
  • 하지만, 편향 트리일 경우 최악의 시간 복잡도는 O(n)이다.