이해하기 전에 B 트리 그리고 B+ 트리 차이점이 있으므로 B 트리와 B+ 트리를 별도로 알아야 합니다.

B 트리란 무엇인가?

B 트리 는 자체 균형 트리이며, m이 트리의 순서를 정의하는 m-way 트리입니다. 비트리 의 일반화이다 이진 검색 트리 노드는 값에 따라 둘 이상의 키와 둘 이상의 하위를 가질 수 있습니다. 중 . B 트리에서는 왼쪽 하위 트리의 값이 낮고 오른쪽 하위 트리의 값이 높은 정렬된 순서로 데이터가 지정됩니다.

캣 팀프 무게

B 트리의 속성

B 트리의 속성은 다음과 같습니다.

• B 트리에서는 모든 리프 노드가 동일한 수준에 있어야 하지만 이진 트리의 경우 리프 노드는 서로 다른 수준에 있을 수 있습니다.

예를 통해 이 속성을 이해해 보겠습니다.

위 트리에서 모든 리프 노드는 동일한 레벨에 있지 않지만 최대 2개의 자식을 갖습니다. 그러므로 위의 트리는 다음과 같다고 말할 수 있다. 이진 트리 하지만 B 트리는 아닙니다.

• Btree의 차수가 m인 경우 각 노드는 최대 중 최소 자식의 경우 리프 노드에는 자식이 없고 루트 노드에는 자식이 두 개 있으며 내부 노드의 상한은 m/2입니다.
• 각 노드는 최대(m-1)개의 키를 가질 수 있습니다. 예를 들어 m 값이 5이면 키의 최대값은 4입니다.
• 루트 노드에는 최소 1개의 키가 있는 반면, 루트 노드를 제외한 다른 모든 노드에는 (한계 m/2 - - 1) 최소 키가 있습니다.
• B 트리에 삽입을 수행하면 노드는 항상 리프 노드에 삽입됩니다.

1부터 10까지의 값을 삽입하여 3차 B 트리를 생성한다고 가정합니다.

1 단계: 먼저 아래와 같이 1개의 값을 가진 노드를 생성합니다.

2 단계: 다음 요소는 2이며, 아래와 같이 1 뒤에 옵니다.

3단계: 다음 요소는 3이며, 아래와 같이 2 뒤에 삽입됩니다.

각 노드는 최대 2개의 키를 가질 수 있다는 것을 알고 있으므로 이 노드를 중간 요소를 통해 분할합니다. 중간 요소는 2이므로 상위 요소로 이동합니다. 노드 2에는 부모가 없으므로 아래와 같이 루트 노드가 됩니다.

4단계: 다음 요소는 4입니다. 4는 2와 3보다 크므로 아래와 같이 3 뒤에 추가됩니다.

5단계: 다음 요소는 5입니다. 5는 2, 3, 4보다 크므로 아래와 같이 4 뒤에 추가됩니다.

각 노드는 최대 2개의 키를 가질 수 있다는 것을 알고 있으므로 이 노드를 중간 요소를 통해 분할합니다. 중간 요소는 4이므로 상위 요소로 이동합니다. 상위는 노드 2입니다. 따라서 아래와 같이 2 뒤에 4가 추가됩니다.

6단계: 다음 요소는 6입니다. 6은 2, 4, 5보다 크므로 아래와 같이 6이 5 뒤에 옵니다.

7단계: 다음 요소는 7입니다. 7은 2, 4, 5, 6보다 크므로 아래와 같이 6 뒤에 7이 옵니다.

각 노드는 최대 2개의 키를 가질 수 있다는 것을 알고 있으므로 이 노드를 중간 요소를 통해 분할합니다. 중간 요소는 6이므로 아래와 같이 상위 요소로 이동합니다.

그러나 노드는 최대 2개의 키를 가질 수 있으므로 4 뒤에 6을 추가할 수 없으므로 이 노드를 중간 요소를 통해 분할합니다. 중간 요소는 4이므로 상위 요소로 이동합니다. 노드 4에는 상위 노드가 없으므로 노드 4는 아래와 같이 루트 노드가 됩니다.

B+ 트리란 무엇입니까?

그만큼 B+ 트리 나무의 뿌리에서 잎까지의 모든 경로의 길이가 동일하기 때문에 고급 자체 균형 트리라고도 합니다. 여기서 길이가 동일하다는 것은 모든 리프 노드가 동일한 수준에서 발생한다는 것을 의미합니다. 리프 노드 중 일부는 세 번째 수준에서 발생하고 일부는 두 번째 수준에서 발생하는 일은 발생하지 않습니다.

B+ 트리 인덱스는 다중 레벨 인덱스로 간주되지만 B+ 트리 구조는 다중 레벨 인덱스 순차 파일과 유사하지 않습니다.

B+ 트리를 사용하는 이유는 무엇입니까?

B+ 트리는 B+ 트리 인덱스 구조를 이용하여 인덱스 방식으로 레코드를 저장함으로써 레코드를 매우 효율적으로 저장하는 데 사용됩니다. 다중 레벨 인덱싱으로 인해 데이터 액세스가 더 빠르고 쉬워졌습니다.

B+ 트리 노드 구조

B+ 트리의 노드 구조에는 아래 그림에 표시된 포인터와 키 값이 포함되어 있습니다.

위의 B+ 트리 노드 구조에서 볼 수 있듯이 n-1개의 키 값(k₁k에게_n-1) 및 n 포인터(p₁맨 위_N).

노드에 배치된 검색 키 값은 정렬된 순서로 유지됩니다. 따라서 만약 내가나제이.

다양한 유형의 노드에 대한 제약

'b'를 B+ 트리의 순서로 둡니다.

비리프 노드

우분투 빌드 필수사항

'm'이 노드의 자식 수를 나타낸다고 가정하면 트리의 순서와 자식 수 간의 관계는 다음과 같이 나타낼 수 있습니다.

k가 검색 키 값을 나타낸다고 하자. 트리의 순서와 검색 키의 관계는 다음과 같이 나타낼 수 있습니다.

포인터의 개수는 검색 키 값에 1을 더한 것과 동일하므로 수학적으로 다음과 같이 작성할 수 있습니다.

포인터(또는 하위) 수 = 검색 키 수 + 1

따라서 최대 포인터 수는 'b'이고 최소 포인터 수는 b/2의 천장 함수가 됩니다.

리프 노드

리프 노드(leaf node)는 B+ 트리의 마지막 레벨에 발생하는 노드로, 각 리프 노드는 하나의 포인터만을 사용하여 서로 연결함으로써 리프 레벨에서 순차 접근을 제공한다.

리프 노드에서 최대 자식 수는 다음과 같습니다.

최대 검색 키 수는 다음과 같습니다.

루트 노드

루트 노드의 경우 최대 자식 수는 다음과 같습니다. b

최소 어린이 수는 2명입니다.

B+ 트리의 특별한 경우

사례 1: 루트 노드가 트리의 유일한 노드인 경우. 이 경우 루트 노드는 리프 노드가 됩니다.

이 경우 최대 자식 개수는 1, 즉 루트 노드 자체이고, 최소 자식 개수는 b-1로 리프 노드와 동일하다.

B+ 트리의 리프 노드 표현

위 그림에서는 '.' 포인터를 나타내고 10, 20, 30은 키 값입니다. 포인터에는 위 그림과 같이 키 값이 저장되는 주소가 포함되어 있습니다.

B+ 트리의 예

위 그림에서 노드에는 9, 16, 25의 세 가지 키 값이 포함되어 있습니다. 9 앞에 나타나는 포인터에는 k로 표시되는 9보다 작은 키 값이 포함되어 있습니다._나. 16 앞에 나타나는 포인터에는 kj로 표시되는 9보다 크거나 같고 16보다 작은 키 값이 포함되어 있습니다. 25 앞에 나타나는 포인터에는 k로 표시되는 16보다 크거나 같고 25보다 작은 키 값이 포함되어 있습니다._N.

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

B 트리와 B+ 트리의 차이점은 다음과 같습니다.