B+-Tree Extensions

상위 문서: Indexing

개요

해당 문서에서는 B⁺-트리 구조의 여러가지 활용과 확장에 대해 다룬다.

B⁺-Tree File Organization

인덱스-순차 파일(index-sequential file) 구성의 문제는 파일이 커짐에 따라 성능이 저하된다는 것이다. 파일이 커지며넛 더 많은 인덱스 항목들과 실제 레코드들이 순서에 어긋나게 저장되고 오버플로우 블록(overflow block)에 저장되기 때문이다. 이러한 문제는 파일에 B⁺-트리 인덱스를 사용하여 해결할 수 있다.

파일:B+-tree file organization.png

Figure 1. B⁺-tree file organization

또한 실제 레코드가 저장됨에 따라 성능이 저하되는 문제는, B⁺-트리의 leaf 노드 레벨을 실제 레코드를 포함하는 블록들을 저장하는 용도로 사용하여 해결할 수 있다. 즉, B⁺-트리 구조를 단순한 인덱스가 아닐, 파일 내의 레코드들을 정리하는 도구로 사용하는 것이다. B⁺-트리 file organization에서는 트리의 leaf 노드들이 레코드 자체를 저장하며, 레코드에 대한 포인터를 저장하지 않는다. 이는 figure 1에 잘 나타나 있다.

레코드는 보통 포인터보다 그 크기가 크므로, leaf 노드에 저장할 수 있는 레코드의 수는 non-leaf 노드에 저장할 수 있는 포인터의 수보다 작다. 그럼에도 각각의 leaf 노드들은 최소 절반 이상은 차있어야 한다. B⁺-트리 file organization에서의 레코드 삽입/삭제는 B⁺-트리 인덱스에서 항목을 삽입하고 삭제하는 방식과 동일하다.

주어진 키 값 v를 가진 레코드를 삽입할 때, 시스템은 트리 내에서 v보다 작거나 같은 가장 큰 키를 찾아 해당 레코드를 저장할 블록을 찾는다. 만약 해당 블록에 레코드를 저장할 충분한 공간이 있다면, 시스템은 그 블록에 레코드를 저장한다. 그렇지 않다면, 일반적인 B⁺-트리 구조에서의 삽입처럼 시스템은 그 블록을 두 개로 나누고, 레코드들을 B⁺-트리에서의 키 순서에 따라 재분배하여 새로운 레코드를 위한 공간을 만든다. 이 분할은 재귀적으로 상위 노드에도 적용된다.

레코드를 삭제할 떄는, 시스템은 해당 레코드를 포함하고 있는 블록에서 그것을 제거한다. 이로 인해 해당 블록이 절반 이하로 점유된다면, 해당 블록의 레코드들을 인접한 블록의 레코드들과 재분배한다. 시스템은 B⁺-트리의 non-leaf 노드들도 일반적인 방식대로 업데이트한다.