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)은 사용 못함

트리
   1. 트리   2. 트리 용어   3. 트리 종류   4. 트리 순회   5. 스패닝 트리   6. 이진 트리   7. 이진 트리 종류   8. 이진 탐색 트리   9. B 트리 (균형 트리)   10. 이진 힙   11. 멀티캐스트 트리   12. 결정 트리  


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