b+트리 예제

다음은 최소 도 3의 B-트리 예제입니다. 실제 B-트리에서 최소 도값은 3보다 훨씬 큽니다. B-tree에서 내부(리프가 아닌) 노드는 미리 정의된 일부 범위 내에 가변수의 자식 노드를 가질 수 있습니다. 데이터가 노드에서 삽입되거나 제거되면 자식 노드 수가 변경됩니다. 미리 정의된 범위를 유지하기 위해 내부 노드가 결합되거나 분할될 수 있습니다. 하위 노드의 범위가 허용되므로 B-트리는 다른 자체 균형 검색 트리만큼 자주 재조정할 필요는 없지만 노드가 완전히 가득 차 있지 않으므로 일부 공간을 낭비할 수 있습니다. 하위 노드 수의 하한과 상한은 일반적으로 특정 구현에 대해 고정됩니다. 예를 들어 2-3 B-트리(단순히 2-3 트리라고도 함)에서 각 내부 노드에는 2개 또는 3개의 하위 노드만 있을 수 있습니다. 예제를 통해 요소를 삽입할 때 B 트리가 어떻게 커지는지 살펴보겠습니다. 일을 간단하게 하기 위해 트리는 3순서가 됩니다.

즉, 일반적으로 정렬 및 검색 알고리즘은 순서 표기명으로 수행해야 하는 비교 작업의 수를 특징으로 합니다. 예를 들어 N 레코드가 있는 정렬된 테이블의 이진 검색은 대략 로그2 N에서 비교할 수 있습니다. 테이블에 1,000,000개의 레코드가 있는 경우 특정 레코드는 최다 20개의 비교와 함께 위치할 수 있습니다. 인덱스를 사용하면 크게 개선할 수 있습니다. 위의 예에서 초기 디스크 읽기는 검색 범위를 2배 로 좁혀 두 배로 좁혀두었다. 각 디스크 블록의 첫 번째 레코드를 포함하는 보조 인덱스를 만들어 크게 개선할 수 있습니다(스파스 인덱스라고도 함). 이 보조 인덱스는 원래 데이터베이스 크기의 1%이지만 더 빨리 검색할 수 있습니다. 보조 인덱스에서 항목을 찾으면 주 데이터베이스에서 검색할 블록을 알 수 있습니다.

보조 인덱스를 검색한 후 한 번 더 디스크 읽기비용으로 주 데이터베이스의 한 블록만 검색해야 합니다. 인덱스는 10,000개의 항목을 보유하므로 가장 많은 14개의 비교가 수행됩니다.