B+-Tree Extensions

상위 문서: Indexing

개요

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

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

Figure 1. B⁺-tree file organization

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

레코드는 보통 포인터보다 그 크기가 크므로, leaf 노드에 저장할 수 있는 레코드의 수는 non-leaf 노드에 저장할 수 있는 포인터의 수보다 작다. 그럼에도 각각의 leaf 노드들은 최소 절반 이상은 차있어야 한다.