[TIL] B-Tree, B-트리
B-Tree, B-트리
데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료 구조
이진 트리는 하나의 노드가 가질 수 있는 자식 노드가 최대 2개인 반면,
B-Tree 는 m 개의 자식 노드를 가질 수 있다
차수가 3인 B-Tree, 파란색 부분은 각 노드의 Key 를 나타내며, 빨간색 부분은 자식 노드들을 가리키는 포인터
Key 들은 노드 안에서 항상 정렬된 값을 가지며, 각 Key 들의 왼쪽 자식들은 항상 Key 보다 작은 값을, 오른쪽은 큰 값을 가진다
B-Tree 는 order M 을 가지며, 이를 B-Tree of order M 이라고 한다
B-Tree of order M 은 다음과 같은 조건을 만족해야 한다
- 모든 노드가 가질 수 있는 자식 노드의 최대 수는 M 이다
ex) 3차 B-Tree 라면 최대 3개의 자식 노드를 가질 수 있다 - 루트와 리프 노드를 제외한 내부 노드는 최소 M/2 개의 자식 노드를 가져야 한다
ex) 3차 B-Tree 라면 각 노드는 최소 2개의 자식 노드를 가진다 - 노드에는 최소 M/2 - 1 개, 최대 M-1 개의 Key 를 가질 수 있다
ex) 3차 B-Tree 라면 최소 1개, 최대 2개의 Key 를 가질 수 있다
B-Tree 실습
B-Tree 검색 과정
루트 노드부터 시작하여 하향식으로 검색 수행
1. 루트 노드에서 시작하여 Key 들을 순회하면서 검사
1-1. 만일 k 와 같은 Key 를 찾았다면 검색 종료
1-2. 검색하는 값과 Key 들의 대소 관계 비교, 어떠한 Key 들 사이에 k 가 들어간다면 해당 Key 들 사이의 자식 노드로 이동
2. 리프 노드에 도달할 때까지 반복, 만일 리프 노드에도 k 와 같은 Key 가 없다면 검색 실패
1) 18 검색 시작, 루트 노드 Key 중 10보다 크고 20보다 작기 때문에 중간 자식 노드로 이동
2) 18은 14, 17보다 크기 때문에 노드의 가장 마지막 자식 노드로 이동
3) 18 검색 완료
B-Tree 데이터 삽입
추가는 항상 leaf 노드에 한다
노드가 넘치면 가운데, Median Key 를 기준으로 좌우 Key 들을 분할하고 가운데 Key 는 승진한다
* 노드가 넘친다 - M차 B트리에서 각 노드는 최대 M-1 개의 Key 를 가질 수 있는데, 데이터를 삽입하는 과정에서 이를 위반한 것
1. 트리가 비어 있다면, 루트 노트를 할당하고 K 삽입
2. 트리가 비어 있지 않다면, 데이터를 넣을 적절한 리프 노드 탐색
3. 리프 노드에 데이터를 넣고, 리프 노드가 적절한 상태에 있다면 종료
4. 리프 노드가 부적절한 상태에 있다면 분리
1) 13 삽입 시작, 루트 노드 Key 중 10보다 크고 20보다 작기 때문에 중간 자식 노드로 이동
2) 13은 14보다 작기 때문에 가장 왼쪽 자식 노드로 이동
3) 13은 12보다 크기 때문에 가장 마지막에 삽입, 해당 노드가 최대로 가질 수 있는 Key 의 개수를 초과했기 때문에 분할 수행
4) 중앙값 12를 기준으로 분할 수행
5) 12는 부모 노드에 오름차순으로 삽입, 11과 13은 12의 왼쪽/ 오른쪽 자식으로 설정
6) 12가 병합된 노드가 최대로 가질 수 있는 Key의 개수를 초과했기 때문에 중앙값 14를 기준으로 분할 수행
7) 14는 부모 노드에 오름차순으로 삽입, 12과 17은 14의 왼쪽/ 오른쪽 자식으로 설정
8) 14가 병합되어 노드가 최대로 가질 수 있는 Key 의 개수를 초과, 중앙값 14를 기준으로 분할 수행
9) 14가 새로운 루트 노드가 되고, 10과 20은 14의 왼쪽/ 오른쪽 자식으로 설정되어 삽입 과정 완료
B-Tree 데이터 삭제
1. 삭제할 Key 가 있는 노드 검색
2. Key 삭제
3. (필요한 경우) 트리 균형 조정
삭제 예시 https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC < 여기가 좋음
참고) 삭제할 노드가 자식 노드를 가지고 있을 경우,
일반적으로 가장 오른쪽 자식 노드로 대체하거나 자식 노드 중 하나를 선택하여 대체한다
* 추가 용어
Inorder Predecessor - 노드의 왼쪽 자식에서 가장 큰 Key
pre-(앞의) decessor(가다, 나가다), 앞서가는 것 - 특정 노드의 "앞서" 있는 (더 작은 값인) 노드
Inorder Successor - 노드의 오른쪽 자식에서 가장 작은 Key
suc-(아래로) cessor(가다, 나아가다), 다음에 오는 것 - 특정 노드의 "다음" 에 있는 (더 큰 값인) 노드
Case1) 삭제할 Key k 가 리프에 있는 경우
Case1.1) 현재 노드의 Key 개수가 최소 Key 개수보다 크다면
다른 노드들에 영향 없이 해당 k 를 단순 삭제한다
- 12 삭제, 해당 노드의 Key 개수는 최소 Key 개수 1보다 크므로 바로 삭제
Case1.2) 왼쪽 또는 오른쪽 형제 노드의 Key 가 최소 Key 개수 이상이라면
1. 부모 Key 값으로 k 대체
2. 최소 Key 개수 이상의 Key 를 가진 형제 노드가 왼쪽 형제라면 가장 큰 값을, 오른쪽 형제라면 가장 작은 값을 부모 Key 로 대체
- 15 삭제, 해당 노드를 부모 Key 로 대체, 왼쪽 형제 노드에서 가장 큰 값을 부모 Key 로 대체
Case1.3) 왼쪽, 오른쪽 형제 노드의 Key 가 최소 Key 개수이고, 부모 노드의 Key 가 최소 개수 이상이면
1. k 를 삭제한 후 부모 Key 를 형제 노드와 병합
2. 부모 노드의 Key 개수를 하나 줄이고, 자식 수 역시 하나를 줄여 B-Tree 유지
- 18 삭제, 부모 Key 를 내려 형제 노드와 병합
Case 2. 삭제할 Key k 가 내부 노드에 있고, 노드나 자식에 Key 가 최소 Key 수보다 많을 경우
1. 현재 노드의 inorder Predecessor 또는 Inorder Successor 와 k 의 자리를 바꾼다
2. 리프 노드의 k 를 삭제하게 되면 리프 노드가 삭제 되었을 때의 조건으로 변한다
- 10 삭제, Inorder Predecessor 인 18을 찾아 서로의 Key 를 교환
Case 3. 삭제할 Key k 가 내부 노드에 있고, 노드에 Key 개수가 최소 Key 개수만큼,
노트의 자식 Key 개수도 모두 최소 Key 개수인 경우
삭제할 Key k 가 있는 노드도 최소, 자식 노드들도 최소의 Key 개수를 가지므로, k 를 삭제하면 트리의 높이가 줄어들어 재구조화가 일어난다
1. k 를 삭제하고, k 의 양쪽 자식을 병합하여 하나의 노드로 만든다
2. k 의 부모 Key 를 인접한 형제 노드에 붙이고, 이전에 병합했던 노드를 자식 노드로 설정한다
3-1. 만일 새로 구성된 인접 형제 노드의 Key 가 최대 Key 개수를 넘어갔다면, 삽입 연산의 노드 분할 과정 수행
3-2. 만일 인접 형제 노드가 새로 구성되더라도 원래 k 의 부모 노드가 최소 Key 개수보다 작아진다면 2번 과정부터 다시 수행
1) 14 삭제, 양쪽 자식 노드를 병합하고 14 삭제
2) 부모 Key 인 10을 형제 노드에 붙이고, 이전에 병합한 자식 노드를 왼쪽 자식으로 가져온다
(이거 예제 사진이 잘못 된 거 같은데 10 대신 20 이라고 생각하고 진행)
3) 10 이 포함된 노드의 Key 가 최대를 넘어갔기 때문에 노드 분할 수행하여 완성
다른 삭제 예시
1) 17 삭제, 연산을 수행하다 보면 17의 부모 노드 Key 가 최소 Key 개수 이하로 내려간다
17의 부모 노드를 기준으로 B-Tree 정렬하여 완성
