[DataBase] Btree
이진 탐색 트리 (BST)
모든 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값들로만 이루어지고,
모든 노드의 오른쪽 서브트리는 해당 노드의 큰 값들만 가지게 된다.
또한 자녀 노드를 최대 2개까지만 가질 수 있다.
근데 자녀 노드를 N개 만큼 느려 더욱 많은 데이터를 저장하고 효율적인 검색을 위해 B-Tree 구조가 탄생하게 된다.
여러 자녀 노드를 가지면서 노드 하나에 여러 키값들을 저장할 수 있게 된다.
- 노드 수가 작아 → 트리 높이도 작고 → 디스크 I/O 적음
- 디스크에서 읽고 쓰는 것을 최소화하기 위해 고안됨
왼쪽 서브트리는 10보다 작은 값을 가지고
가운데 서브트리는 10~20사이에 값을 가지게 되고
오른쪽 서브트리는 20보다 큰 값을 가지게 된다.
B 트리는 최대 몇개의 자녀노드를 가지느냐에 따라 성질이 조금 달라진다.
B tree 파라미터
M : 각 노드의 최대 자녀수 --> 최대 M개의 자녀를 가질 수 있는 트리는 M차 B 트리라고 한다.
M - 1: 각 노드의 최대 Key 수
M / 2 : 각 노드의 최소 자녀 노드의 수
3차 B tree 라고 한다면 3/2 = 1.5 이기에 올림해서 2가 된다.
(단 root node와 자녀가 없는 leaf node 는 제외)
M/2 -1 : 각 노드의 최소 Key 수 (root node는 제외)
노드가 최소 하나의 key를 가지기 때문에 몇 차인지에 따라 상관없이 internal 노드는 최소 두 개의 자녀노드를 가진다.
B Tree의 데이터 추가
추가는 항상 맨 하단에 있는 leaf 노드에서 이루어지며 노드가 초과되면 가운데 key를 기준으로
좌우 key 들을 분할하고 가운데 key는 승진한다.
1 [탐색] 삽입할 위치(리프 노드)를 찾는다.
[30]
/ \
[10, 20] [40, 50]새로운 값 15를 삽입하고자 할 때:
- 15 < 30 → 왼쪽 자식 [10, 20] 탐색
- 해당 노드에 삽입 시도
2 [삽입] 리프 노드에 공간이 있다면, 정렬된 위치에 삽입
- [10, 20] → 아직 2개 → 최대치 안 넘음
- 삽입 후 정렬 → [10, 15, 20]
[30]
/ \
[10, 15, 20] [40, 50]3 [Split] 만약 리프 노드가 가득 찼다면, 분할(Split)
예: [10, 15, 20] 이 꽉 찼는데 12를 삽입하고 싶다
- 12를 삽입 → [10, 12, 15, 20] (정렬된 상태로 삽입)
- 노드가 초과함 → 중간 키를 기준으로 Split
- 중간 키: 12
- 왼쪽 노드: [10]
- 오른쪽 노드: [15, 20]
- 중간 키 12를 부모 노드로 올림
[12, 30]
/ | \
[10] [15,20] [40,50]4 [부모도 꽉 찼을 경우] → 부모도 Split 발생 → 재귀적으로 위로 전파
- 부모 노드도 꽉 차있을 경우 → 부모도 분할
- 이 과정이 루트까지 가면 → 루트가 분할되고 트리 높이 증가
루트 분할 전:
[20, 40]
/ | \
[10] [30] [50]
새로운 값 `35` 삽입 → 분할 필요
* B Tree는 모든 leaf 노드들이 같은 레벨에 있는 밸런스 트리이다. --> 시간복잡도가 Olog N 이 된다.
B Tree의 데이터 삭제
삭제도 항상 leaf 노드에서 발생한다.
삭제후 최소 key 수 보다 적어졌다면 재조정에 들어간다.
3차 B tree에서 각 노드의 최소 Key 수 = 3/2 -> 2(올림) - 1 = 1
여기서 5를 삭제하게 된다면 최소 key가 만족할 수 없기때문에
1. Key 수가 여유있는 형제의 지원(1,2 와 8,9)을 받는다.
2. 지원이 불가능하면 부모의 지원을 받고 형제와 합친다.
3. 2번후 부모도 만족하지 못한다면 다시 재조정에 들어간다.
위에서는 2를 지원받고 2를 승격하고 그 다음값인 3을 밑으로 내린다.
여기서 3을 삭제하게 되면 조건이 만족되지 않기 때문에 여유가 있는 오른쪽에 지원을 받는다.
8은 승격하고 7은 내려오게 된다.
또 다시 7를 삭제한다고 할때는 형제는 모두 지원이 불가능 하기에 부모에게 2를 받고 삭제된 노드는 형제노드에 흡수된다.
internal 노드에서 데이터 삭제
- internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼후 삭제한다.
(삭제할 데이터의 선임자나 후임자와 위치를 바꿔주어야 한다.)
선임자(해당 노드의 값 보다 작은 데이터들 중 가장 큰데이터)를 기준으로 15를 삭제하는 경우는 아래와 같다.
9와 위치를 바꾸어 삭제하면 된다.
해당 글은 유튜버 '쉬운코드' 님의 영상의 내용을 적었습니다.
출처 : https://www.youtube.com/watch?v=H_u28u0usjA&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=30