B 플러스 트리

많은 분기를 두는 이유

노드 하나에 여러 키와 자식 참조를 담을 수 있다. 저장 장치의 블록이나 페이지에 맞춰 많은 분기를 두면 이진 트리보다 적은 단계로 많은 항목에 접근할 수 있다. 실제 분기 수는 키와 참조의 크기, 페이지 크기 등의 영향을 받는다.

탐색과 범위 순회

내부 노드의 구분 키를 비교하여 해당하는 자식으로 내려가고 잎에서 항목을 찾는다. 순서대로 연결된 잎을 이용하면 시작 키를 찾은 뒤 인접한 항목들을 계속 읽을 수 있다. 예를 들어 120 이상 160 미만의 키를 구하는 질의는 시작점 탐색과 이후의 범위 순회로 나눌 수 있다.

삽입과 삭제

새 항목이 들어갈 잎에 공간이 부족하면 노드를 분할하고 부모의 구분 정보를 갱신한다. 분할이 위로 전파되어 루트가 바뀔 수도 있다. 삭제 뒤 점유 조건이 깨지면 이웃 노드와 재분배하거나 병합한다. 정확한 점유 기준과 예외는 트리 정의와 구현에 따라 확인해야 한다.

용어와 구현

기본 B 트리와 달리 데이터 값은 잎에 모으고 내부 노드는 탐색용으로 사용한다. 다만 제품 문서가 B 트리라는 이름으로 여러 변형을 통칭하기도 한다. 인덱스가 정렬되어 있다는 사실만으로 테이블의 물리적 행 배치까지 같은 순서라고 결론 내릴 수는 없다.