문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류: 자료 구조]] == 개요 == [[전산 과학]]에서 '''B-트리'''(B-tree)는 [[데이터베이스]]와 [[파일 시스템]]에서 널리 사용되는 [[트리 구조|트리 자료구조]]의 일종으로, [[이진 트리]]를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효율적이다. B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 [[시간 복잡도#대수 복잡도|대수 시간]]으로 할 수 있다. 대부분의 [[이진 트리]]는 항목이 삽입될 때 하향식으로 구성되는 데 반해, B-트리는 일반적으로 상향식으로 구성된다. n개의 키 (s1,s2,s3...,sn)가 있는 한 노드를 생각해 보자. 키집합은 정렬되어 있다고 한다. (즉, s1<s2<s3...<sn) 그 노드는 n+1자식노드를 가리키는 포인터로 구성된다. 즉, t0,t1,t2...tn. B-트리의 기본 개념은 내부 노드의 자식 노드의 수가 미리 정해진 범위 내에서 변경가능하다는 것이다. 항목이 삽입되거나 삭제될 때, 내부 노드는 해당 범위의 자식 노드의 수를 만족시키기 위해 분리되거나 혹은 다른 노드와 합쳐지게 된다. 자식 노드의 수가 일정 범위 내에서만 유지되면 되므로 분리 및 합침을 통한 재균형 과정은 다른 [[자가 균형 이진 탐색 트리]]만큼 자주 일어나지 않지만, 저장 공간에서의 손실은 있게 된다. 자식 노드의 최소 및 최대수는 일반적으로 특별한 구현에 대해서 결정되어 있다. 예를 들어, 2-3 B-트리(혹은 단순히 2-3 트리)에서 각 내부 노드는 2 또는 3개의 자식 노드를 가질 수 있다. 만약 허용되지 않은 수의 자식 노드를 가질 경우, 해당 내부 노드는 부적절한 상태에 있다고 한다. B-트리는 노드 접근시간이 노드에서의 연산시간에 비해 훨씬 길 경우, 다른 구현 방식에 비해 상당한 이점을 가지고 있다. 이는 대부분의 노드가 [[하드디스크]]와 같은 [[2차 저장장치]]에 있을 때 일반적으로 일어난다. 각 내부 노드에 있는 자식 노드의 수를 최대화함으로써, 트리의 높이는 감소하며, 균형맞춤은 덜 일어나고, 효율은 증가하게 된다. 대개 이 값은 각 노드가 완전한 하나의 디스크 블록 혹은 2차 저장장치에서의 유사한 크기를 차지하도록 정해진다. <!--Rudolf Bayer을 루돌프 바이엘로 했다. 독일계 의약품사에도 Bayer는 바이엘로 읽으니까요 // 저(Iceager)는 외래어 인명 표기 용례집에서 인명 'Bayer'를 '바이어'로 표기하는 것을 참조하여 '바이어'로 옮겼다. --> B-트리의 창시자인 [[루돌프 바이어]]는 'B'가 무엇을 의미하는지 따로 언급하지는 않았다. 가장 가능성 있는 대답은 리프 노드를 같은 높이에서 유지시켜주므로 균형잡혀있다(balanced)는 뜻에서의 'B'라는 것이다. '바이어(Bayer)'의 'B'를 나타낸다는 의견도, 혹은 그가 일했던 보잉 과학 연구소(Boeing Scientific Research Labs)에서의 'B'를 나타낸다는 의견도 있다. == 노드 구조 == B-트리의 노드는 대개 항목과 자식 포인터의 [[순서 집합]]으로 표현된다. 루트 노드를 제외한 모든 노드는 임의의 수 L, U(L<U)에 대해 최소 L 항목, 최대 U 항목을 가지고 있으며, 최대 U+1개의 자식 포인터를 가지고 있다. 모든 내부 노드에서, 자식 포인터의 수는 언제나 항목 개수보다 하나가 많다. 모든 리프 노드가 동일한 높이에 있기 때문에, 노드는 일반적으로 리프 노드인지 내부 노드인지 판별하는 수단을 가질 이유가 없다. 각 내부 노드의 항목은 [[부트리]]를 나누는 구분 값이다. 예를 들어, 어떤 내부 노드가 3개의 자식 노드(혹은 부트리)를 가지고 있다면, 그 내부 노드는 두개의 구분 값이나 항목 ''a''<sub>1</sub>과 ''a''<sub>2</sub>를 가지고 있어야 한다. 가장 왼쪽 부트리에 있는 모든 값은 ''a''<sub>1</sub>보다 작으며, 가운데 부트리의 모든 값은 ''a''<sub>1</sub>와 ''a''<sub>2</sub>의 사이에 있으며, 가장 오른쪽 부트리의 모든 값은 ''a''<sub>2</sub>보다 크게 된다. == 알고리즘 == === 탐색 === 탐색은 일반적인 방식, 즉 [[이진 탐색 트리]]와 동일한 방식으로 수행된다. 루트에서 시작하여, 하향식으로 탐색 대상의 값을 구분 값과 비교하며 자식 포인터를 찾아나가는 과정으로 진행한다. === 삽입 === 부적절한 상태에 있는 노드란, 그 노드에 허용된 자식 노드의 숫자가 허용된 범위 밖인 노드를 의미한다. # 삽입될 노드가 어느 위치로 삽입될지 찾아 해당 부모 노드에 삽입한다. # 부적절한 상태의 노드가 없다면, 삽입 과정을 종료한다. # 만약, 어떤 노드가 너무 많은 항목을 가지고 있다면, 이를 두 노드로 분리한다. 이 과정을 반복적으로 트리를 타고 올라가며 진행한다. 만약 루트 노드를 분리하였다면, 새로운 루트 노드를 만든다. == 참고 == ''L''을 허용된 자식 노드의 최소수라고 하고 ''U''를 최대수라고 하자. 그러면, 각 노드는 항상 ''L''과 ''U'' 사이의 자식 노드를 가지게 된다. 단, 예외로 루트 노드의 경우 ''2''에서 ''U''사이의 어느 수의 자식 노드도 가질 수 있다. 다른 말로, 루트 노드는 최소수에서 예외로, 자신만의 최소수 ''2''를 가진다는 것이다. 이는 트리가 적은 수의 항목을 가지는 것을 가능하게 한다. 하나의 자식 노드를 가지는 루트 노드는 전혀 의미가 없는데, 이는 해당 자식 노드에 연결된 부트리를 직접 루트 노드에 연결하면 되기 때문이다. 자식 노드를 가지지 않은 루트 노드 역시 불필요한데, 이는 항목이 없는 트리는 일반적으로 루트 노드조차 없는 것과 같기 때문이다. B-tree 문서로 돌아갑니다.