m-원 탐색트리란 무엇인가?
B-트리를 배우기 전에 그 근본 개념이 되는 m-원 탐색트리에 대해 알아봅시다.
기존의 이진 탐색트리 에서 균형 이진 탐색트리인 AVL 트리의 경우 n 개의 노드에 대해서 깊이가 최소 logn에 가깝기 때문에, 실제 시스템에서 AVL 구조로 저장된 데이터에 접근하기 위해서는 만약 모든 노드가 다른 메모리 안에 들어 있다면 최악의 경우 logn번 만큼 메모리 혹은 디스크에 접근을 해야 했습니다.
이렇게 수 차례에 걸쳐 메모리 혹은 디스크에 접근하는 것은 치명적인 탐색 시간 상승을 야기했고, 이에 탐색 트리의 높이를 줄여 탐색시간을 줄이기 위한 많은 노력들이 있었고, 이를 위해서는 필수적으로 트리의 차수가 증가 해야 했습니다. m-원 탐색트리는 m개의 차수를 가지는 노드들로 구성된 트리이며, 실제로는 트리 노드들이 하나의 캐시 블록이나 디스크 블록을 체울 수 있는 가장 큰 차수를 사용하고 있습니다.
m-원 탐색트리의 정의는 다음과 같습니다.
m-원 탐색트리의 정의
m-원 탐색트리의 예시
B-트리란?
B-트리는 이러한 m-원 탐색트리의 일종이며 다음과 같이 정의됩니다.
차수가 m인 B-트리의 정의
B-트리의 예시
B-트리의 삽입
B-트리의 삭제
키가 x인 노드를 삭제하려고 할 때, x가 리프가 아닌 노드 z에서 발견될 경우, z에서 x가 차지하던 자리는 B-트리의 리프 노드로 부터 적당한 키로 채워진다. 가령 x가 그의 i번째 키라고 하면, E_i는 서브트리 A_i 내의 가장 작은 원소 혹은 서브트리 A_(i-1)의 가장 큰 원소로 채워질 수 있습니다. 여기서 삭제되는 리프노드 p에 대해 다음의 4가지 경우가 존재합니다.
CASE1
p 또한 루트노드인 경우
삭제 후 리프에 적어도 키가 하나 남아있다면 삭제 후 저장하고, 없다면 공백트리가 됩니다.
CASE2
삭제 후 p가 적어도 [m/2]-1 개의 원소를 가지고 있는 경우 즉, 최소 원소 개수가 만족되는 경우
그대로 삭제를 진행
CASE3 회전
p가 [m/2]-2개의 원소를 가지며, 인접한 형제노드 q가 적어도 [m/2]개 원소를 가지는 경우. 즉, p가 삭제 후 최소 키보다 적은 키를 가지고 있고 형제 노드는 최소 키 이상의 키를 가지고 있는 경우
다음과 같이 회전 을 진행합니다.
CASE4 병합
p가 [m/2]-2개의 원소를 가지고 있고, 가장 가까운 형제노드 q가 [m/2]-1개의 원소를 가지고 있는 경우. 즉, p가 삭제 후 최소 키보다 적은 키를 가지고 있고 형제 노드도 딱 최소 키만을 가지고 있는 경우
p,q와 p,q 중간 원소 E_i를 하나의 노드로 병합 합니다.
Comments