균등한 응답속도를 위한 탐색 트리, B-Tree

    B-Tree의 개요

    B-Tree의 개념

    - 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조

    - 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 자료구조의 일종

     

    - 대부분의 이진 트리는 항목이 삽입될 때 하향식으로 구성되지만 B-트리는 상향식으로 구성됨.
    - B는 Balanced의 의미이며, leaf node가 한쪽 방향으로 쏠리는 현상이 적음
    - B-Tree 에서 B를 Bi로 인식하는 사람들이 많으나, Balanced이다. 일반적인 트리와 다르게 자식노드가 3개 이상이 될 수 있기 때문이다.

    B-Tree의 특징

    1. 각 노드는 1/2이상 채워져야 하며 모든 리프 노드(leaf node)는 같은 레벨 (균형 트리)
    2. 탐색, 추가, 삭제는 루트 노드(root node)로 부터 시작
    3. 노드 내 값은 오름차순을 유지
    4. 공백이거나 높이가 1이상인 m-원 탐색 트리(m-way search tree)

     

    B-Tree의 장단점

    장점

    1. 삽입, 삭제 후에도 균형 트리 유지
    2. 효율적인 알고리즘 제공
    3. 저장 장치의 효율성
    4. 균등한 탐색 속도 보장 가능

     

    단점

    1. 노드의 삽입과 삭제 시 트리의 균형을 유지하기 위해 복잡한 연산(재분배, 합병) 필요
    2. 순차탐색 시에 중위(indorder) 순회로 비효율적임

    - B+ 트리 구조에서 리프 노드간의 linked list로 순차 탐색 효율이 향상

     

    B-Tree의 구조

    B-Tree의 구조

    - 기존 이진트리는 자식노드가 2개까지만 허용되는 것과 달리 B-Tree는 2개 이상이 가능한 구조이다.

    B-Tree의 Insert 절차

    B-tree 노드 삽입 절차, 새로운 값인 59가 추가된 경로를 설명하는 구조

    1. 기존 노드에 59가 신규로 추가됨
    2. 59가 추가되면서 middle value가 65로 변경되며, 새로운 노드들이 형성됨

     

    B-Tree의 활용

    - DBMS나 파일시스템의 인덱스 자료구조로 활용 (B+tree, B*tree로 발전)

    - 검색엔진, 패턴 매칭 등 성능이 일정하면서 빠른 탐색이 요구되는 분야에 활용

     

    키워드

    균형트리, 중위순회, root node, leaf node

     

    참고자료

    https://ko.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC

    댓글

    Designed by JB FACTORY