B+ Tree는 효율적인 삽입, 삭제, 검색 작업을 가능하게 하는 B Tree의 확장입니다.
B 트리에서는 키와 레코드가 모두 내부 노드와 리프 노드에 저장될 수 있습니다. 반면 B+ 트리에서는 레코드(데이터)가 리프 노드에만 저장되고 내부 노드에는 키 값만 저장됩니다.
B+ 트리의 리프 노드는 단일 연결 목록 형태로 함께 연결되어 검색 쿼리를 보다 효율적으로 만듭니다.
B+ Tree는 메인 메모리에 저장할 수 없는 대용량 데이터를 저장하는데 사용됩니다. 주 메모리의 크기는 항상 제한되어 있기 때문에 B+ 트리의 내부 노드(기록에 액세스하는 키)는 주 메모리에 저장되고 리프 노드는 보조 메모리에 저장됩니다.
B+ 트리의 내부 노드는 종종 인덱스 노드라고 불립니다. 다음 그림은 3차 B+ 트리를 보여줍니다.
B+트리의 장점
- 동일한 수의 디스크 액세스로 레코드를 가져올 수 있습니다.
- 트리의 높이는 균형을 유지하며 B 트리에 비해 작습니다.
- B+ 트리에 저장된 데이터에 직접 접근할 수도 있고 순차적으로 접근할 수도 있습니다.
- 키는 인덱싱에 사용됩니다.
- 데이터가 리프 노드에만 저장되므로 검색 쿼리가 더 빨라집니다.
B 트리 VS B+ 트리
| SN | B 트리 | B+트리 |
|---|---|---|
| 1 | 검색키는 반복적으로 저장할 수 없습니다. | 중복된 검색 키가 존재할 수 있습니다. |
| 2 | 데이터는 리프 노드와 내부 노드에 저장될 수 있습니다. | 데이터는 리프 노드에만 저장할 수 있습니다. |
| 삼 | 데이터는 리프 노드뿐만 아니라 내부 노드에서도 찾을 수 있으므로 일부 데이터를 검색하는 속도가 느려집니다. | 리프 노드에서만 데이터를 찾을 수 있으므로 검색이 비교적 빠릅니다. |
| 4 | 내부 노드를 삭제하는 것은 매우 복잡하고 시간이 많이 걸립니다. | 요소는 항상 리프 노드에서 삭제되므로 삭제 과정은 결코 복잡하지 않습니다. |
| 5 | 리프 노드는 서로 연결될 수 없습니다. | 리프 노드는 서로 연결되어 검색 작업을 보다 효율적으로 만듭니다. |
B+ 트리에 삽입
1 단계: 새 노드를 리프 노드로 삽입
2 단계: 리프에 필요한 공간이 없으면 노드를 분할하고 중간 노드를 다음 인덱스 노드에 복사합니다.
3단계: 인덱스 노드에 필요한 공간이 없으면 노드를 분할하고 중간 요소를 다음 인덱스 페이지에 복사합니다.
예 :
다음 그림에 표시된 순서 5의 B+ 트리에 값 195를 삽입합니다.
195는 190 이후 120의 오른쪽 하위 트리에 삽입됩니다. 원하는 위치에 삽입합니다.
노드에는 최대 요소 수(예: 4)보다 많은 요소가 포함되어 있으므로 이를 분할하고 중앙값 노드를 상위 노드에 배치합니다.
이제 인덱스 노드에는 B+ 트리 속성을 위반하는 6개의 하위 항목과 5개의 키가 포함되어 있으므로 다음과 같이 분할해야 합니다.
B+ 트리에서 삭제
1 단계: 리프에서 키와 데이터를 삭제합니다.
2 단계: 리프 노드에 최소 개수보다 적은 요소가 포함되어 있으면 형제 노드와 노드를 병합하고 그 사이에 있는 키를 삭제합니다.
3단계: 인덱스 노드에 최소 개수보다 적은 요소가 포함되어 있으면 노드를 형제 노드와 병합하고 그 사이의 키를 아래로 이동합니다.
예
다음 그림에 표시된 B+ 트리에서 키 200을 삭제합니다.
200은 190의 오른쪽 하위 트리에 195 이후에 존재합니다. 삭제하세요.
195, 190, 154 및 129를 사용하여 두 노드를 병합합니다.
이제 요소 120은 B+ 트리 속성을 위반하는 노드에 존재하는 단일 요소입니다. 따라서 60, 78, 108, 120을 사용하여 병합해야 합니다.
이제 B+ 트리의 높이가 1씩 감소합니다.
