5-2 B-트리

1. B-트리 

① B-트리

  - 이진 트리 확장하여 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조

  - 하나의 노드에 많은 수의 데이터가 배치

② 다진검색트리

  - 키가 k개 있으면 k+1개 자식 가짐.

  - 루트를 제외한 모든 노드는 k/2~k 개의 키를 가짐.

  - 모든 리프 노드는 같은 깊이 가짐.

  - 균형을 위해 최대 허용량의 반 이상의 키는 채워야 하는 검색 트리

 

2. B-트리에서 삽입 

3. B-트리에서 삭제

① 삭제 과정

  - x 를 키로 갖는 노드 탐색

  - 리프 노드가 아니면 x 직후 원소 y를 가진 리프 노드 r 찾아 x,y바꿈

  -  리프 노드 x 제거

  -  x제거 후 노드에 언더 플로우가 발생하면 적절히 해소

 

② 예시