탐색트리 구조

*B-트리(B+트리)
·인덱스 개념의 특수한 응용의 하나이다.
·데이터 레코트의 순차적 처리와 직접적 처리를 모두 지원하는 다단계 인덱스이다.
·인덱스를 구성하는 방식에 의하여 어느 정도의 효율적인 처리 보장한다.
*B-트리는 정의에 의해 균형이 잡혀있다. 루트에서 순차 세트에 이르는 거리 동일하다.
·효율적인 성능 보장한다.
·삽입 삭제 알고리즘은 복잡하다.
B*트리
B*-트리 또한 B-트리의 변형이다. B-트리가 각 노드가 적어도 반은 채워져야 하는데 반하여 노드의 2/3가 채워져야 한다. B*-트리는 빈번한 노드의 분열을 줄이려는 데에 목적이 있다. 어느 한 노드가 꽉 차게 되면 노드를 바로 분열시키는 대신에 재분배 원칙에 따라 꽉 찬 노드에서 키와 포인터를 꺼내서 다른 인접 형제 노드에 삽입하는 것이다.
B+ 트리
현재 사용되고 있는 C-ISAM 라이브러리도 B+ 트리로 구현이 되어 있었고, 다른 많은 file system이나 data base system에서도 B+ 트리가 사용되고 있다.
B+ 트리는 B 트리를 변형한 또 다른 구조이다. B+ 트리는 두 부분으로 나누어져 있는데 그하나는 leaf을 제외한 node로 이루어진 index부분이고 다른 하나는 leaf node로 구성된 순차 자료부분이다 모든 키값은 순차 자료부분 즉 leaf node에 키값의 asending으로 나열되어 있다. B 트리에 있는 키값을 사용하여 구성한 B+ 트리이다. index의 node에 있는 키값은 leaf에 있는 키값을 신속하게 직접 찾아 갈 수 있도록 하는 목적으로만 존재한다. 즉 모든 키값은 leaf에 나열되고 index 부분에 있는 키값도 다시 leaf에 나타나야 한다. B 트리와 구별되는 B+ 트리의 또 다른 특징은 모든 leaf node가 순차적 순서로 linked list를 구성하고 있다는 점이다.