B* Tree와 Node Buffering

B* Tree는 2-3 Split 방식으로 운용됩니다. 2-3 Split은 재분배 우선 삽입일 때, split 시 각 노드는 1/2가 아닌 2/3이 찬 상태일때 수행합니다.

 

B* Tree는 다음으로 정의할 수 있습니다.

• 모든 노드는 최대 m개의 자손 노드를 가집니다.
• 루트 노드를 제외한 모든 노드는 최소 ceil((2m - 1) / 3) 개의 자손 노드를 가집니다.
• 루트 노드는 최소 2개의 자손 노드를 가집니다.
• 모든 단말 노드는 동일 레벨입니다.

2-3 Split을 사용한 B* Tree는 다음 2가지의 문제점을 가집니다.

1. 루트 노드는 이웃 노드가 없으므로 2-3 Split이 불가능 합니다.
2. 루트 노드는 2/3 이상의 자손 노드를 가질 수 없습니다.

1번째 문제의 경우 루트 노드 사이즈를 다른 노드들 보다 크게 허용하여 해결할 수 있지만, 루트 노드를 위한 루틴은 다른 노드와 다르게 되는 문제점을 가지고, 2번째 문제의 경우 루트 노드만 1-2 Split을 하여 해결할 수 있지만, 삭제나 재분배 시 프로시저들이 복잡해지는 문제가 있습니다.

 

노드들의 버퍼링 방법에는 다음 방법들이 있습니다.

• Virtual B-Tree
• LRU 대체 알고리즘
• 높이 기반 대체 기법
• 가변길이의 키 필드 사용

1번째인 가상 B-Tree는 루트 노드 뿐만 아니라 다른 노드들도 RAM에 적재하여 디스크 I/O 횟수를 줄이는 방법입니다.

 

2번째인 LRU 대체 알고리즘은 시간적 지역성(Temporal Locality)를 이용하여 가장 최근에도 사용된 적 없는 페이지를 대체하여 시간적 지역성이 높은 부분을 계속해서 메모리에 머물게 유지합니다.

 

3번째인 높이 기반 대체 기법은 루트 노드에 가까운 노드들을 버퍼에 지속적으로 보관하는 방법으로, 노드 레벨이 루트에 가까울수록 희생자로 선정되지 않는 방법입니다.

 

4번째인 가변길이의 키 필드를 사용하는 방법은 Overflow, Underflow의 조건이 차수가 아닌 노드의 바이트로 계산하여 사용하는 방법입니다.