1. 코드에서 B-Tree 방식
1-1. 조회 (Top-Down)
- 기존 개념에서는 top-down 방식
- 코드 구현 방식에서도 top-down 방식
→ 조회 알고리즘
- 이중 for문으로
- 안쪽 for문에서 현재 노드에 찾는 키가 있는지 탐색하고
- 바깥 for문에서 찾는 키가 없다면 현재 노드를 자식노드로 바꿈
1-2. 삽입
- 기존 개념에서는 bottom-up 방식
- 코드 구현 방식에서는
- 리프노드 찾는 조회에서 top-down 방식
- 리프노드에서 삽입 후 노드 넘치는걸 확인해서 분할할때는 bottom-up
→ 삽입 알고리즘
- 루트 노드에서부터 삽입을 시도하고
- 현재 노드가 리프노드라면
- 삽입하고
- 만약 노드가 넘치면 노드를 분할하는 작업 실행
- 현재 노드가 리프노드가 아니라면
- 재귀적으로 자식노드를 매개변수로 넣어서 현재 함수 실행함
- 만약 재귀 밖으로 나온 노드가 넘치면 분할하는 작업 수행
- 현재 노드가 리프노드라면
1-3. 삭제 (Top-Down)
- 기존 개념에서는 bottom-up 방식
- 코드 구현 방식에서는 top-down 방식
→ 삭제 알고리즘
- 루트에서부터 삭제 시도 (이때 deleteValFromNode)
- 현재 노드에서 삭제할 키가 있다면
- 현재 노드가 리프노드일때
- 바로 삭제
- 리프 노드가 아닐 때 (이때 deleteInnerNode 실행됨)
- 내부 노드에서 키를 삭제
- 선임자나 후임자의 키 개수가 최소범위보다 많을 때
- 삭제할 키를 선임자나 후임자로 키 내용을 변경하고
- 삭제 키를 선임자나 후임자로 변경후 현재 노드의 자식 노드부터 변경된 삭제키를 삭제하도록 함 (deleteValFromNode(cessor,cur_node->child[cur_node_pos]))
- 선임자와 후임자 모두 키 개수가 최소범위일 때 (이때 mergeChildNode 실행됨)
- 현재 노드의 삭제할 키를 왼쪽 자식 노드 가장 오른쪽에 넣음
- 오른쪽 자식 노드의 키를 왼쪽 자식 노드 키로 옮김
- 오른쪽 자식노드의 자식들을 왼쪽 자식 노드의 자식 배열로 옮김
- 현재 노드의 삭제할 키를 키 재배열로 삭제시킴
- 현재 노드의 자식노드 중 오른쪽 자식 노드는 왼쪽 자식 노드와 합쳐져서 없으므로 자식 배열 재배열을 통해 해당 키의 오른쪽 자식 노드를 삭제함
- → mergeChildNode끝나고
- 삭제키를 자식노드에 병합했으므로 현재노드의 자식노드로부터 삭제키를 삭제하도록 함 (deleteValFromNode(deletion_for_merge, cur_node->child[cur_node_pos]);)
- 선임자나 후임자의 키 개수가 최소범위보다 많을 때
- 내부 노드에서 키를 삭제
- 현재 노드가 리프노드일때
- 현재 노드에서 삭제할 키가 없다면
- 현재 노드가 리프노드일때
- 삭제할 키가 없다는 문구 출력 후 종료
- 리프노드가 아닐 때
- 재귀적으로 자식노드를 매개변수로 넣어서 현재 함수(deleteValFromNode) 실행
- 현재 노드가 리프노드일때
- (항상 위에 작업이 끝나면 이 부분 확인함) 현재 노드의 자식 노드 키 개수가 최소값보다 적을 때 (이때 balanceNode 실행됨)
- 오른쪽 또는 왼쪽 형제에게 키를 빌릴 수 있으면 키 빌리고 현재 노드의 최소값 문제 해결
- 형제도 키가 여유가 없는 상황이면 부모에게 빌리기 (이때 mergeNode 실행됨)
- 항상 왼쪽 형제와 현재노드를 병합함
- 왼쪽 형제 노드의 마지막 키 바로 오른쪽에 부모에게 빌린 키 넣음
- 왼쪽 형제 노드에 현재 노드(부모의 오른쪽 자식 노드)의 모든 키 옮기
- 현재 노드 삭제
- 왼쪽 형제 노드에 현재 노드의 모든 자식 노드 옮기기
- 부모노드에서 빌린 키 부분 자리가 비어있으므로 key 재배열로 정리함
- 부모노드에서 자식 하나가 사라졌으므로(현재 노드가 삭제되어서) 자식 배열도 재배열
- 현재 노드에서 삭제할 키가 있다면
2. 알고리즘 절차 정리
2-1. 구조체
0. BTreeNode
- leaf 여부
- key 담을 배열 (한 개 더 넘치게 설정, 노드가 넘칠때를 대비해서)
- key 개수
- 자식노드 담을 배열 (한 개 더 넘치게 설정, 노드가 넘칠 때 자식노드도 하나 넘쳐서)
- 자식노드 개수
2-2. 조회 관련 함수
0. searchNode
- 매개변수: 루트노드, 찾을 키(val)
- 간단 설명: 루트노드부터 자식노드까지 차례대로 키(val) 찾음
- 이중 반복문
- 가장 안쪽 반복문
- 노드의 키 개수만큼 키를 하나씩 val과 비교
- 만약 노드의 특정키와 val이 같다면 그대로 문구 출력 후 종료
- 만약 val이 노드의 특정 키보다 작다면 바로 break → 그러면 바로 그 특정 키 인덱스와 동일한 자식노드(해당 키의 왼쪽 자식 노드)로 조회해야하기 때문
- for문이 다 지나도록 if문에 하나도 안걸리면 인덱스는 자동으로 cnt_key와 동일해지므로 가장 오른쪽 자식노드를 조회하게 됨
- 가장 바깥쪽 반복문
- 인덱스 변수 지정(pos)
- 안쪽 반복문에서 pos 값을 정하고 나옴 → pos값은 몇번째 자식 노드를 탐색할지 정함
- 만약 현재 노드가 리프노드이면 반복문 종료 후 바깥에서 키를 찾지 못했다고 출력
- 리프노드가 아니면 노드(level)를 자식노드(pos위치 자식노드)로 지정해서 자식노드를 안쪽 반복문에서 탐색하도록 함
2-3. 삽입 관련 함수
0. insert
- 매개변수: 넣을 키(val)
- 간단 설명: 키를 insertNode함수를 이용해서 넣음
- 루트가 없으면 루트를 생성하고 val를 넣음
- 루트가 있으면 insertNode에 매개변수 root와 val를 넣고 실행시킴
- 루트의 첫번째 키부터 탐색해서 val를 넣도록 매개변수 지정
0. insertNode
- 매개변수: 부모노드에서 탐색할 키 위치, 삽입할 키(val), 현재 노드, 부모노드
- 간단 설명: 리프노드이면 키를 삽입하고 아니면 재귀적으로 자식노드로 들어감
- 현재노드 키 위치(pos) 변수 지정
- 현재 노드에서 키 탐색
- 동일한 키가 있으면 중복이므로 오류 문자 출력 후 현재 노드 반환하여 종료 → (재귀함수로 나중에 루트가 사라질 수도 있어서 루트 노드를 항상 반환하도록함, 이때 루트가 아니어도 이미 재귀를 통해 내부 노드로 들어갔을것이고 내부 노드에서 나오면서 노드가 계속 바뀌면서 최종적으로 루트 노드가 됨)
- 현재노드 키가 val보다 크면 반복문 종료 → pos는 딱 val보다 큰 키의 인덱스가 됨 → 이 뜻은 그 키의 왼쪽 자식 노드(더 작은 키가 저장되어 있는 자식노드) 위치와 동일함
- 아무 조건문에 걸리지 않고 반복문이 끝나면 pos는 자연스럽게 해당 노드의 가장 오른쪽 자식노드(가장 큰 키가 저장되어 있는 자식노드)의 위치가 됨
- 리프노드가 아니면
- 현재노드의 자식노드(pos위치)를 현재노드로, 현재노드를 부모노드로 지정한 현재 함수 insertNode를 다시 실행 후 반환값을 node로 저장 → 더 아래의 자식 노드로 들어가면서 리프 노드까지 도달하도록함
- 위의 재귀 함수가 끝난 후 반환된 현재 노드의 키 개수가 초과하면 분리함수 splitNode 실행하고 반환값을 node로 저장
- 리프 노드일 때
- 삽입할 키가 들어갈 자리를 만들기 위해 pos 기준 오른쪽 키들을 한칸씩 오른쪽으로 옮김
- 자식들도 부모 키 위치를 따라가도록 pos 기준으로 오른쪽 자식 위치를 한칸씩 오른쪽으로 옮김
- 현재 노드 pos 위치에 삽입할 값(val)를 넣음
- 현재 노드 키 개수 증가시킴
- 만약 현재 노드의 키 개수가 넘치면 분리함수 splitNode를 실행하고 반환값을 node로 저장
- node 반환 → 최종적으로 이 노드가 루트가 됨
- 이걸 반환하는 이유는 재귀 함수에서 나올때 현재 노드가 무엇인지 알 수 있도록 하는 이유가 있고
- 또, 삽입 과정에서 splitNode를 하면서 새로운 루트노드가 생길 수 있기 때문에 함
0. splitNode
- 매개변수: 현재노드가 부모노드의 몇번째 자식인지(pos), 현재노드, 부모노드
- 간단 설명: 현재 노드가 넘칠때 가운데 키를 부모 노드로 승진
- 현재 노드 중앙키 구하고 오른쪽 노드를 새로 만듬 → 현재 노드가 왼쪽 노드가 됨
- 오른쪽 노드에 현재 노드 절반 기준 오른쪽 키를 옮겨줌
- 이 과정에서 현재노드에 중앙키가 항상 있음
- 현재 노드가 리프가 아니라면 자식 노드도 오른쪽 노드에 옮겨줌
- 만약 현재 노드가 루트라면
- 부모노드가 없으므로 새로운 부모 노드 생성
- 부모 노드에 중앙키(현재 노드의 가장 오른쪽 키) 승진
- 부모 노드 자식에 현재노드와 오른쪽 노드 포인터 저장
- 현재 노드가 루트가 아니라면
- 원래 있던 부모 노드에 pos 부분 자리 비우기 위해 pos 기준 오른쪽 키를 한칸씩 오른쪽으로 옮기기
- 자식 배열도 똑같이 오른쪽으로 한칸씩 옮기기
- 부모 노드 pos자리에 중앙키 넣고 오른쪽 노드를 자식노드로 추가
2-4. 삭제 관련 함수
0. delete
0. deleteValFromNode
0. deleteInnerNode
0. overrideWithSuccessor
0. findSuccessor
0. overrideWithPredecessor
0. findPredecessor
0. mergeChildNode
0. balanceNode
0. borrowFromRight
0. borrowFromLeft
0. mergeNode
3. 구현 코드
- 해당 코드에 주석 추가함
https://github.com/vinyl-bin/btree_implementation
** 출처
**관련 자료
- B-Tree 시뮬레이션 사이트 https://www.cs.usfca.edu/~galles/visualization/BTree.html
- B-Tree top-down 방식 https://velog.io/@mongle/Data-structure-B-tree-B-tree
- python B-Tree 코드 https://blog.naver.com/nabilera1/223457915464
**핵심 자료
하루살이