B+ Tree

B+ Tree

B+ 트리는 B-트리 데이터 구조의 변형입니다. B+ 트리에서 데이터 포인터는 트리의 리프 노드에만 저장됩니다. B+ 트리 에서 리프 노드의 구조는 내부 노드의 구조와 다릅니다. 리프 노드에는 레코드(또는 이 레코드가 포함된 블록)에 대한 데이터 포인터와 함께 검색 필드의 모든 값에 대한 항목이 있습니다. B+ 트리의 리프 노드는 레코드에 대한 검색 필드에 대한 정렬된 액세스를 제공하기 위해 서로 연결됩니다. B+ 트리의 내부 노드는 검색을 안내하는 데 사용됩니다. 리프 노드의 일부 검색 필드 값은 B+ 트리의 내부 노드에서 반복됩니다.

B+ 트리의 특징

• 균형: B+ 트리는 자체 균형이 있습니다. 즉, 트리에 데이터가 추가되거나 제거되면 균형 잡힌 구조를 유지하기 위해 자동으로 조정됩니다. 이를 통해 트리 크기에 관계없이 검색 시간이 비교적 일정하게 유지됩니다.
• 다중 레벨: B+ 트리는 다중 레벨 데이터 구조로, 맨 위에 루트 노드가 있고 그 아래에 하나 이상의 내부 노드 레벨이 있습니다. 최하위 레벨의 리프 노드에는 실제 데이터가 들어 있습니다.
• 정렬됨: B+ 트리는 트리 내 키의 순서를 유지하므로 범위 쿼리 및 정렬된 데이터가 필요한 기타 작업을 쉽게 수행할 수 있습니다.
• Fan-out : B+ 트리는 높은  fan-out 을 가지고 있는데, 이는 각 노드가 많은 자식 노드를 가질 수 있다는 것을 의미합니다. 이는 트리의 높이를 줄이고 검색 및 인덱싱 작업의 효율성을 높입니다.
• 캐시 친화적: B+ 트리는 캐시 친화적으로 설계되었습니다. 즉, 최신 컴퓨터 아키텍처의 캐싱 메커니즘을 활용하여 성능을 향상시킬 수 있습니다.
• 디스크 지향: B+ 트리는 디스크 기반 저장 시스템에 자주 사용되는데, 디스크에서 데이터를 저장하고 검색하는 데 효율적이기 때문입니다.

왜 B+트리를 사용하나요?

• B+ 트리는 효율적인 디스크 액세스를 촉진하는 동시에 I/O 작업을 최소화하므로 데이터 액세스가 느린 저장 시스템에 가장 적합한 선택입니다.
• B+ 트리는 균형 잡힌 구조로 인해 다양한 활동에 대해 예측 가능한 성능을 보장하고 효과적인 범위 기반 쿼리를 용이하게 하기 때문에 빠른 데이터 검색이 필요한 데이터베이스 시스템과 애플리케이션에 적합한 선택입니다.

B+ 트리와 B 트리의 차이점

	B+ 트리	B-트리
구조	데이터 저장을 위한 별도의 리프 노드와 인덱싱을 위한 내부 노드	노드는 키와 데이터 값을 모두 저장합니다.
정렬	더 높은 순서(더 많은 키)	낮은 순서(키가 적음)
키 복제	일반적으로 리프 노드에서 키 복제를 허용합니다.	일반적으로 키 복제를 허용하지 않습니다
디스크 액세스	연결 목록 구조에서 순차적 읽기로 인해 디스크 액세스가 더 좋아짐	내부 노드에서 비순차적 읽기로 인해 디스크 I/O가 더 많아짐
응용 프로그램	범위 쿼리가 일반적인 데이터베이스 시스템, 파일 시스템	메모리 내 데이터 구조, 데이터베이스, 일반 용도
성능	범위 쿼리 및 대량 데이터 검색에 대한 더 나은 성능	검색, 삽입 및 삭제 작업에 대한 균형 잡힌 성능
메모리 사용량	내부 노드에 더 많은 메모리가 필요합니다.	키와 값이 동일한 노드에 저장되므로 메모리가 덜 필요합니다.

B+ 트리 구현

동적 다중 레벨 인덱싱을 구현하기 위해 일반적으로 B-트리 와 B+ 트리가 사용됩니다. 그러나 인덱싱에 사용되는 B-트리의 단점은 특정 키 값에 해당하는 데이터 포인터(키 값을 포함하는 디스크 파일 블록에 대한 포인터)를 B-트리의 노드에 해당 키 값과 함께 저장한다는 것입니다. 그렇게 되면 B-트리의 노드에 패킹할 수 있는 항목 수를 크게 줄여 B-트리의 레벨 수를 늘리고 레코드의 검색 시간을 늘립니다. B+ 트리는 트리의 리프 노드에만 데이터 포인터를 저장하여 위의 단점을 제거합니다. 따라서 B+ 트리의 리프 노드 구조는 B 트리의 내부 노드 구조와 상당히 다릅니다. 여기서 데이터 포인터는 리프 노드에만 있기 때문에 리프 노드는 반드시 모든 키 값과 디스크 파일 블록에 대한 해당 데이터 포인터를 저장해야 액세스할 수 있습니다. 

또한, 리프 노드는 레코드에 대한 정렬된 액세스를 제공하는 데 연결됩니다. 따라서 리프 노드는 인덱스의 첫 번째 레벨을 형성하고, 내부 노드는 다중 레벨 인덱스의 다른 레벨을 형성합니다. 리프 노드의 일부 키 값은 내부 노드에도 나타나 단순히 레코드 검색을 제어하는 ​​매개체 역할을 합니다. 그래서  B+ 트리는 B-트리와 달리 두 가지 차수를 갖고 있음을 알 수 있다. 즉, 내부 노드를 위한 차수 ‘a’와 외부(또는 리프) 노드를 위한 차수 ‘b’가 존재한다. . 

B+ 트리의 구조

B+ 트리에는 두 가지 유형의 노드가 포함됩니다.

• 내부 노드: 내부 노드는 루트 노드에는 없지만 최소 n/2 레코드 포인터에는 존재하는 노드입니다.
• 리프 노드: 리프 노드는 n개의 포인터를 가지고 있는 노드입니다.
•  

B+ 트리에서 레코드 검색

B+ 트리에서 검색

B+ 트리에서 58을 찾아야 한다고 가정해 봅시다. 루트 노드에서 페칭을 시작한 다음 58의 레코드가 들어 있을 수 있는 리프 노드로 이동합니다. 위에 주어진 이미지에서 50과 70 사이에서 58을 얻습니다. 따라서 세 번째 리프 노드에서 리프 노드를 얻고 거기서 58을 얻습니다. 해당 노드를 찾을 수 없으면 '레코드가 발견되지 않음' 메시지를 반환합니다.

B+ 트리에 삽입

B+ 트리에 삽입하는 작업은 다음 단계를 통해 수행됩니다.

• 트리의 모든 요소는 리프 노드에 삽입되어야 합니다. 따라서 적절한 리프 노드로 가는 것이 필요합니다.
• 오버플로가 없으면 키를 증가하는 순서대로 리프 노드에 삽입합니다.

B+트리에서의 삭제

B+ 트리에서의 삭제는 단순히 삭제가 아니라 검색, 삭제, 균형 조정의 결합된 프로세스입니다. 삭제 프로세스의 마지막 단계에서는 B+ 트리를 균형 조정하는 것이 필수적이며, 그렇지 않으면 B+ 트리의 속성에 맞지 않게 됩니다.

B+트리의 장점

• 'l' 레벨의 B+ 트리는 동일한 'l' 레벨의 B-트리에 비해 내부 노드에 더 많은 항목을 저장할 수 있습니다. 이는 주어진 키에 대한 검색 시간에 상당한 개선이 이루어졌음을 강조합니다. 더 낮은 레벨과 P 다음 포인터의 존재는 B+ 트리가 디스크에서 레코드에 액세스하는 데 매우 빠르고 효율적임을 의미합니다. 
• B+ 트리에 저장된 데이터는 순차적으로나 직접 모두 액세스할 수 있습니다.
• 레코드를 가져오려면 동일한 수의 디스크 액세스가 필요합니다.
• B+트리는 중복된 검색 키를 가지며, 검색 키를 반복적으로 저장하는 것은 불가능합니다. 

B+ 트리의 단점

• B-트리의 가장 큰 단점은 키를 순차적으로 탐색하는 것이 어렵다는 것입니다. B+ 트리는 B-트리의 빠른 랜덤 액세스 속성을 유지하면서도 빠른 순차 액세스를 허용합니다.