분야
hwp(2) B-트리에서의 검색
(3) B-트리에서의 삽입
(4) B-트리에서의 삭제
(5) 인덱스된 실제 B-트리 소스코드
(6) 실행화면
(1) B-트리 특성
① B-트리는 공백이거나 높이가 1이상인 m-원 탐색 트리
② 루트와 리프를 제외한 내부 노드는 최소 (m/2), 최대 m개의 서브트리를 갖는다.
③ 루트는 자체가 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다.
④ 모든 리프는 같은 레벨에 있다.
B-트리는 항상 균형 상태를 유지하면서 키 값의 삽입이나 삭제 뒤에도 B-트리 정의에 명세된 성질이 유지해야 한다. 또한, 인덱스구조로 가장 효율적이다.
각 노드는 적어도 1/2은 키 값으로 채워져야 한다.
(2) B-트리에서의 검색
키 값을 검색하기 위해서 m-원 탐색 트리의 직접검색과 같은 과정.
먼저, 루트노드를 조사하고 작은키 값은 왼쪽으로 큰 키 값은 오른쪽으로 포인터가 이동한다. 리프노드에서의 검색은 순차 검색이된다.
B-트리 전체의 순차 검색은 키 값에 따라 트리의 각 노드를 중위 순회[inorder traversal(왼->위->오)]하면 된다. 한 노드의 다음 키를 접근하기 전에 그 키 왼편에 있는 서브트리를 순회한 뒤 노드의 키를 접근하고 다시 오른쪽 서브트리를 순회한다.
- 검색 알고리즘
searchBT(key)
// key : 키의 값
// x : 노드
// root : 루트 노드
// n : 노드에서의 키의 개수
x
