[Data Structure] B Tree, B+ Tree

B Tree

• 이진트리의 확장 버전
• 더 많은 수의 자식을 가질 수 있게 일반화시킨 트리구조
• 모든 leaf노드들이 같은 레벨을 가질 수 있도록 자동으로 균형을 맞춤
• 정렬된 순서 보장, 멀티레벨 인덱싱을 통한 빠른 검색 → 데이터베이스와 파일 시스템에서 널리 사용
• 규칙
  • 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있다.
  • 노드에는 최대 M-1 개부터 [M/2]-1 개의 키가 포함될 수 있다.
  • 노드의 키가 x개라면 자식의 수는 x+1개다.
  • 최소차수: 자식 수의 하한값. 최소차수가 t라면 M = 2t-1을 만족
  • EX. 최소차수 t가 2라면, 3차 B트리이며, key의 하한은 1개이다.
• 탐색
  • 루트 노드부터 하향식으로 검색
  • 찾고자하는 값 k가 key들 사이에 있다면 거기의 자식 노드로 내려감
  • 리프노드까지 갔는데도 없으면 탐색 실패
• 삽입
  1. 분할 X: 맞는 위치에 넣음
  2. 분할 O: 노드가 담을 수 있는 최대 key 개수를 초과하는 경우
     • 왼쪽 키들은 왼쪽 자식으로, 오른쪽 키들은 오른쪽 자식으로 분할
     • 만약 부모 노드 역시 가득 차게 되면, 부모노드에서도 이 과정을 반복
• 삭제
  1. 삭제할 key k가 leaf노드에 존재하는 경우
     • 다른 노드에 영향을 주지 않으므로 단순 삭제
  2. 현재 노드의 key 개수가 최소 key 개수보다 큰 경우
     • 다른 노드에 영향을 주지 않으므로 단순 삭제
  3. 왼쪽 또는 오른쪽 형제 노드의 key가 최소 key 개수 이상인 경우
     • 부모 key 값을 자식으로 변경
     • 최소 키 개수 이상의 키를 가진 형제 노드가 왼쪽 형제라면 가장 큰 값을, 오른쪽 형제라면 가장 작은 값을 부모 key로 대체
  4. 삭제할 key k 가 내부 노드에 있고, 노드와 노드 자식의 key가 모두 최소개인 경우

B+ Tree

• B Tree의 변형 구조
• index와 순차 데이터(leaf 노드로 구성)로 구성. index의 key 값은 leaf에 있는 key 값을 직접 찾아가는데 사용
• 
• 장점
  • 블럭 사이즈를 더 많이 이용 가능(Key 값에 대한 하드디스크 엑세스 주소가 없기 때문)
  • leaf 노드끼리 연결리스트로 연결되어 있어서 범위 탐색에 매우 유리
• 단점
  • B Tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+ Tree는 무조건 leaf노드까지 내려가봐야 함

B Tree & B+ Tree

B Tree는 각 노드에 데이터가 저장 B+ Tree는 index노드와 leaf노드로 분리되어 저장(또한, leaf노드는 서로 연결되어 있어서 임의접근이나 순차접근 모두 성능이 우수함)

• B Tree는 각 노드에 key와 data가 모두 들어가며, data는 disk block으로 포인터가 될 수 있다.
• B+ Tree는 각 노드에서 key만 들어가고 data는 모두 leaf노드에만 존재 -> 삽입, 삭제 모두 leaf노드에서 이뤄짐

---

참고링크

• ICPC 신촌 2022 겨울 알고리즘 캠프 - 트리
• https://github.com/seohyun319/CS_I/tree/main/01. DataStructure
• https://github.com/seohyun319/CS_I/blob/main/01. DataStructure/10_B Tree %26 B%2B Tree.md