B-Tree는 I/O에 효율적인 자료구조로 가장 많이 사용된다.
왜 효율적인 자료구조인지 알아보자.
B-Tree 계열을 알기 위해서는 (B+Tree, B*-Tree, ...)
우선적으로 B-Tree의 기원인 BST를 알아야한다
BST(Binary Search Tree)
이진 탐색 트리로
이진트리의 특성은 자식을 0, 1, 2개 중 하나를 가진다는 것이다
하지만 이것의 최악의 구조에는 다음과 같은 경우가 존재한다
위와같이 잇다고했을 때
가장 밑단의 자식 노드에 접근하려고 하면,
최악의 경우로 취급된다. ( O(N)만큼의 시간 복잡도 요구됨 )
최악의 경우에는 위와 같이 접근을 해야한다.
내부적으로 BST를 스스로 정렬한 구조인 AVL이나 red black tree 등이 존재하는데,
이것들 보다 더 많은 데이터를 포함하는 트리인 B-Tree에 대하여 알아보자
B-Tree
여기서의 B는 주의할점이 Binary가 아니라 Balanced라는 의미이다.
Balanced이기 때문에
균형이 잡힌 트리이다.
그래서 BST의 일반화된 구조가 B-Tree라고 한다
이러한 Balanced의 규칙을 지키기 위하여 다음과 같은 특징들이 존재한다.
우선은 규칙들에 해당되는 용어를 정리해보자.
구성 요소에는
- Node: 구성의 가장 기본적인 단위
- Key : 노드가 담을 수 있는 데이터
- Root Node : 가장 뿌리가 되는 최상위의 노드
- Leaf Node : 가장 밑단의 최하위 자식 노드
- Internal Node : Leaf 노드가 아니면 전부 Internal 노드라고 부른다
그렇다면 다음 규칙들이 존재한다.
- M : 최대 자식 노드의 개수 (차수, Order)
M 은 B-Tree의 차수 를 나타내며,
하나의 노드( 디스크 페이지, 디스크에서의 동작 단위인 블록)가 가질 수 있는 최대 자식 포인터의 개수이다.
이 M은 트리의 너비를 결정하므로, M차 B-Tree와 같은 용어로 사용된다.
M이 클수록 한 노드에 더 많은 정보를 담을 수 있으므로, 트리의 높이가 낮아져 데이터 검색 시 필요한 디스크 접근(I/O) 횟수를 최소화할 수 있다.
이것이 B-Tree의 차별점이기도 하다. 하나의 노드에 여러개의 데이터를 저장할 수 있기 때문이다.
예시로 다음 5차 B-Tree를 확인해보자.
5차 B-Tree
위는 M=5인, 5차 B-Tree의 예시이다.
- M-1 : 각 노드의 최대 key 값의 개수
노드 내에 저장할 수 있는 key의 최대 개수이다.
각각의 노드는 M-1이 넘는 만큼의 key(데이터)를 저장할 수 없다.
최대의 key 값의 개수이므로, 그림 상에서 노드에서의 칸의 개수라고 생각하면 된다.
따라서 최대 M개의 자식을 가지기 위해서는 최대 M-1개의 키를 저장할 수 있다.
또한 사진에서처럼 B-Tree의 규칙에 따라서 k개의 키를 가진 노드는 k+1 개의 자식 포인터를 가진다. 만약 실제 데이터의 개수가 k개라면, 자식에 대하여 k+1만큼의 범위를 가지고 있는 것이므로 k+1개의 포인터를 가지고 있다는 것이다.
노드 내의 모든 키 값은 오름차순으로 정렬되어야하며,
이 키들이 자식 노드로 가는 경로를 분할하는 기준이 된다.
노드 내의 모든 키 값은 오름차순으로 정렬되어야한다.
이는 왼쪽 -> 오른쪽으로 정렬된다. 같은 레벨에서는 비유적으로 이를 형제 관계에서 왼쪽이 동생 쪽이고, 오른쪽이 형이라고 칭하기도 한다.
- [M/2] : 각 노드의 최소 자식의 수
루트 노드를 제외한 모든 노드가 가져야하는 최소한의 자식 노드 개수이다. ( Celling으로 반올림을 해줘야한다)
이 규칙은 B-Tree의 상징인 Balanced 상태를 유지하기 위하여 강제하는 핵심이다.
각 노드가 최소한 절반 이상은 채워져잇어야 불필요한 노드 생성과 트리의 높이 증가를 막는다.
데이터 삭제 시에도 노드가 너무 비어있지않도록 보장을 해준다.
- [M/2]-1 : 각 노드의 최소 key 값의 개수
루트 노드를 제외한 모든 노드들이 가져야하는 최소한의 key의 개수이다.
트리가 k개의 키에서 k+1 자식을 가진다. 이에 따라 위에서 서술한 최소 자식의 수를 유지하기 위해서는 최소 해당 key값의 개수를 가져야한다.
루트 노드는 최소 키 개수 제약에서 예외된다.
B-Tree에서의 조회
B-Tree에서의 조회는 쉽다.
B-Tree는 루트 노드를 기준으로 왼쪽과 오른쪽의 서브트리로 나뉜다.
작은 값에 대해서는 왼쪽으로, 큰 값에 대해서는 오른쪽으로라는 정렬이 이미 되어있기 때문에
조회하려는 key 값에 대하여 비교를 하면서 해당 노드로 접근을 하고,
노드 안에서 key를 찾으면 된다.
B-Tree에서의 삽입
B-Tree에서의 삽입은 무조건 leaf 노드에서 이루어져야한다.
루트 노드에서부터 탐색을 시작하여,
삽입에 대한 적절한 위치를 찾아야한다.
B-Tree는 정렬 기반으로 서브트리로 확장된 구조이기 때문에 탐색이 쉽다.
1) 삽입에 대한 적절한 리프 노드까지 내려가기
새로운 키를 삽입하기 위해서는 먼저 루트부터 시작한다.
비교를 통해서 어느 자식으로 내려갈지에 대하여 결정한다.
이 과정을 반복해서 삽입 위치가 될 리프 노드까지 도달하면 된다.
하지만 Balanced Tree인 만큼 노드에 대하여 키들의 개수가 조건을 만족하는지를 확인해야한다.
만약 키의 개수가 규칙을 넘는다면, 이에 대한 재조정이 필요하다.
2) 리프 노드에 여유 공간 존재 - 그냥 삽입
리프가 아직 최대 허용 키 개수인 M-1개를 초과하지 않았다면,
그 자리에 정렬된 상태를 유지하면서 삽입하면 된다.
추가적인 구조 변경 없이 작업이 끝난다.
3) 리프 노드가 가득 찬 상태 - 분할(Split) 발생
하지만 리프 노드가 이미 최대 개수인 M-1개 만큼 가득 찼다면,
키를 삽입한 뒤에 전체를 정렬하고,
하나의 노드를 분할하여 두 개의 노드로 만들어야한다.
노드가 넘치면 가운데에있는 median을 부모 노드로 올린다.
그리고 부모가 자식 포인터를 재조정하도록 만든다.
(M-1개의 key보다도 더 많은 노드를 저장하려고 하면 해당 상황을 노드가 넘친다고 한다)
4) 부모 노드도 가득 찬 상태 - 상위로 연쇄적인 분할 전파
부모 노드가 분할된 키를 받아야하는데,
부모 또한 노드가 이미 가득차있다면,
동일한 과정에 대한 반복으로 부모 노드도 또 Split된다.
이러한 반복은 루트 노드에게까지로 전파될 수도 있다.
최종적으로 루트가 분할되면 새로운 루트가 생성되어
트리의 높이(Depth)가 1 증가하는 것이다.
즉, 삽입에 대한 전반적인 과정은
리프에서 시작하고, 공간이 없으면 Split을 통해 상위로 조정해나가면서
트리의 균형을 계속 유지하는 것이다.
B-Tree에서의 삭제
B-Tree에서의 삭제도, 삽입과 동일하게 leaf 노드에서 이루어져야한다.
1) 삭제 대상이 리프 노드에 있는 경우
리프 노드에서 이루어져야하기 때문에,
해당 키를 삭제하고 다시 노드에서 정렬해주면 된다.
하지만 리프노드가 아닌 곳이 삭제의 대상이라면 어떻게 해야할까?
2). 삭제 대상이 리프 노드에 없는 경우 - 먼저 리프로 내려보내기
내부 노드(Internal Node)를 바로 삭제하는 것은 불가능하다.
대신 삭제하려는 키의 전임자(predecessor) 또는 후임자(successor)의 키를 가져와서,
삭제하려는 키와 교체한 뒤에 해당키가 실제로 존재하는 리프에서 삭제 과정을 수행한다.
위의 예제처럼 12를 삭제하고 싶으나, 이는 Internal 노드이기 때문에 바로 삭제해주지 못한다.
그래서 successor인 13과 자리를 바꾸고 12를 삭제해준다.
하지만 이렇게 노드에서 키에 대한 삭제가 이루어졌는데,
이 노드의 키들이 최소 만족 개수인 [M/2]-1개를 만족하지 못한다면,
이에 대하여 지원을 받는 재조정이 필요하다.
3) 삭제 후 최소 키 개수를 만족하지 못하는 경우 - 형제 노드에게서 빌리기 (Roatating / Redistribution )
동일한 레벨에 대하여 우선적으로 key의 개수가 보다 더 여유있는 쪽으로부터 키를 받으면 된다.
예를 들어 위의 왼쪽에 있는 노드에서 키 하나를 삭제했는데 해당 노드가 최소한 가져야하는 키의 개수를 만족하지 못한 경우라고 생각해보자.
그러면 형제 노드로부터 데이터를 전달 받아야한다.
받는 순서는 우선적으로 왼쪽부터 탐색 -> 없다면 오른쪽으로 탐색한다.
(B-Tree에서 순서는 무조건 왼->오 이다)
즉, 형제 중에서 여유가 있는 쪽에서 키 하나를 받고,
그에 맞춰서 부모의 키도 함께 조정하면 트리가 다시 균형을 유지한다.
그런데 만약 동일한 레벨 차원에서도 최소한의 키에 대해서만 만족하고 있다면 형제로부터 빌려오는 것이 어렵다. 이럴 때에는 어떻게 할까?
4) 형제에게서 빌릴 수 없는 경우 - 병합(Merge)
만약 형제 노드의 지원을 받을 수 없다면
상위의 부모 노드로부터 키 하나를 받고 형제와 합쳐서 하나의 노드로 병합(Merge) 해야한다.
이 과정에서도 트리는 항상 정렬된 상태로 유지되어야한다.
5) 부모 쪽에서도 규칙 위반이 전파되는 경우 - 재귀적 재조정
부모 노드에서 키 하나를 내려주었는데,
만약에 부모 노드에서 최소 만족하는 키의 개수인 [M/2]-1개를 만족하지 못한다면 어떻게 해야할까?
부모 역시 최소 키 조건에 대하여 만족하는지를 확인해야한다.
이럴 때, 부모가 루트 노드라면 루트가 키를 전부 다 잃은 빈 노드의 상태라면 루트를 삭제해주면 된다. 그리고 병합으로 생긴 자식을 새로운 루트 노드로 삼아서 트리 높이(Depth)를 1 줄이면 된다.
부모가 루트 노드가 아니라면 같은 방식으로 상위로 계속 재조정을 하면서 진행하는 방식으로 진행된다.
즉, 트리의 삭제에 대해서는 Balanced를 위한 조건들을 지키기 위하여 항상 정렬->균형 유지->최소 키 개수 조건 유지 를 만족해주어야한다.
REF
'자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조] 비선형 자료구조 : 트리 (1) | 2024.04.12 |
|---|