키 순차접근 및 B+ Tree

인덱스화된 순차 접근은 2가지 방법으로 이루어 집니다.

• Index 방식
• Sequential 방식

인덱스 방식은 키로 인덱스를 통한 직접 검색(Exact Search)를 수행합니다.

순차방식은 키의 순서대로 레코드들을 순차적으로 접근(Range Search) 합니다.

 

하지만, 기존의 단순 인덱스(Simple Index) 혹은 B-Tree는 순차접근을 위해서 중위순회(In-order Travers)를 요구하기 때문에 순차접근에 불리합니다. (제일 처음을 찾아서 내려온다음, 부모노드, 오른쪽 자식 노드, 다시 상위노드 ... 을 수행하기 때문에 많은 시간 소요)

 

이를 해결하기 위해 레코드 삽입, 삭제 후에도 키 순서대로 레코드들이 물리적으로 저장되는 집합체인 순차 집합(Sequential Set)을 사용합니다.

 

이 방법은 레코드들을 블록에 모아서 저장하며, 이 블록은 블록 간 선후 관계를 표현하는 연결필드가 포함되어 있습니다. 또한, 블록에서 레코드 삭제 시 Underflow가 발생할 수 있으며, Split 혹은 Redistribution을 수행합니다. 반대로 블록에서 레코드 삽입 시 Overflow가 발생할 수 있고 Split을 수행합니다.

 

이때, 고려할 점으로는 내부 단편화와 레코드들의 물리적 연속성이 있는데, 내부 단편화의 경우 재분배나 2-3 Split을 수행하고, 물리적 연속성은 블록 내부에서만 만족하게 됩니다.

 

블록의 크기는 메모리에 확보할 수 있는 버퍼의 개수를 고려하여 선택합니다. 2-3 Split을 수행할 경우, 메모리에 버퍼는 최소한 3개는 있어야 수행할 수 있습니다.

 

순차집합에 단순 인덱스를 추가할려면, 인덱스가 메모리에 적재되어야합니다. 이렇게 수행할 경우, 인덱스에 대한 이진탐색으로 레코드를 탐색합니다. 또한, 블록의 변경이 있을 경우 인덱스의 변경이 요구됩니다.

 

위 방법에서는 키를 사용했으나 분리자를 사용할 경우, 인덱스 내용에 키 사용이 불필요해지는 효과를 얻을 수 있습니다.

 

이렇게 만들어낸 순차집합을 통해 단순전위 B+ Tree(The Simple Prefix B+ Tree)를 사용합니다.

단순 전위란, 키 문자열의 가장 짧은 길이의 분리자 역할을 할 수 있는 앞부분을 분리자로 사용함을 의미합니다.

 

레코드의 삽입과 삭제는 순차집합에서 발생하며, 인덱스는 B-Tree로 표현하고 N개 분리자를 포함하는 노드는 N+1개의 자식노드를 참조합니다.

 

이 방법으로 순차탐색을 할 경우, Leaf Node가 다 연결되어 있는 구조이기 때문에 B-Tree 보다 순차탐색에서 유리합니다.

 

블록이 분리된 경우, 새로운 분리자가 생성되어 인덱스 집합에 삽입됩니다.

블록이 병합된 경우, 분리자는 인덱스 집합에서 삭제됩니다.

블록 내에서 레코드 재분배가 이루어 진경우 인덱스 집합의 분리자는 이동합니다.

 

가변 차수의 단순전위 B+ Tree의 구조는 다음과 같습니다.

• 각 인덱스 블록은 고정되지 않은개수의 분리자를 포함합니다.
• 가변자들의 수는 차수가 아닌 블록의 바이트 사이즈로 제한됩니다.
• 트리의 차수가 가변이기 때문에 분리, 병합, 재분배 등이 복잡합니다.

단순전위 B+ Tree가 아닌, 일반 B+ Tree는 분리자로 전위의 사용이 불필요하고, 분리자는 실제 키의 복사본을 사용한다는 차이점이 있습니다.

 

B-Tree와 B* Tree, The Simple Prefix B+ Tree의 공통된 특징으로는 다음과 같습니다.

• 페이징된 인덱스 구조를 사용합니다.
• Height - Balanced Tree 구조입니다.
• 바텀업 방식으로 트리가 생성됩니다.
• 2-3 Split이나 재분배를 통해 높은 공간 활용도를 보입니다.
• 가상 트리구조로 표현이 가능합니다.

여기서 가상 트리구조란, RAM에 루트에 가까운 것을 항상 저장해 두어 디스크에 거의 접근하지 않게끔 하여 트리 전체가 RAM에 있는듯한 효과를 말합니다. (앞선 포스트의 높이 기반 대체 기법, Virtual B-Tree)

 

B-Tree가 각 항목에 키와 연관된 정보를 포함하게끔 변형한 트리를 연관정보를 포함하는 B-Tree라고 합니다.

이 방법은, 깊이가 커지면서 탐색 시간이 커지지만, 연관정보를 포함하고 있어서 탐색에 성공하면 바로 끝나는 점이 있습니다.