B Tree 이해하기
이진트리에 대해 알아보았으니 이제 균형 이진 탐색 트리의 한 종류인 B Tree에 대해 공부해 보도록 하겠다.
B Tree는 데이터 베이스와 파일 시스템에서 사용되는 트리 구조이다. DB에 트리 구조가 사용된다는 생각을 해본적이 없어서 선배들이 데베시에서 과제 B+ Tree 구현이 정말 어렵다고 했을 때 자료구조에 나오는 걸 DB에서 과제로 나오는거지 했었던 기억이 있다. 그 이유의 즉슨! DB에 B Tree, B+ Tree가 쓰이기 때문이다! 앞서 공부했든 이진 탐색 트리의 일반화를 통해 만들어졌다.
B Tree는 노드가 2개 이상의 자식을 가질 수 있어 트리의 높이를 낮게 유지하고 디스크 I/O를 최소화할 수 있다. 또한 하나의 노드에 많은 수의 정보를 담을 수 있어서 높이를 낮게 유지하는데 도움이 된다. 최대 M개의 자식을 가질 수 있는 B Tree를 M차 B Tree라고 한다. 이의 특징을 몇가지 정리해보겠다.
1. 모든 리프 노드가 동일한 깊이를 가진다.
트리의 리프 노드는 모두 동일한 레벨에 위치해야 하므로 Perfect Binary Tree와 공통된 특성을 가지고 있다. 따라서 탐색 시 리프 노드에 도달하는 경로의 길이가 모두 동일하다.
2. 각 노드는 여러 개의 키와 자식 포인터를 가질 수 있다.
하나의 노드에는 여러 개의 키가 저장되고 각각의 키는 해당 자식 트리를 가리키는 포인터와 연결된다. 만약 노드가 최대 M개의 자식을 가질 수 있는 M차 B Tree라면, 하나의 노드는 최대 M-1개의 키를 가진다. 이때 M을 B Tree의 차수(order)라고 한다.
3. 각 노드는 최소한 절반 이상 자식 노드를 가지고 있어야 한다.
하나의 노드는 최소한 ⌈m/2⌉개의 자식을 가져야 하고 키의 수는 자식 수보다 하나 적다. 예외적으로 루트 노드는 하나 이상의 자식을 가질 수 있고 리프 노드도 당연히 자식을 갖지 않는다.
즉, ⌈M/2⌉-1 <= (M차 B Tree에서 키 개수) <= M-1이다.
4. 키는 오름차순으로 정렬되어 있다.
각 노드의 키들은 반드시 정렬되어 있는 상태여야하며 각 키 사이에는 해당 범위에 속하는 자식 노드로 향하는 포인터가 존재한다. 각 포인터는 노드에 저장된 키 범위에 맞는 자식 노드를 가리킨다.
해당 그래프를 확인하면 모든 리프 노드가 동일한 깊이를 가지고 있는 것을 확인할 수 있으며 각 노드는 2개 이상의 자식 포인터를 가지고 있다. 또한 3차 B Tree이기 때문에 최대 2개의 키를 가지는 것을 확인할 수 있다. 각 노드의 키는 부모 노드의 키 범위를 기준으로 분류되어 있다. 즉, 이진 탐색 트리처럼 항상 각 키의 왼쪽 자식은 자신보다 작고 오른쪽 자식은 자신보다 크다.
B Tree의 주요 연산
1. 탐색(Search) - 검색하고자 하는 키를 k라 하였을 때 검색하는 과정이다.
이진 탐색 트리와 유사하지만 각 노드에 여러 개의 키가 있기 때문에 노드 내에서 이진 탐색을 사용한다. 루트노드에서 시작하여 키들을 순회하면서 검사한다. k값과 같은 키를 찾았으면 검색을 종료한다. 이진 탐색을 진행하여 k와 키들의 대소관계를 비교하고 어떠한 키들 사이에 k가 들어가면 해당 키들 사이의 자식 노드로 내려간다. 리프노드에 도달할 때까지 반복하고 리프노드에도 k값을 가지는 키가 없다면 검색을 실패 후 종료된다.
2. 삽입(Insert) - 균형을 유지해야 하기 때문에 키를 삽입하는 경우에는 트리의 변형이 일어날 수 있다.
삽입 과정은 탐색 과정과 다르게 리프 노드에서부터 시작한다. 비어있는 트리의 경우 루트 노드를 만들어서 k를 삽입한다. 루트 노드가 가득 찼다면 노드를 분할하고 리프 노드를 생성한다. 이후로는 해당 키가 들어갈 리프 노드를 탐색 과정과 동일하게 탐색한다. 이후 두 가지 경우로 나뉜다.
2-1. 분할이 일어나지 않는 경우
리프 노드가 가득차지 않았다면 오름차순으로 k를 삽입한다.
2-2. 분할이 일어나는 경우
리프 노드에 키가 가득찼다면 노드를 분할해야 한다. 먼저 오름차순으로 k삽입한다. 최대 키의 개수를 초과했으므로 중앙값에서 분할을 수행한다. 중앙 키가 부모 노드로 올라가고 나머지 키는 새로운 자식 노드로 분할된다. 만약 부모 노드 또한 최대 키의 개수를 초과하면 동일한 과정으로 중앙값에서 분할하고 다시 부모 노드로 중앙 키가 올라간다. 최대 키의 개수를 초과하지 않을 때까지 부모 노드로 올라가고 만족할 때까지 반복한다. 최악의 경우에는 루트 노드까지 올라가서 트리의 높이가 1 증가할 수 있다.
3. 삭제(Delete) - 삽입과 마찬가지로 균형을 유지해야 하기 때문에 삭제 시에도 트리의 변형이 일어날 수 있다.
삭제할 키가 있는 노드를 탐색하는 과정이 이루어지고 키가 삭제 되고 필요한 경우 트리 균형 조정이 일어나야한다.
1) 삭제할 키 k가 리프 노드에 있는 경우
1-1) 현재 노드의 키 개수가 최소 키 개수보다 크다.
다른 노드에 영향을 미치지 못하므로 해당 k를 단순 삭제한다.
1-2) 현재 노드의 키 개수가 최소 키 개수이고 왼쪽 또는 오른쪽 형제 노드의 키 개수가 최소 키 개수보다 크다.
부모 키 값으로 k를 대체한다. 이때 최소 키 개수 이상의 키를 가진 형제 노드가 왼쪽 형제라면 왼쪽 형제의 키 값 중 가장 큰 값을 가져오고 오른쪽 형제라면 오른쪽 형제의 키 값 중 가장 작은 값을 부모 키로 대체한다. 같다면 왼쪽 형제의 키가 먼저 사용된다.
1-3) 왼쪽, 오른쪽 형제 노드의 키가 최소 키 개수이고 부모 노드의 키가 최소 키 개수 이상이다.
k를 삭제한 후 부모 키를 형제 노드와 병합한다. 이후 부모 노드의 키 개수를 하나 줄이고 자식 노드의 수도 하나 줄여서 균형을 유지한다.
1-4) 자신과 형제, 부모 노드의 키 개수가 모두 최소 키 개수이다.
부모 노드를 루트 노드로 한 부분 트리의 높이가 하나 줄어드는 경우이기 때문에 트리의 재구조화 과정이 일어난다. 3-2 과정이 진행된다.
2) 삭제할 키 k가 내부 노드에 있다.
2-1) 현재 노드 또는 자식 노드의 키 개수가 최소 키 개수보다 크다.
현재 노드의 왼쪽 자손에서 가장 큰 키 값 혹은 현재 노드의 오른쪽 자손에서 가장 작은 키 값을 k와 바꾼다. 이제 k가 리프 노드에 있으므로 k를 삭제한다는 것은 리프 노드를 삭제하는 경우와 같아진다. 리프 노드 삭제는 1의 경우이므로 1로 이동해서 조건에 맞게 삭제한다.
2-2) 현재 노드와 자식 노드 모두 키 개수가 최소이다.
현재 노드와 자식 노드가 모두 최소 키 개수를 가지고 있다면 k를 삭제할 때 B Tree를 만족하기 위해서 트리의 높이를 줄여야한다. 즉, 트리를 재구조화해야한다. 재구조화 과정은 다음과 같다.
1. k를 삭제하고 k의 양쪽 자식 노드를 하나로 합친다. 이를 노드 n1라 하자.
2. k의 부모 키를 형제 노드와 합친다. 이를 노드 n2라 하자.
3. n1을 n2의 자식 노드가 되도록 연결한다.
4-1. 이 과정을 수행했을 때 n2의 키 개수가 최대로 가질 수 있는 키 개수보다 크다면 키 삽입 과정과 동일하게 분할한다.
4-2. n2의 키 개수가 최소로 가질 수 있는 키 개수보다 작다면 2로 돌아가서 동일한 과정을 반복한다.
어려워서 유튜브를 찾아봤다. 쉽게 정리해 놓으셨으니 이해 안 되면 찾아보기!
삭제는 항상 리프 노드에서!
삭제 후 최소 키 수보다 적어졌다면 재조정
형제 지원 -> 부모 지원 받고 형제 합침 -> 부모 도움 후 부모도 문제 시 다시 재조정
https://www.youtube.com/watch?v=H_u28u0usjA