B-Tree, B-tree   B 트리

(2020-02-20)

Balanced Tree, 균형잡힌 트리 구조, 균형 트리

1. B 트리 (B-Tree, Balanced Tree)이진 탐색 트리를 보다 일반화시킨 트리 자료구조를 말함
     - 데이터베이스파일시스템에 널리 쓰이는 자료구조

  ㅇ 성능 및 공간 활용을 위해 이진 탐색 트리에 제약조건을 부가시켜 확장한 것
     - 트리가 항상 균형을 유지 (Balanced)
        . 루트(root)와 리프(leaf) 간의 거리를 가능한 일정하게 유지하려 함
           .. 따라서, 데이터량이 증가해도 검색 성능이 안정적 임
        . 트리 깊이가 3~4 정도 수준으로 일정 함
        . 데이터들이 항상 정렬 상태를 유지 함
     - 삭제로 인한 공간 낭비 최소화


2. DBMS에서 B-Tree (B+ tree)트리 구조의 리프 노드(leaf node)에 만 키 값을 저장

  ㅇ 특징
     - 특정 레코드 검색 시에,
        . 정확한 인덱스 키 값, 패턴 매칭, 부분 매칭, 범위 매칭 등으로도 검색 가능
     - 순차 접근 및 임의 접근 모두 가능
     - 색인순차접근방식과는 달리, 색인 키를 갱신하더라도 성능 저하가 발생하지 않음
     - 인덱스화된 컬럼의 원래 값을 변형시키지 않고, 
        . 인덱스 자료구조 내에서 항상 정렬된 상태를 유지함
     - 데이터량이 증가해도 검색 성능이 안정적 임
     - 등호(=) 조건 뿐만 아니라 부등호(<,>,<=,>=)를 사용한 검색 조건에서도 사용 가능


[트리] 1. 트리 2. 트리 용어 3. 트리 종류 4. 이진 트리 5. 이진 탐색 트리 6. 스패닝 트리 7. 트리 순회 8. B 트리 9. 10. 멀티캐스트 트리

 
        최근수정     요약목록     참고문헌