B-tree 알고리즘이란?

다방향 탐색 트리를 이르는 말. 데이터 레코드의 순차적 처리와 직접적 처리를 모두 지원하는 다단계 트리 구조라고 정의되어 있다.

 

※ B-tree의 특징

•  삽입 및 삭제 알고리즘은 Tree가 Balance 되는 것을 보장한다. 즉, 삽입과 삭제가 일어나도 B-tree의 기본 구조를 지켜서 진행된다. (Balance : 모든 leaf 노드가 (거의) 같은 level에 속해야 한다.)
• Branching factor가 2 이상의 큰 값일 수 있다. ( -> 빠른 탐색 시간을 보장한다.)
• m-원 탐색 트리 성질을 만족해야 한다. (1. 탐색의 효율성을 증가  2. record들을 정렬된 순서로 출력한다.)
• 데이터의 저장 및 탐색이 가장 많이 이용되는 데이터 구조 중의 하나이다.

 

※B-tree의 정의(Definition)

• capacity order = d라는 값으로 구조가 정해진다.
• 각 노드는 2d개의 record와 2d+1개의 pointer를 저장하는 공간을 가진다.
• m-원 탐색 트리여야 한다. (m =2d+1)
• 루트 노드를 제외한 모든 노드는 d개 이상의 record (최대 record 수의 Half 이상)를 가져야 한다. (단, 루트노드는 1개 이상의 record를 가진다.)
• 모든 leaf 노드들은 같은 (depth) level에 존재해야만 한다. (balance 보장)

★ m원 탐색 트리

• 각 노드는 최대 m-1개의 record, m개의 pointer를 가진다.
• 이것들은 p0, rec0, p1, rec1, ........ , rec (m-2), p(m-1)의 순서로 배열된다.
• 각 노드는 처음부터 빈 곳 없이 채워져야 하며 마지막은 pointer이어야 한다.
• 임의의 노드에서 r(i)의 key는 p(i) sub-tree 내의 record의 key보다 크고, p(i+1) sub-트리의 모든 record의 key보다 작다. 모든 가능한 정수 i 에 대해 이 사실이 성립해야만 한다.
• ex) binary search tree(BTS)는 2-원 탐색트리이다.