본문 바로가기

자료구조 & 알고리즘/트리(Tree)

[박혜웅] 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+트리의 구조

 

'자료구조 & 알고리즘 > 트리(Tree)' 카테고리의 다른 글

[강한구] Binary Heap  (0) 2010.03.31
[박혜웅] digital tree  (0) 2010.03.28
[박혜웅] 트리 (tree)  (0) 2010.03.28
[강한구] 이진트리  (0) 2009.07.13
[강한구] 트리 기초개념  (0) 2009.04.01