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. 멀티캐스트 트리
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
            1. 자료구조
            2. 자료구조 종류
        1.   선형 자료구조 (리스트 등)
        2.   비선형 자료구조 (트리,그래프)
          1.   그래프
          2.   트리
            1.   1. 트리
                2. 트리 용어
                3. 트리 종류
                4. 이진 트리
                5. 이진 탐색 트리
                6. 스패닝 트리
                7. 트리 순회
                8. B 트리
                9.
                10. 멀티캐스트 트리
        3.   기타 자료구조
        4.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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