[박혜웅] B Tree (balanced tree)

• balanced tree

  • 루트노드로부터 모든 자식노드의 길이가 비슷한 트리

    • 모든 잎노드의 높이 차이가 1이하인 트리
  • 높이가 낮아지므로, 탐색속도가 빨라진다.
  • 모든 노드에 데이타 저장 (색인에 사용)

 

• B Tree 의 종류

  • B tree

    • 모든 노드는 차수*(1/2) 이상의 자식노드를 보유
    • 저장효율 50%

  • B+ tree: 자료저장에 사용

    • 잎노드를 순회하면, 데이터의 순회가 간단하므로
    • 저장효율 50%

  • B* tree: B트리보다 저장효율이 높음

    • 오버플로우 발생시, 노드를 분할하지 않고 근접노드로 데이타를 이용하므로
    • 저장효율 66%

 

• B^*트리의 특징

  • 이웃 노드들이여유가 있으면, 분할을피하면서 키의 일부분을 이웃노드로 옮긴다.
  • 저장효율 66%(2/3)

  • 갱신비용이 많이 듬. 

     

• B⁺트리의 특징

  • 잎 노드에만 데이타 저장

    • 순차 탐색이 가능. 자료저장에 사용
  • 저장효율 50%

 

• B+트리의 구조