01. 메트릭 검색 트리
– 트리의 노드가 m개 이상의 분기를 가질 수 없는 검색 트리.
→ 동일한 수의 노드 m은 이진 트리보다 높이가 낮은 트리입니다.
– 이진탐색트리의 발전된 형태이다.
– 검색 트리 구체화(키 값으로 정렬)그러나 2명 이상(m명 이하)의 자녀를 가질 수 있습니다.
(2) 다중 경로 검색 트리에서 검색
– 일반적으로 노드의 가지(하위 트리) 수가 많을수록 최대 검색 길이가 짧아집니다(트리의 깊이가 작기 때문).
02. 비트리
1. 배경
– m-way 검색 트리는 하위 트리입니다. 균형특별히 제한되지 않음
→B-트리는 각 노드가 많은 자식을 갖도록 하여 트리의 높이를 줄입니다.전체적으로 균형을 유지하기 위해검색 성능을 더욱 향상시킬 수 있습니다.
m-way 검색 트리를 개선한 B-트리는 인덱스 구조를 구현하는 데 가장 일반적으로 사용됩니다.
2) B-트리
차수가 m인 B-트리의 검색 경로 길이는 이상적인 m-way 검색 트리보다 길 수 있지만,
키 값 삽입/삭제 시 B-Tree 잡기 쉬운
3) B-트리 조건
– 루트 노드와 리프 노드를 제외한 트리의 각 노드는 적어도 (m/2)개의 하위 트리가 있음
– 트리의 루트에는 적어도 두 개의 하위 트리가 있습니다.
– 트리의 모든 리프 노드는 동일한 수준에 있습니다.
4) B-tree에 키를 삽입하는 알고리즘
(1) 노드의 키 값을 왼쪽에서 오른쪽으로 찾아 삽입할 위치를 찾습니다(B-tree에서 모든 노드는 리프 노드부터 삽입됨).
(2) 노드에 공백이 있으면 삽입 후 종료
(3) 노드가 가득 차면 노드를 둘로 나누고 키와 포인터의 절반을 새 노드에 할당
– 리프 노드의 키 값과 삽입 노드의 키 값 사이의 중앙값 선택
– 키 값이 선택된 중앙값보다 작은 것은 외부 노드에, 선택된 중앙값보다 큰 것은 오른쪽 노드에 배치됩니다.
– 중간 값을 가진 노드의 키 값과 포인터를 부모 노드에 삽입합니다. 부모 노드가 루트 노드인 경우 두 노드를 가리키도록 변경합니다(자식 노드가 됨).
5) B-tree에서 키 삭제(리프 노드에서 삭제) 알고리즘
(1) 삭제할 키 값이 포함된 노드를 찾습니다.
(2) 노드에서 키 값 삭제
(3) 필요한 경우 재정렬합니다.
6) B-tree에서 키를 삭제하는 알고리즘(내부 노드 삭제)
– 내부노드의 키값은 하위노드의 기준값(중간값)이므로 삭제할 때 대체할 수 있는 일치하는 값을 찾아야 한다.
모두 리프 노드에 위치한 외부 하위 트리의 가장 큰 키 값 또는 오른쪽 하위 트리의 가장 작은 키 값으로 교체
(1) 삭제된 위치로 이동할 키 값을 선택하여 해당 리프 노드에서 삭제하고 현재 키 값의 삭제된 위치로 값을 교체
(2) 키가 삭제되는 리프 노드에 기준 값으로 대체할 키 값이 지정된 개수가 없으면 트리를 재정렬한다.
03. B*, B+ 트리
1) B* 트리 정의
– 노드의 2/3 이상이 채워진 B-tree
– 노드가 가득 차면 분할하지 말고 키와 포인터를 다른 형제 노드로 이동하십시오.
– 삽입/삭제 시 발생하는 노드 분리를 줄이기 위한 설계
2) B+ 나무 정당성
– 검색 트리로 구성되어 있어 매우 빠른 검색이 가능하나 전체 데이터를 순차적으로 처리하기 번거로움
→ 매번 왼쪽인지 오른쪽인지 비교하여 다음 노드를 찾으면서 처리해야 함.
– B+ 트리는 색인 순차 파일을 만드는 데 사용됩니다.
– B-트리와 마찬가지로 각 노드의 키는 적어도 1/2이 차 있어야 합니다.
– 모든 키 값은 리프 노드에 있으며 리프 노드만 키 값에 해당하는 실제 데이터(파일 내용)의 주소를 가집니다.
→ 리프 노드에 도달하면 직접 검색이 종료됩니다.