C ++의 B 트리 및 B + 트리 데이터 구조

b tree b tree data structure c

이 C ++ 자습서에서는 B 트리 및 B + 트리 데이터 구조를 설명합니다. 전체 데이터를 메인 메모리에 저장할 수 없을 때 디스크에 데이터를 저장하는 데 사용됩니다.

B- 트리는 자체 균형이 조정 된 트리이자 디스크 액세스에 사용되는 특수한 m-way 트리입니다.

저장할 데이터의 양이 너무 많으면 전체 데이터를 메인 메모리에 저장할 수 없습니다. 따라서 데이터를 디스크에 저장합니다. 디스크에서의 데이터 액세스는 주 메모리 액세스와 비교할 때 더 많은 시간이 걸립니다.

디스크에 저장된 데이터의 키 수가 매우 많을 때 데이터는 일반적으로 블록 형태로 액세스됩니다. 이 블록에 액세스하는 시간은 나무의 높이에 정비례합니다.

=> Absolute C ++ 교육 시리즈를 보려면 여기를 클릭하십시오.

학습 내용 :

• C ++의 B- 트리
  • B-Tree의 기본 동작
    • # 1) 검색
    • # 2) 삽입
    • # 3) 삭제
  • B 트리의 응용
• C ++의 B + 트리
  • B + 트리의 장점
• B- 트리와 B + 트리의 차이점
• 결론
  • 추천 도서

C ++의 B- 트리

B-Tree는 평평한 나무입니다. 즉 B 나무의 높이가 최소로 유지됩니다. 대신 B- 트리의 각 노드에 많은 키가 배치됩니다. B- 트리의 높이를 최소로 유지함으로써 AVL 트리와 같은 다른 균형 잡힌 트리에 비해 액세스가 더 빠릅니다.

일반적인 B- 트리는 다음과 같습니다.

실행 가능한 jar 파일을 실행하는 방법

일반적으로 B-tree의 노드 크기는 블록 크기와 동일하게 유지됩니다.

다음은 B-Tree의 속성 중 일부입니다.

• B- 트리의 모든 잎은 같은 수준에 있습니다.
• m 차의 B- 트리는 최대 m-1 개의 키와 m 개의 자식을 가질 수 있습니다.
• B- 트리의 모든 노드에는 최대 m 개의 자식이 있습니다.
• 루트 노드에는 두 개 이상의 노드가 있어야합니다.
• 루트 노드와 리프 노드를 제외한 모든 노드는 m / 2 자식을 포함합니다.

다음으로 B-tree의 기본 작업에 대해 설명합니다.

B-Tree의 기본 동작

다음은 B-Tree의 기본 작업 중 일부입니다.

# 1) 검색

B 트리 검색은 BST 검색과 유사합니다. 위의 트리에서 항목 3을 찾으려면 다음과 같이 진행합니다.

• 3을 루트 요소와 비교하십시오. 여기, 3<6 and 3 <15. So we proceed to the left subtree.
• 왼쪽 하위 트리에서 3과 4를 비교합니다. 3으로<4, we proceed to the left subtree of node 4.
• 다음 노드에는 2와 3의 키가 있습니다. 3> 2, 3 = 3입니다. 그래서 우리는이 노드에서 키를 찾았습니다. 찾은 위치로 돌아갑니다.

B 트리에서 검색하는 것은 트리의 높이에 따라 다릅니다. 일반적으로 주어진 항목을 검색하는 데 O (log n) 시간이 걸립니다.

# 2) 삽입

B 트리에 새 항목을 삽입하는 작업은 리프 노드 수준에서 수행됩니다.

다음은 B 트리에 새 항목을 삽입하는 일련의 단계 (알고리즘)입니다.

• B 트리를 횡단하여 항목을 삽입 할 리프 노드에서 위치를 찾습니다.
• 리프 노드에 키가 포함 된 경우
• 그렇지 않으면 리프 노드 키 = m-1이면 다음과 같습니다.
  • 점점 더 많은 항목에 새 항목을 삽입하십시오.
  • 노드의 중앙값을 취하고 노드를 두 개의 노드로 분할합니다.
  • 중앙값을 상위 노드로 푸시합니다.
  • 부모 노드 키 = m-1이면 부모 노드에 대해서도 위 단계를 반복합니다. 이것은 적절한 리프 노드를 찾을 때까지 수행됩니다.
• 마지막으로 요소를 삽입하십시오.

다음과 같이 B 트리에 삽입하는 방법을 시연했습니다.

아래에 표시된 트리에 항목 70을 삽입하겠습니다.

Windows 10 기본 게이트웨이를 사용할 수 없음

주어진 트리는 최소 차수 'm'= 3입니다. 따라서 각 노드는 내부에 2 * m -1 = 5 개의 키를 수용 할 수 있습니다.

이제 항목 70을 삽입합니다. 노드에 5 개의 키를 가질 수 있으므로 요소 70을 루트 요소 30과 비교합니다. 70> 30이므로 오른쪽 하위 트리에 항목 70을 삽입합니다.

오른쪽 하위 트리에는 40, 50, 60 키가있는 노드가 있습니다. 각 노드에는 5 개의 키가있을 수 있으므로이 노드 자체에 항목 70을 삽입합니다.

삽입 후 B-Tree는 다음과 같이 보입니다.

# 3) 삭제

삽입과 마찬가지로 키 삭제도 리프 노드 수준에서 수행됩니다. 그러나 삽입과 달리 삭제는 더 복잡합니다. 삭제할 키는 리프 노드 또는 내부 노드 일 수 있습니다.

키를 삭제하려면 아래 단계 (알고리즘)를 따릅니다.

1. 리프 노드를 찾습니다.

두. 노드의 키 수가> m / 2 인 경우 노드에서 주어진 키를 삭제합니다.

삼. 리프 노드에 m / 2 키가없는 경우 B 트리를 유지하기 위해 오른쪽 또는 왼쪽 하위 트리에서 키를 가져 와서 키를 완성해야합니다.

다음 단계를 따릅니다.

• 왼쪽 하위 트리에 m / 2 요소가 포함 된 경우 가장 큰 요소를 부모 노드로 푸시 한 다음 중간 요소를 키가 삭제 된 위치로 이동합니다.
• 오른쪽 하위 트리에 m / 2 요소가 포함 된 경우 가장 작은 요소를 부모 노드로 푸시 한 다음 중간 요소를 키가 삭제 된 위치로 이동합니다.

네. 노드에 m / 2 개의 노드가 없으면 위의 단계를 수행 할 수 없으므로 두 개의 리프 노드와 부모 노드의 중간 요소를 결합하여 새 리프 노드를 만듭니다.

5. 부모에 m / 2 노드가 없으면 해당 부모 노드에 대해 위의 단계를 반복합니다. 이 단계는 균형 잡힌 B 트리를 얻을 때까지 반복됩니다.

아래는 B 트리에서 노드를 삭제하는 그림입니다.

다음 B 트리를 다시 고려하십시오.

B 트리에서 키 60을 삭제한다고 가정 해 보겠습니다. B 트리를 확인하면 삭제할 키가 리프 노드에 있음을 알 수 있습니다. 이 리프 노드에서 키 60을 삭제합니다.

이제 트리는 아래와 같이 보일 것입니다.

키 60을 삭제 한 후 B 트리 리프 노드가 필요한 속성을 충족하고 B 트리를 더 이상 수정할 필요가 없음을 알 수 있습니다.

그러나 키 20을 삭제해야한다면 키 10 만 왼쪽 리프 노드에 남아있을 것입니다. 이 경우 루트 30을 리프 노드로 이동하고 키 40을 루트로 이동해야합니다.

따라서 B 트리에서 키를 삭제할 때주의해야하며 B 트리의 속성을 위반하지 않아야합니다.

B 트리에서 순회

B 트리의 순회도 BST의 순회 순회와 유사합니다. 왼쪽에서 재귀 적으로 시작한 다음 루트로 이동하여 왼쪽 하위 트리를 향해 진행합니다.

B 트리의 응용

• B 트리는 디스크의 대용량 데이터베이스에 저장된 데이터에 액세스하는 데 시간이 많이 걸리므로 특히 대용량 데이터베이스의 데이터를 인덱싱하는 데 사용됩니다.
• 더 큰 정렬되지 않은 데이터 세트에서 데이터를 검색하는 데는 많은 시간이 걸리지 만 B 트리를 사용하는 인덱싱을 사용하면 상당히 개선 될 수 있습니다.

C ++의 B + 트리

B + 트리는 B 트리의 확장입니다. B + 트리와 B 트리의 차이점은 B 트리에서는 키와 레코드가 내부 노드와 리프 노드로 저장 될 수있는 반면, B + 트리에서는 레코드가 리프 노드로 저장되고 키가 내부 노드에만 저장된다는 것입니다.

레코드는 연결 목록 방식으로 서로 연결됩니다. 이 배열은 B + 트리 검색을 더 빠르고 효율적으로 만듭니다. B + 트리의 내부 노드를 인덱스 노드라고합니다.

B + 트리에는 내부 노드 용과 리프 또는 외부 노드 용의 두 가지 순서가 있습니다.

B + 트리의 예는 아래와 같습니다.

연결 목록 C ++는 무엇입니까

B + 트리는 B- 트리의 확장이므로 B- 트리 주제에서 논의한 기본 작업은 여전히 ​​유지됩니다.

삽입 및 삭제하는 동안 B + Trees의 기본 속성은 그대로 유지해야합니다. 그러나 B + 트리의 삭제 작업은 데이터가 리프 노드에만 저장되고 항상 리프 노드에서 삭제되므로 비교적 쉽습니다.

B + 트리의 장점

• 동일한 수의 디스크 액세스에서 레코드를 가져올 수 있습니다.
• B 트리에 비해 B + 트리의 높이는 더 적고 균형을 유지합니다.
• 색인 생성을 위해 키를 사용합니다.
• B + 트리의 데이터는 리프 노드가 연결 목록에 정렬되어 있으므로 순차적으로 또는 직접 액세스 할 수 있습니다.
• 데이터가 리프 노드에만 저장되고 연결 목록으로 저장되므로 검색이 더 빠릅니다.

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

결론

이 튜토리얼에서는 B- 트리와 B + 트리에 대해 자세히 설명했습니다. 이 두 데이터 구조는 매우 많은 양의 데이터가 있고 전체 데이터를 메인 메모리에 저장할 수 없을 때 사용됩니다. 따라서 디스크에 데이터를 저장하기 위해 B- 트리와 B + 트리를 사용합니다.

B- 트리 검색은 데이터가 내부 노드와 리프 노드에 저장되기 때문에 약간 느립니다. B + 트리는 B- 트리의 확장이며 여기에있는 데이터는 리프 노드에만 저장됩니다. 이 요인으로 인해 B + 트리에서 검색하는 것이 더 빠르고 효율적입니다.

=> 전체 C ++ 자습서 목록을 보려면 여기를 방문하십시오.

추천 도서

• C ++의 AVL 트리 및 힙 데이터 구조
• 그림이있는 C ++의 연결된 목록 데이터 구조
• 그림이있는 C ++의 큐 데이터 구조
• 일러스트레이션이있는 C ++의 스택 데이터 구조
• 그림이있는 C ++의 순환 연결 목록 데이터 구조
• C ++의 데이터 구조 소개
• C ++의 우선 순위 큐 데이터 구조 (그림 포함)
• 그림이있는 C ++의 이중 연결 목록 데이터 구조