B Tree
B Tree는 Balanced Tree로 균형을 유지하는 트리
이진 트리가 자식 노드가 최대 2개라면,
B Tree는 자식 노드가 2개 이상인 트리를 말한다
- 노드의 데이터가 1개 이상일 수 도 있다.
- 노드내 데이터의 수에 따라 2차, 3차, m차 B Tree라고 한다.
- 차수가 홀수인지 짝수인지에 따라 알고리즘이 달라짐
B Tree 성립 조건
- 노드내의 데이터수가 n개라면 자식 노드의 개수는 n+1
root 노드의 데이터가 3개라 자식 노드의 개수는 4개
- 노드의 데이터는 반드시 정렬된 상태여야 함
- 노드의 자식노드의 데이터들은 노드 데이터를 기준으로 데이터보다 작은 값은 왼쪽 서브 트리에 큰값들은 오른쪽 서브 트리에 이루어 져야 함
- root노드가 자식이 있으면 최소 2개이상의 자식을 가져야함(양쪽으로 하나씩)
- root노드를 제외한 모든 노드는 적어도 m/2 개의(m은 차수) 데이터를 가져야함
-> 3차까지는 1개의 데이터를 가지면 되나 4차부터는 root를 제외한 노드가 2개이상의 데이터는 갖고 있어야함
- Leaf 노드로 가는 경로의 길이는 모두 같아야 함. 즉 Leaf 노드는 모두 같은 레벨에 존재해야 함
- 입력 데이터는 중복 불가
탐색
이진 트리와 마찬가지로
root 노드 부터 시작해서 하향식으로 탐색함
삽입
- 데이터는 항상 리프 노드에 추가된다
- 리프 노드의 선택은 root에서 시작해 하향식으로 탐색해서 결정
- 선택한 리프 노드에 여유가 있으면 삽입, 없으면 분할(중간 값을 위로 올림)
1) 1 삽입
2) 3 삽입
3) 7 삽입 -> 중간 값인 3이 올라감 (짝수 차수일 경우 중간에서 왼쪽)
4) 9 삽입
5) 8 삽입 -> 중간 값인 8이 올라감
6) 11 삽입
7) 15 삽입 -> 중간 값인 11 올라가서 root가 3,8,11 이 됨
-> 중간 값인 8이 올라가서 root가 됨
삭제
리프 노드일때
case 1 : 6 삭제 - 삭제해도 B Tree가 유지되면 끝
case 2 :
1) 9 삭제 - 삭제하면 B Tree가 유지 안 됨
2) 11이 내려와서 병합 (노드 데이터들중 )
3) 8이 내려와서 병합
리프 노드가 아닐때
삭제는 반드시 리프노드에서 이루어 져야 하기 때문에
왼쪽 서브트리 중 가장 큰값 or 오른쪽 서브트리 중 가장 작은 값 이랑 바꿔치기 한다.
그리고 나서 리프 노드 지우는 법이랑 동일하게 수행한다
1) 7을 삭제 하려함
2) 6이랑 7 바꿔치기 하고 7삭제
3) 6다시 내려오고 9가 올라간다
B+ Tree
-
Index node 들과 data node(레코드) 로 구성이 되어있다 .
-
Index node : leaf node 를 제외한 나머지 node 들.
-
Data node : leaf node 를 일컫는 동의어.
-
Data node 는 연결리스트로 형성되어있고 Data node 하나의 크기는 Index node 하나의 크기와 똑같지 않아도 된다.
-
B+ 트리의 높이는 B 트리 보다 낮게 구성되므로 검색시간과 디스크에 접근하는 횟수가 줄어든다.
-
index node 에 존재하는 key는 자신의 right subtree 의 data node 의 가장 첫번째 위치에 존재하게 된다.
삽입
overflow 발생 시 차수에 따라 방식이 다르다.
t = M/2
차수 M 이 홀수인 경우 : t-1번재(가운데) index 를 상위로 올린다.
차수 M=5
차수 M 이 짝수인 경우 : t 번째(중간에서 오른쪽) index 를 상위로 올린다. (B 트리의 짝수 overflow 와의 차이점)
이렇게 해야 정확히 반으로 쪼갤 수 있기 때문이다. 직접 트리를 그리면서 balance 가 맞춰지는 것을 확인하는게 더 이해가 빠를것이다.
차수 M=6
삭제
B 트리는 삭제과정이 복잡하지만 B+ 트리는 data node 에서 삭제를 수행한다. 삭제 된 key 값이 index node 에 존재한 경우 재귀적으로 확인하여 index node 를 변경시킨다.
삭제하는 원소 k 가 있는 node 를 y라 하면
- y 의 key 개수가 t 개 이상이면 원소 k 삭제 후 index node 에 k 가 있으면 index node 에서도 삭제 후 적절한 key 값을 그 자리에 넣는다.
예시. 차수 M=4
leaf node의 3 삭제 후 index node 의 3도 삭제된다. 그 후 4를 추가해준다.
- y 의 key 개수가 t-1 개 이면 y 의 sibling node z 의 원소 수가 t 개 이상인 경우 borrow 한다.
원소 k 삭제 후 x에서 y로 원소 보내고 z에서 x로 원소 보낸다.
