탐색트리 구조

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