Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS
GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip
주니어 개발자를 위한 전공 지식 모음.zip. Contribute to seoul-developer/CS development by creating an account on GitHub.
github.com
💋 B-Tree란?
✔️ 개념
이진 탐색 트리를 일반화한 트리다. Binary-Tree 라고 오해를 하지만 Balanced-Tree 를 의미한다.
따라서, 이진 탐색 트리와 비교하면 더 이해가 쉽다!
일반적인 이진 탐색 트리에서는 각 노드가 최대 두 개의 자식 노드를 가지지만, B-Tree에서는 그 제약이 없어 여러 개의 자식을 가질 수 있다.
⇒ B-Tree는 자녀 노드의 수가 2개로 고정되어 있지 않다.
이진 탐색 트리를 생각해보면, 왼쪽 자녀 노드는 키보다 작은 값을 가지고, 오른쪽 자녀 노드는 키보다 큰 값을 가진다.
B-Tree에서는 2개 이상의 자녀 노드를 가질 수 있다. 예를 들어서, 자녀 노드를 3개 가지는 B-Tree가 있다고 할 때, 부모 노드의 키가 k1, k2라고 한다면 가장 왼쪽의 서브 트리의 모든 노드 키는 k1 미만, 중간 서브 트리의 모든 노드 키는 k1 이상 k2 미만, 가장 오른쪽 서브 트리의 모든 노드 키는 k2 이상으로 구분할 수 있을 것이다.
⇒ B-Tree에서는 부모 노드도 키를 1개 이상 가진다!
✔️ 특징
- 자녀 노드의 최대 개수를 늘리기 위해서, 부모 노드에
키를 하나 이상 저장한다. - 부모 노드의 키는
오름차순으로 정렬한다. - 정렬된 순서에 따라서 자녀 노드들의 키 값의 범위가 결정된다.
⇒ 자녀 노드의 최대 개수를 원하는 만큼 정해서 쓸 수 있다.
✔️ 파라미터
최대 몇 개의 자녀 노드를 가질 것인지가 B-Tree에서는 중요한 파라미터이다!
M만 결정하게 되면, 아래의 나머지 속성들은 저절로 결정되게 된다.
- M ⇒ 각 노드의 최대 자녀 노드 수
- 최대 M개의 자녀 노드를 가질 수 있는 B-Tree는
M차 B-Tree M-1⇒ 각 노드의 최대 키 수- 3차 B-Tree에서 부모 노드의 최대 키는 2개!
ceil(M / 2)⇒ 각 노드의 최소 자녀 노드 수- 3차 B-Tree의 경우, 3 / 2 = 1.5에 올림을 한 값인 2가 최소 자녀 노드의 수가 된다.
- root node, leaf node에서는 위 조건은 예외적으로 제외된다.
ceil(M / 2) - 1⇒ 각 노드의 최소 키 수- root node에서 위 조건은 예외적으로 제외된다.
결과적으로, 아래와 같은 조건은 항상 성립하게 된다.
- internal 노드의 키 수가 x개 ⇒ 자녀 노드의 수는 언제나
x + 1개 - 노드가 최소 하나의 key는 가지기 때문에, 몇차 B-Tree인지와 상관 없이, internal 노드는 최소 2개의 자녀는 가진다.
- M차 B-Tree에서는 루트 노드를 제외하고는 모두 최소
ceil(M/2)개의 자녀 노드를 가질 수 있다.
✔️ 최소 자녀 노드의 수는 왜 정해둘까?
최소 자녀 노드의 수를 정하는 것은 B 트리의 균형을 유지하고 트리의 높이를 증가시키지 않기 위한 중요한 설계 요소 중 하나다.
최소 자녀 노드의 수를 제한하면, 트리의 전체 높이가 낮아져서 각 연산의 수행 시간이 상대적으로 작아지며, 디스크 I/O 등의 비용도 줄어든다. 키의 최소 자녀 노드의 수를 조절하여 트리의 균형을 유지하는 것이 B 트리의 핵심 개념 중 하나이며, 이를 통해 B 트리는 대용량 데이터베이스와 파일 시스템에서 효과적으로 사용된다.
💋 B-Tree insert 연산
- 데이터 추가는 항상 리프 노드에 한다.
- 노드가 넘치면 가운데 키를 기준으로 좌우 키를 분할하고 가운데 키는 승진한다.
- M차 B Tree에서 노드가 M-1개보다 더 많은 키가 생기는 경우
insert 연산은 이 링크를 타고 들어가면 그 과정을 따라갈 수 있다.
기억해야 할 특징적인 것은, 데이터 추가를 항상 리프 노드에 하고 키를 승진하는 방식으로 트리의 높이를 높이기 때문에 모든 리프 노드는 같은 레벨에 존재하게 된다는 것이다.
⇒ B-Tree는 Balanced Tree
⇒ 검색의 average, worst case의 시간 복잡도는 모두 O(logN)
💋 B-Tree delete 연산
- 데이터 삭제도 항상 리프 노드에서 발생한다.
- 삭제하려는 데이터가 internal 노드에 존재한다면, 리프 노드에 있는 데이터와 위치를 바꾸고 나서 삭제한다.
- 데이터 삭제 후 노드의 키 수가 최소 키 수(
ceil(M / 2)-1)보다 적어졌다면 재조정한다.
아래 예시는 3차 B-Tree에서의 데이터 삭제에 대한 예다.
⇒ 최대 자녀 노드 3개, 최대 부모 키 2개, 최소 자녀 노드 2개, 최소 부모 키 1개
✔️ 리프 노드의 데이터를 삭제한 후, 최소 키 수 제약을 만족하는 경우
리프 노드의 데이터를 삭제하고, 삭제 이후에도 최소 키 수 제약을 만족한다면, 그냥 노드를 삭제한다.
✔️ 리프 노드의 데이터를 삭제한 후, 최소 키 수 제약을 만족하지 못해 형제 노드로부터 키를 빌려오는 경우
가운데에서 5 노드를 지웠더니, 빨간 부분을 보면 해당 노드는 최소 키 수인 1개보다 적어지게 된다.
재조정을 하기 위해서는, 좌우 형제들 중에서 키 수에 여유가 있는 형제의 지원을 받는다. 옆에 1, 2 키를 가진 형제 노드는 현재 키 수가 2개로 1개 여유가 있어서 키를 빌려올 수 있다.
결과적으로 부모 노드에 있던 키 3을 내리고, 왼쪽 형제 노드에서 키 2를 부모 노드로 올리면 최소 키 개수를 만족시키면서 데이터를 삭제할 수 있다.
유사한 방식으로, 아래 예시에서는 부족한 키 수를 보충하기 위해 오른쪽 형제 노드로부터 키를 가져오게 된다.
✔️ 리프 노드의 데이터를 삭제한 후, 최소 키 수 제약을 만족하지 못해 부모 노드의 지원을 받아 형제 노드와 합치는 경우
리프 노드에서 데이터를 삭제하는데, 양쪽 형제 노드 모두 최소 키 개수만큼만 가지고 있다면 (형제 노드에서 빌려오는 것이 불가능한 경우), 부모의 지원을 받고 형제와 합친다.
아래같은 상황에서 7 키를 삭제하려고 한다.
7을 삭제했더니, 노드에 아무런 데이터가 없게 되어 최소 키 수인 1을 만족하지 못하게 되었다. 하지만 옆에 있는 형제 노드들도 각각 키를 1, 9 하나씩만을 가지고 있어서 빌려줄 수도 없다.
형제의 지원이 불가능하므로, 부모 노드의 지원을 받고 형제와 합친다.
형제와 합치게 되면서 노드가 하나 줄어들게 된다.
이 작업 이후에 부모 노드의 키 수도 너무 작아져 문제가 생겼다면, 거기서도 다시 재조정한다.
아래와 같은 경우에 키 1을 삭제한다면, 형제 노드도 부모 노드도 모두 최소 키 수인 1만큼만 갖고 있어서 빌려줄 수 없다.
✔️ internal 노드에서 데이터를 삭제하는 경우
아래의 예시에서 루트 노드에 존재하는 데이터인 15를 삭제한다고 해보자.
internal 노드에 있는 데이터를 삭제하려면, 리프 노드에 있는 데이터와 위치를 바꾼 후 삭제한다.
⇒ 리프 노드에 있는 데이터 중 어떤 데이터와 위치를 바꿀 것인지가 중요하다!
삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.
- 선임자(predecessor): 나보다 작은 데이터 중 가장 큰 데이터
- 후임자(successor): 나보다 큰 데이터 중 가장 작은 데이터
⇒ 이렇게 선임자나 후임자와 자리를 바꾸게 되면, 데이터 삭제 후에 루트 노드의 왼쪽 서브 트리의 키들은 모두 루트 노드의 키보다 작고 오른쪽 서브 트리의 키들은 모두 루트 노드의 키보다 커서 B-Tree의 속성을 만족하게 된다.
현재 15의 선임자는 9, 후임자는 20이 된다.
선임자와 자리를 바꿨다. 그리고, 이후에 15를 삭제하더라도 최소 키 수인 1개를 만족하기 때문에 곧바로 삭제할 수 있다.
✔️ internal 노드의 선임자/후임자는 항상 리프 노드에 있을까?
하나의 internal 노드를 생각했을 때, 나보다 작은 값 중 가장 큰 값을 찾으려면 어떻게 해야 할까?
먼저 왼쪽 서브 트리로 가면 항상 현재 키보다 작은 값만 존재한다. 거기서부터 계속해서 오른쪽으로 가서 더이상 데이터가 없을 때까지 내려가면 현재 키보다 작은 값 중 가장 큰 값이 존재한다. 그리고, 그 값은 더이상 데이터가 없을 때까지 갔으므로 루트 노드일 것이다.
⇒ 삭제하려는 데이터의 선임자 or 후임자는 항상 리프 노드에 있다.
✔️ 정리
삭제 후, 해당 노드의 키 수가 최소 키 수보다 적어졌다면 아래와 같은 방식으로 진행한다.
- 키 수가 여유있는 형제 노드의 지원을 받는다.
- 왼쪽 형제 노드(동생 노드)의 키 수에 여유가 있다면, 동생 노드의 가장 큰 키를 부모 노드로 올려서 현재 노드와 동생 노드 사이에 둔다. 그리고 원래 그 자리에 있던 키(부모 노드의 키)를 현재 노드의 가장 왼쪽에 둔다.
- 오른쪽 형제 노드(형 노드)의 키 수에 여유가 있다면, 형 노드의 가장 작은 키를 부모 노드로 올려서 현재 노드와 형 노드 사이에 둔다. 그리고 원래 그 자리에 있던 키(부모 노드의 키)를 현재 노드의 가장 오른쪽에 둔다.
- 형제 노드의 지원이 불가능하면, 부모 노드의 도움을 받고 형제 노드와 합친다. (합칠 때는 왼쪽으로 합친다)
- 동생 노드가 있으면, 동생 노드와 현재 노드 사이의 키를 부모로부터 받는다. 그 키와 현재 노드의 키를 모두 동생 노드에 합치고, 현재 노드를 삭제한다.
- 동생 노드가 없다면, 형 노드와 현재 노드 사이의 키를 부모로부터 받는다. 그 키와 형 노드의 키를 모두 현재 노드에 합치고, 형 노드를 삭제한다.
- 부모가 지원한 후에 부모 노드의 최소 키 수에 문제가 발생하는 경우 상황에 맞게 대응한다.
- 부모가 루트 노드가 아니라면, 그 위치에서부터 다시 1번부터 재조정을 시작한다.
- 부모 노드가 루트 노드고 비어 있다면, 부모 노드를 삭제하고 직전에 합쳐진 노드를 루트 노드로 한다.
💋 참고자료
- https://www.tutorialspoint.com/data_structures_algorithms/b_trees.htm
- https://www.geeksforgeeks.org/introduction-of-b-tree-2/
- https://www.youtube.com/watch?v=bqkcoSm_rCs&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=25
- https://www.youtube.com/watch?v=H_u28u0usjA&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=26
B-Tree의 연산에 대해서 직접 실습해보고 싶다면, 이 링크를 들어가면 쉽게 눈으로 확인할 수 있다. (왕추천)
B-Tree Visualization
www.cs.usfca.edu
도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!
'Computer Science > Data Structure' 카테고리의 다른 글
| [자료구조] Map과 Hash Table: 해시 함수와 해시 충돌의 해결, 해시 테이블 리사이징 (3) | 2023.12.19 |
|---|---|
| [자료구조] B-Tree 자료구조가 DB 인덱스에 사용되는 이유: secondary storage 접근과 block 단위의 저장 공간 활용 관점에서 (0) | 2023.12.19 |
| [자료구조] AVL 트리의 개념, Balance Factor, 시간 복잡도와 한계에 대해 알아보자! (0) | 2023.12.17 |
| [자료구조] 이진 탐색 트리 (Binary Search Tree): 개념, 순회, 연산과 시간 복잡도 (2) | 2023.12.15 |
| [자료구조] Priority Queue(우선순위 큐)와 Heap(힙) (2) | 2023.12.15 |
