B+Tree 알고리즘이란?

■ 실제로 가장 널리 활용되는 구조

 

■ 인덱스 구조와 시퀀스셋(data node set)으로 구성됨.

 

※ 인덱스 구조(Index)

• 각 노드가 record 대신 key값만 저장된 B-tree 구조
• 노드의 key값은 데이터 노드로 찾아가는데 이용하는 navigation에 이용
• B-tree의 요구와 조건은 모두 충족시켜야함.

※ 시퀀스셋(data node set)

• 데이터 노드들의 연결리스트로 구성됨.
• 노드는 데이터 즉 record들을 가짐. (모든 레코드가 저장됨.)
• 모든 record는 key값 순서로 정렬되어 있음.

▶인덱스 구조의 루트 노드를 제외한 모든 노드들은 "at least half full(절반 이상)" 조건을 만족함.

(단, 초기 상황은 예외)

 

※ B+tree의 장점

• 범위 탐색(Range Search)가 가능
•     (1) leaf 노드들끼리 연결리스트로 구성되어 있어 순차적인 범위 탐색에 유리.
•     (2) 범위 탐색은 먼저 시작하는 key 값을 스캔하여 해당 leaf노드를 찾은 다음 leaf 노드만을 따라가면서 검색.
• 인덱스 구조의 노드들은 branching factor(=capacity order)를 크게 할 수 있음.
•     (1) 이유: record의 key값만 저장하므로.
•     (2) 결론: 트리의 height가 낮아져 빠른 검색이 가능함.

---

※ B+tree node 타입 선언

 

typedef struct idxnode* type_ptr_idxnode;

typedef struct datanode* type_ptr_datanode;

 

typedef struct idxnode {   // 인덱스 노드

    type_key key[2*d1];

    type_ptr_idxnode ptri[2*d1 + 1];

    type_ptr_datanode ptrd[2*d1 + 1];

    int fill_cnt;

} type_idx_node;

 

typedef struct datanode {   // 데이터 노드

    type_rec rec[2*d2];

    type_ptr_datanode link;

    int fill_cnt;

} type_data_node;