Gidhub BE Developer

B+ 트리

2018-06-13
goodGid
파일처리

B+ 트리

  • 순차 탐색의 성능 향상 (B-트리의 순차 탐색 보완)

  • 인덱스 세트
    • 리프 이외의 노드
  • 순차 세트
    • 리프 노드

B+ 트리의 특징

3차 B+ 트리

내부 노드 : 최소 upper_bound(m/2) - 1 = 1 개   / 최대 m - 1  = 2 개 키 값
리프 노드 : 최소 upper_bound(m/2) = 2 개   / 최대 m = 3 개 키 값

B+ vs B 트리 차이

  • 인덱스 세트와 순차 세트의 구분이 있으며 구조가 다름
    • 인덱스 세트는 리프 노드에 있는
      키 값을 찾는 경로로만 이용 (키 값만 저장)
    • 인덱스 세트에 있는 키 값은 순차 세트에 다시 나타남

  • 순차 세트는 실제 데이터를 찾는데 이용

  • 순차 세트의 모든 노드가 연결 리스트로 연결

B+ 트리 삽입

  • B 트리의 리프 노드에 삽입하는 것과 유사

  • 차이점
    리프 노드 분할 시 중간 키 값의 복사본이 부모 인덱스 노드로 올라감

B+ 트리 삽입 예

B+ 트리 삭제

  • B 트리와 유사

  • 차이점
    • 키 값의 삭제는 리프 노드에서만 수행
    • 인덱스 세트의 키 값을 삭제할 필요가 있는 경우에는
      삭제하지 않고 분리자로 이용
  • B 트리 : 중간 or 리프가 삭제
    B+ 트리 : 리프노드만 삭제

B+ 트리 삭제 예

B+ 트리 성능

  • 특정 키 값 검색

    • 장점
      인덱스 노드는 레코드 포인터를 저장하지 않으므로
      노드 내 공간이 절약
      –> 인덱스 노드에 더 많은 키값이 저장
      –> 트리 레벨이 낮아질 수 있음

    • 단점
      검색이 항상 리프 노드까지 내려가야만 종료

  • 순차 검색은 리프 노드에서 연결 리스트를 순회하므로 효율적

  • B+ 트리 = 직접 처리 + 순차 처리를 모두 필요로 하는 곳에서 효율적

B+ 트리 관련 참고 자료

Recommend

Index