B-Tree와 B+Tree

B트리 (B-Tree)

정의

B트리는 자가 균형 다진 트리(M-ary tree)이다. 즉, 모든 리프의 노드가 같은 depth 를 가지며, 내부 노드가 여러 자식을 가질 수 있다.

m은 B트리의 차수이다. 각 노드는 최대 m개의 자식을 가질 수 있다.

ㄴ 3차 B트리라고 한다면, m은 3이고 최대 3개의 자식을 가질 수 있다는 것.

 

 

구조와 속성

• 루트 노드: (트리가 비어있지 않을 때) 2개 이상, m개 이하의 자식을 가진다. 
• 내부 노드: ⌈m/2⌉개 이상, m개 이하의  자식을 가진다.
• 리프노드: 모든 리프 노드는 동일한 레벨에 있다. 균형 유지
• 노드의 키: 각 노드는 ⌈m/2⌉개 이상, m-1개 이하의 키를 가진다. 정렬된 상태를 유지하고 있어 효율적 탐색이 가능하다.

 

 

장단점

• 장점
  • 자동으로 균형을 유지하여 검색, 삽입, 삭제 연산이 효율적으로 수행된다. 복잡도 O(logn).
  • 한 노드에 여러 키를 저장할 수 있어, 디스크 I/O 횟수를 줄일 수 있다.
  • 트리는 동적으로 성장하거나 축소될 수 있어, 데이터 크기 변화에 유연하게 대응할 수 있다.
• 단점
  1. 노드 분할과 병합 등의 연산이 복잡하여 구현이 어렵다
  2. 각 노드가 특정 개수의 키와 자식을 유지해야 하므로, 일부 공간이 비효율적으로 사용될 수 있다.
  3. 순차적인 데이터 접근이 많은 경우 비효율적이다.

 

 

 

B트리 연산

탐색 (Search)

 

1. 루트 노드에서 시작하여 키를 찾음.
2. 찾는 키가 현재 노드에 있으면 종료.
3. 찾는 키가 현재 노드에 없으면 자식노드로 이동.
   ㄴ 노드의 키를 기준으로 이진탐색트리와 마찬가지로 left노드는 키 값보다 작고, right 노드는 크다.
4. 리프 노드에 도달할 때까지 반복.

 

삽입 (Insert)

모든 삽입은 리프 노드에서 일어나며, 리프 노드가 가득 차있을 때와 차지 않았을 때 차이가 있다.

 

 

 

1. 루트 노드에서 시작하여 삽입 위치 찾음.
2. 리프 노드까지 도달.
3. 해당 노드가 가득 차있지 않다면, 리프노드에 삽입.
4. 해당 노드가 가득 차있다면 노드를 분할 한 후, 리프노드에 삽입.
   ㄴ 중간 키를 부모노드로 올리고, 나머지 키들을 두개의 자식 노드로 나눈다.
   ㄴ 분할이 루트 노드까지 전파될 수 있다. 이 경우 새로운 루트 노드가 생성된다.

 

* 분할 과정 예시

초기 상태

 

노드 6 삽입 후

1. 노드의 키 값 [3, 4, 5] 중 중간 값인 4를 부모 노드로 올리고
2. 중간 값을 기준으로 두개의 자식 노드로 분할
3. 이 후 리프노드에 6 추가

 

삭제 (Delete)

삭제 시 노드가 최소 키 수를 충족하지 않게 되면 병합(Merge) 또는 차용(Borrow) 연산이 발생한다.

 

1. 루트 노드에서 시작하여 삭제할 키를 찾음.
2. 키가 리프 노드에 있다면 키를 삭제.
3. 키가 내부 노드에 있다면:
   • 키의 왼쪽 서브트리에서 최대 키를 찾거나, 오른쪽 서브트리에서 최소 키를 찾는다.
   • 찾은 키로 삭제할 키를 대체한다.
   • 대체된 키를 삭제한다.
4. 삭제 후 노드가 최소 키 수를 충족하지 않으면 병합 또는 차용을 수행.
   • 부모 키 위치에 형제 노드 키를 차용하거나, 부모 키와 형제 노드와 병합.

 

* 형제 노드 차용 예시

초기 상태

노드 5 삭제 후

1. 5를 삭제하게 되면 최소 차수(1)를 만족하지 못함.
   형제 노드가 최소 키 수보다 많은 키를 가지고 있으면 형제노드 차용.
2. 원래 부모 노드였던 6을 삭제 위치로.
3. 오른쪽 형제노드 최소값을 부모 위치로.

 

 

* 형제 노드 합병 예시

노드 1 삭제 후

1. 1을 삭제하게 되면 최소 차수(1)를 만족하지 못함.
   형제노드가 최소 키 수 이하의 키를 가지고 있으므로 차용 불가.
2. 부모 키 값을 형제 노드로 합병.
   부모 노드의 데이터 수 줄어듬. 

 

 

 

 

 

---

B+트리 (B+Tree)

정의

B+트리는 B트리의 변형으로, 모든 데이터가 리프 노드에만 저장되고 내부 노드는 인덱스 역할만 하는 트리구조이다.

리프 노드를 연결 리스트 형태로 연결하여 B트리의 단점인 데이터의 순차적 접근에서의 성능 저하를 최적화했다.

 

 

구조와 속성

 

• 내부 노드: 인덱스 키만을 포함하고, 자식 노드에 대한 포인터를 가진다. 데이터는 저장하지 않는다.
• 리프 노드: 모든 데이터를 저장하며, 각 리프 노드는 양방향 연결 리스트로 연결되어 있다.
• 차수: m인 B+트리에서 각 노드는 최소⌈m/2​⌉개의 자식과 최대 m개의 자식을 가진다.

 

장단점

• 장점
  • 자동으로 균형을 유지하여 검색, 삽입, 삭제 연산이 효율적으로 수행된다. 복잡도 O(logn).
  • 내부 노드는 익덱스 역할만 하므로, 디스크 I/O 성능이 향샹된다.
  • 리프 노드가 연결 리스트 형태로 연결되어 있어 순차 접근이 매우 빠르다
  • 리프 노드에만 데이터를 저장하므로 같은 높이의 B트리보다 더 많은 키를 저장할 수 있다.
• 단점
  1. B트리보다 구조가 복잡하여 구현이 어렵다
  2. 각 노드가 특정 개수의 키와 자식을 유지해야 하므로, 일부 공간이 비효율적으로 사용될 수 있다.

 

 

B+트리 연산

탐색(Search)

B+트리에서의 검색은 B트리와 유사하지만, 모든 데이터는 리프노드에 저장되어 있으므로 끝까지 내려가야 한다.

1. 루트 노드에서 시작하여 키를 기준으로 적절한 자식 노드로 이동.
2. 리프 노드에 도달할 때까지 이 과정을 반복.
3. 리프 노드에서 키를 찾으면 종료.

 

삽입(Insert)

삽입 과정도 B트리와 유사하지만, 데이터는 리프 노드에만 저장된다.

1. 삽입할 키의 위치를 찾음.
2. 리프 노드에 키를 삽입.
3. 리프 노드가 가득 찬 경우 분할하여 부모 노드에 중간 키를 삽입.
4. 필요하다면, 부모 노드에서 분할과 삽입이 전파될 수 있다.

 

삭제(Delete)

1. 삭제할 키의 위치를 찾는다.
2. 리프 노드에서 키를 삭제한다.
3. 리프 노드가 최소 키 수를 만족하지 않으면, 형제 노드에서 키를 차용하거나 병합한다.
4. 필요하다면, 부모 노드에서 재조정이 일어날 수 있다.

 

 

 

 

 

Binary Search Tree에서 B+Tree까지(Database Index 추가)