- 데이터베이스와 파일 시스템에서 널리 사용되는 트리 구조
- 이진 트리를 확장하여
하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조 - 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 로그 시간으로 할 수 있음
- 이진 트리는 항목이 삽입될 때 하향식으로 구성되는 데 반해,
B-트리는 일반적으로 상향식으로 구성 - 내부 노드의 자식 노드의 수가 미리 정해진 범위 내에서 변경 가능
- 항목이 삽입되거나 삭제될 때, 내부 노드는 해당 범위의 자식 노드의 수를 만족시키기 위해 분리되거나 혹은 다른 노드와 합쳐짐
- 자식 노드의 수가 일정 범위 내에서만 유지되면 되므로 분리 및 합침을 통한 재균형 과정은 다른 자가 균형 이진 탐색 트리만큼 자주 일어나진 않지만, 저장 공간에서의 손실은 있음
- 자식 노드의 최소 및 최대 수는 일반적으로 특별한 구현에 대해 결정되어 있음
> 2–3 B-트리의 경우 각 내부 노드는 2또는 3개의 자식 노드를 가질 수 있음
> 2–3트리에서 2개 미만이거나 3개를 초과하는 자식 노드를 갖는 경우와 같이 부적절한 상태에 있는 노드는 그 노드에 허용된 자식 노드의 숫자가 허용된 범위 밖인 노드 - 노드 접근시간이 노드에서의 연산시간에 비해 훨씬 길 경우, 다른 구현 방식에 비해 이점을 가짐.
> 각 내부 노드에 있는 자식 노드의 수를 최대화함으로써, 트리의 높이가 감소하여 균형 맞춤은 덜 일어나고, 효율은 증가 - 루트 노드를 제외한 모든 노드는 임의의 수 L, U(L<U)에 대해
최소 L항목, 최대 U항목을 가짐
> 최대 U+1개의 자식 포인터를 가지고 있음
> 모든 내부 노드에서, 자식 포인터의 수는 언제나 항목 개수보다 하나가 많음
> 모든 리프 노드가 동일한 높이에 있기 때문에, 노드는 일반적으로 리프 노드인지 내부 노드인지 판별하는 수단을 가질 필요가 없음
traversal
- 이진 탐색 트리와 동일한 방식으로 수행
- 루트에서 시작하여, 하향식으로 탐색 대상의 값을 구분 값과 비교하며
자식 포인터를 찾아나감
Insert
1 — 삽입될 노드가 어느 위치로 삽입될지 찾아 해당 부모 노드에 삽입
2 — 부적절한 상태의 노드가 없다면 삽입 종료
2–1 ) 어떤 노드가 너무 많은 항목을 가지고 있다면 두 노드로 분리
2–2 ) 반복적으로 트리를 타고 올라가며 진행
2–3 ) 루트 노드를 분리하였다면, 새로운 루트 노드를 만듦
Delete
