B-Tree, B-tree   B 트리

(2021-09-26)

Balanced Tree, 균형잡힌 트리 구조, 균형 트리, B+ tree, B+ 트리


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

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

  ㅇ 특징(성질)
     - 하나의 노드에 여러 엔트리(값)들을 갖을 수 있음
     - 노드 내부 엔트리들은 항상 정렬된 상태를 유지
     - 한 노드의 자식 노드(서브 트리)의 갯수는, (자신의 엔트리 갯수) + 1 개를 갖음
        . 예를들면, 루트 노드는 적어도 2개의 서브 트리를 갖음
     - 자식 노드(서브 트리)들이 정렬된 상태를 유지 (좌에서 우로 순서 정렬)
     - 각 노드가 최소 엔트리 개수를 나타내는 minimum 값을 지니고,
       각 노드가 갖을 수 있는 최대 엔트리 개수는 minimum의 2배임
     - 모든 리프 노드트리 깊이는 항상 같음


2. DBMS에서 B-Tree (B+ tree)
  
  ㅇ B 트리의 수정 버전
     - 트리 구조리프 노드(leaf node)에 만 키 값을 저장시킴
     - 여기서 리프 노드는, 실제 저장된 레코드주소 값을 갖음

  ㅇ 특징
     - 특정 레코드 검색 시에,
        . 정확한 인덱스 키 값, 패턴 매칭, 부분 매칭, 범위 매칭 등으로도 검색 가능
     - 단, B-Tree 그 자체로는,
        . 전체 일치,전방 일치 만 가능하고, 중간 일치,후방 일치인덱스 사용 못함
        . 또한, 키 값이 변형되도(함수,연산 결과로 검색하는 경우) 인덱스 사용 못함 
     - 즉, B 트리는, 인덱스 컬럼의 원래 값을 변형시키지 않고 그대로 사용하는 방식
        . 한편, Hash 방식 등에서는 값을 변행해서 인덱스화에 사용 
        . 비록, Hash 방식은 더빠른 검색이 가능하지만, 전방 일치 등이 불가능

     - 순차 접근 및 임의 접근 모두 가능
        . 색인순차접근방식과는 달리,
        . 색인 키를 갱신하더라도 성능 저하가 발생하지 않음
     - 즉, 데이터량이 증가해도 검색 성능이 안정적 임
        . 트리가 항상 균형을 유지 (Balanced) 하므로

     - 등호(=) 조건 뿐만 아니라, 부등호(<,>,<=,>=)를 사용한 검색 조건에서도 사용 가능
     - 단, 부정형(<>,!=,NOT IN)은 사용 못함



Copyrightⓒ written by 차재복 (Cha Jae Bok)
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"