b + 트리에 대량로드 데이터

Question

색인을 통해 삽입/삭제/검색을위한 모든 작업과 함께 b + 트리 색인을 작성했습니다. 거대한 데이터 세트의 삽입을 가속화하기 위해 대규모 데이터 세트를 실험 할 수 있도록 대량로드를 구현하고 싶습니다.

내가하려고 한 것은 데이터를 정렬하고 리프 수준에서 페이지를 채우기 시작하는 것입니다. 필요에 따라 키는 복사되거나 상위 레벨로 푸시됩니다. 나는 항상 색인의 개척지를 다양한 높이에서 추적한다. 예를 들어 내 인덱스의 높이가 3 (루트, 내부 노드와 리프 레벨을 포함하는 한 레벨) 인 경우, 메모리에 3 페이지를 유지하고 일단 가득 차거나 더 이상 데이터가 없으면 디스크.

문제는 모든 개별 노드의 페이지 제한을 유지하기 위해 각 페이지에 쓸 데이터의 양입니다. 이러한 제한은 here입니다. 노드로드 제한을 보장하기 위해 어떤 채우기 비율을 사용할 것인지를 결정하기위한 대량로드 구현 또는 좋은 전략 구현에 대한 세부 정보가있는 유용한 리소스를 찾을 수 없었습니다.

아이디어가 있으십니까?

Answer 1

질문 아래의 의견에서 마지막 페이지 (트리에서 상위 페이지로 간주하는 경우 마지막 페이지)가 최소 채우기 수에 도달하지 않을 수도 있다는 우려가 있음을 알 수 있습니다.

이러한 페이지의 수는 log2 (n) (트리의 높이)로 제한되므로 이론적 인 성능 보장에 영향을주지 않을 것으로 판단됩니다.

어쨌든 링크 된 보증은 정확성을 요구하지 않습니다. 그들은 실행 시간에 보장 된 경계에 충분합니다. 그들은 을 필요로하지 않습니다. 그러나 보장 된 실행 시간을 위해서입니다 (예 : 하나의 행을 가진 한 페이지를 b 트리의 끝에 추가하십시오 - 여전히 보장 된 실행 시간을 얻습니다).

실제 b-trees가 작동하는 방법을 알고 싶다면 마음에 드는 RDBMS를 살펴볼 수 있습니다 (SQL Server 사용자로서 SQL Server가 50 % 페이지 충만도 보증을 만족스럽게 실행하지 못한다는 것을 알고 있습니다. 실용적인 영향). 나는 당신이 이론적 인 관심이별로 중요하지 않은 것으로 취급된다는 것을 알게 될 것이라고 생각합니다.