B 트리
데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.
특징
- 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있다.
- 항목이 삽입될 때 하향식으로 구성되는 이진 트리에 비해 B-트리는 일반적으로 상향식으로 구성된다.
- 내부 노드의 자식 노드의 수가 미리 정해진 범위 내에서 변경가능하다.
- 항목이 삽입, 삭제될 때 내부 노드는 해당 범위의 자식 노드의 수를 만족시키기 위해 분리되거나 다른 노드와 합쳐지게 된다.
탐색
- 이진 탐색 트리와 동일한 방식으로 수행
- 루트에서 시작해 하향식으로 탐색 대상의 값을 구분 값과 비교하여 자식 포인터를 찾아나감
삽입
- 삽입될 노드가 어느 위치로 삽입될지 찾아 해당 부모 노드에 삽입
- 부적절한 상태의 노드(그 노드에 허용된 자식 노드의 숫자가 허용된 범위 밖인 노드)가 없다면 삽입 과정 종료
- 만약, 어떤 노드가 너무 많은 항목을 가지고 있다면, 이를 두 노드로 분리하고 이 과정을 반복적으로 트리를 타고 올라가며 진행
- 만약 루트 노드를 분리하였다면, 새로운 루트 노드를 만든다