B+ Tree

■ B+ 트리란

B트리에 인덱스를 추가했고,  리프노드들이 순차화일로 구성된다.

즉, 중간노드(인덱스세트)에 있는 값들이 리프노드(순차세트)에 다시 나타난다.(단지, 리프노드에 있는 키 값을 찾는 경로로만 사용)

■ m차 B+ 트리에서 if m=3, then 루트노드는 0개 혹은 2~3(m)개의 서브트리를 가진다.

■ 리프노드는 당연히 노드를 가지지 않고(-_-), 모든 내부 노드최소 m의 절반(m/2), 최대 m개의 서브트리를 가진다.


■ 삽입 시에는 B 트리와 유사하지만, 다른 점은 오버플로가 생겼을 때 중간 값을 부모 노드로 올려보내는데

분할되는 노드에도 그 중간 값이 남아 있다는 점이다.

■ 삭제 시에도 B 트리와 유사하다. 단, 삭제는 리프노드에서만 일어나고, 인덱스세트에 있는 값은 유지하여 분리 키값으로 사용한다.

분리 키값이란 데이터를 찾을 때 어느 방향으로 갈건지에 대한 방향지시등 같은 역할을 하는 값을 말한다.

■ 삭제 후에 언더플로가 일어나면(값의 개수가 m/2미만인 경우) 재분배를 해주어야하는데 

형제노드가 충분하면 바로 이동시키고 오버플로라면 분할시켜 언더플로 구역으로 나눠주면 된다.


■ 검색은 항상 순차세트인 리프노드까지 내려가야 종료된다. (실제주소를 얻으려면 -> 인덱스세트의 키 값은 단지 분리키값일 수 있으므로)

■ 인덱스노드(인덱스세트)는 레코드 포인터를 저장하지 않는다. -> 노드 내 공간이 절약 -> 트리 레벨이 낮아질 수 있음

■ 인덱스된 순차화일인 B+ 트리는 당연히 순차검색에 있어서 B 트리보다 효율적이다.

■ 직접, 순차처리를 모두 필요로 하는 응용에서 효율적인 방식이다.



'computer' 카테고리의 다른 글

인덱스된 순차 화일 (ISF, Indexed Sequential File) - 2  (0) 2012.05.26
B+ Tree  (0) 2012.05.26
인덱스된 순차 화일 (ISF, Indexed Sequential File) - 1  (0) 2012.05.26
c++ get() 함수, 개행문자 읽기  (0) 2012.05.07
신호.  (0) 2012.04.30
Modeling (모델링).  (0) 2012.04.30