[DataStructure] B+Tree

B+Tree알고리즘이란

• B+Tree알고리즘에 대해 알아보기 전에 왜 사용하는지 알아보자
  
  

도입배경과 B-Tree

• B-Tree는 널리 쓰이는 인덱스 자료구조인데 이진 트리르 확장한 자료구조이다.
• B-Tree는 노드의 key마다 data를 가지는데, B+Tree는 리프노드에만 data를 저장한다.
• B+트리는 데이터베이스 인덱스 및 파일 시스템에서 널리 사용되는 자료구조인 B트리의 단점을 개선하기 위해 도입되었다.
• B트리의 공간활용문제 :
  • b트리는 내부 노드에도 데이터와 포인터를 함께 저장하므로 리프 노드에
• 리프노드가 아니라면 자식의 Key값을 저장한다.
• 리프노드의 부모 key는 리프노드의 첫번쨰 key보다 작거나 같을 수 있으므로 중복되는 key가 발생할 수 있다.
• 또한 리프노드는 연결리스트의 형태로 되어 있어 인접한 다음 노드에 바로 접근가능하다 .

B+ tree 설명

• 이름처럼 트리 구조이다. 이진탐색트리랑 개념적으로 비슷함
  key값으로 정렬되고, 자녀노드가 여러개이다.
• 각각의 노드가 메모리가 아닌 디스크에 있음
• 더 추가하다 보면 tree depth가 더 늘어남
• 대부분의3-4 depth정도로 오는 데이터를 처리할 수 있음
  
  

쓰기

• B+tree 쓰기는 여러 Disk writer이 필요할 때가 있음
• 중간에 crash하는 경우 데이터가 corruption 될 수 있음
• 대부분은 write-ahead Log라는 파일에 어떤 write을 할 것인지미리 써놓고 B+tree 업데이트를 시작함
  
  

추가적으로 형제간의 포인터가 있다는 것이 특징이다.

B+ Tree에서 수행되는 주요 연산에 대해 알아보자

1. 검색(Search)
2. 삽입(Insert)
3. 삭제(Delete)
   
   
   

검색연산

1. 루트 노드부터 시작하여 key를 비교
2. 내부 노드에서는 key 값과 비교하여 어느 자식으로 내려갈지 결정
   • 예: [10 | 20 | 30] → key=25는 20~30 사이 → 두 번째 자식으로
3. 리프 노드에 도달할 때까지 반복
4. 리프 노드에 도달하면:
   • key와 일치하는 값이면 → 해당 데이터를 반환
   • 일치하지 않으면 → 검색 실패
5. 범위 검색의 경우:
   • 시작 key를 찾은 후 → 리프 노드의 연결 리스트를 따라가며 순차 탐색

삽입연산

1. 삽입 위치 탐색 - 검색 연산과 마찬가지로 리프 노드까지 탐색하여 삽입 위치 찾음
2. 삽입 수행 - 리프 노드의 key 리스트에 정렬된 위치로 key-value 삽입
3. 오버플로우(Overflow) 발생 여부 확인
   • 리프 노드가 가득 찬 경우(key 수 > 최대 key 수) → 노드를 분할(Split)
4. 노드 값이 넘친 경우에 Split(분할) 수행
   • key를 절반 기준으로 분리 → 새 리프 노드 생성
   • 부모 노드에 중간 key 값을 올림
   • 리프 노드끼리는 연결 리스트로 연결 유지
5. 재귀적 Split
   • 부모 노드도 가득 찬 경우 → 상위 노드로 재귀적으로 Split
   • 루트 노드까지 Split되면 → 트리 높이가 1 증가

삭제 연산

1. 삭제할 key 위치 탐색
   • 검색처럼 리프 노드까지 내려감
2. 리프 노드에서 key 제거
3. 언더플로우(Underflow) 확인
   • 노드의 key 수가 최소 허용 개수 미만이면 처리 필요
4. Borrow or Merge
   • 형제 노드에서 key 하나 빌리기(Borrow) → 부모 key 일부 업데이트
     
   • 불가능하면:
     • 형제 노드와 병합(Merge) → 부모 key 하나 삭제됨 → 상위 노드 언더플로우 체크
       
5. 재귀적 조정
   • 부모 노드에서도 언더플로우 발생 시 → 재귀적으로 위로 전파
   • 루트 노드까지 병합되면 → 트리 높이 1 감소 가능