B-Tree에서 대량로드 알고리즘이 있습니까?

Question

b + 트리에 대량로드가 있다는 것을 알고 있습니다. B-Tree에서 대량로드를위한 알고리즘이 있는지 알고 싶었습니다. 예를 들어 주어진 데이터 배열은 B-Tree를 만드는 가장 좋은 방법입니다.

Answer 1

사실 대답은 '예'입니다.

B + 트리와 일반 B- 트리의 주된 차이점은 값이 실제로는 이전의 나뭇잎에 저장되는 반면 나중에는 모든 노드에서 값을 찾을 것이라는 점입니다. 따라서 B + - 트리를 사용하면 거의 연속적인 방식으로 데이터를 저장할 수 있습니다. 각 리프에는 전체 정렬 된 데이터의 연속 슬라이스가 있습니다. B- 트리에서는 내부 노드가 여러 요소를 포함하지만 인접하지는 않습니다. 전체 정렬 된 데이터 세트.

이 속성은 대량로드에 필수적입니다.이 프로세스는 이미 정렬 된 데이터 집합에서 B + 트리의 잎을 형성 할 배열로 절단하여 작동합니다. 따라서 B-tree의 경우 작동하지 않는 것처럼 보입니다.

내부 노드 요소를 그룹화하는 방식으로 데이터를 정렬 할 수 있으면 문제가 해결됩니다. 그렇게하기 위해서는 요소가 어떻게 그룹화되는지 미리 알아야합니다. 이것은 가능한 것으로 밝혀졌습니다.

노드의 최소 수의 자식을 (B- 트리 순서의 원래 정의와 일치하는) o (주문)이라고합시다. 우리는 루트 노드가 트리의 가장 높은 단계에 있고 잎이 가장 낮게 (단계 0) 있다고 생각합니다. 잘 균형 잡힌 나무의 경우, 모든 나뭇잎은 실제로 같은 단계에있게됩니다.

트리의 단계 k는 단계 k-1에서 적어도 o 개의 요소만큼 이격 된 요소를 그룹화합니다. 초기 정렬 후에는 스테이지 0을 구성하는 정렬 된 배열에서 요소를 추출하고 스테이지 1을 만들기 위해 다른 배열에 그룹화 한 다음 해당 배열로 스테이지 2의 새 배열로 다시 한 번 반복하고 프로세스를 반복해야합니다 가장 새로운 배열의 요소가 o보다 적어 질 때까지 루트 스테이지가됩니다.

빌드 각 노드 등을 하위 노드에 노드를 연결,

• 분할 o 요소의 배열의 각 단계
• 빌드 인덱스 배열 : 그때부터, 무대 세트에서 직접 트리를 구축 할 수 있습니다 해당 인덱스 배열 쌍 * 값 배열

결과 트리의 균형이 반드시 일치하지는 않습니다. 그것은 데이터 집합의 항목 수에 따라 다르며 o입니다. 더 나은 분산 트리를 갖기 위해 스테이지를 구축하는 데 사용되는 간격을 조정할 수 있어야합니다.

B 트리를 대량로드하는 데 필요한 모든 작업은 B + 트리의 작업보다 훨씬 지루하지만 가능합니다.