B-트리

B-트리
유형	트리(데이터 구조)
발명된	1970년[1]
발명자	루돌프 바이어, 에드워드 맥크라이트
빅 O 표기의 시간 복잡도
알고리즘. 평균 최악의 경우 공간 O(n) O(n) 서치 O(log n) O(log n) 삽입 O(log n) O(log n) 삭제 O(log n) O(log n)

컴퓨터 과학에서 B-트리는 정렬된 데이터를 유지하고 검색, 순차적 액세스, 삽입 및 삭제를 로그 시간으로 허용하는 자체 균형 트리 데이터 구조입니다.B-트리는 2진수 검색 트리를 일반화하여 하위 ^[2]항목이 3개 이상인 노드를 허용합니다.다른 자체 밸런싱 바이너리 검색 트리와 달리 B-Tree는 데이터베이스 및 파일 시스템과 같이 비교적 큰 데이터 블록을 읽고 쓰는 스토리지 시스템에 매우 적합합니다.

기원.

B-Tree는 Boeing Research Labs에서 일할 때 대규모 랜덤 액세스 파일의 인덱스 페이지를 효율적으로 관리하기 위해 Rudolf Bayer와 Edward M. McCreight에 의해 발명되었습니다.기본적인 가정은 인덱스가 너무 커서 트리의 작은 부분만 메인 메모리에 들어갈 수 있다는 것이었다.바이엘과 맥크라이트의 논문 '대형주문지수 ^[1]구성 및 유지'는 1970년 7월 처음 배포됐으며 이후 악타 인포매티카에 ^[3]실렸다.

Bayer와 McCreight는 B가 무엇을 의미하는지 설명하지 않았다: Boeing, balanced, broad, bushy, 그리고 Bayer가 ^[4][5][6]제안되었다.맥크라이트는 "B-tree의 B가 무엇을 의미하는지 더 많이 생각할수록 B-tree를 ^[5]더 잘 이해할 수 있다"고 말했다.

정의.

Knuth의 정의에 따르면, 순서 m의 B-트리는 다음 ^[7]특성을 만족시키는 나무이다.

1. 각 노드에는 최대 m개의 자녀가 있습니다.
2. 모든 내부 노드에는 적어도 'm/2'의 자녀가 있습니다.
3. 리프 이외의 모든 노드에는 2개 이상의 하위 노드가 있습니다.
4. 모든 잎은 동일한 레벨로 나타나며 아무런 정보도 전달되지 않습니다.
5. 자녀가 k개인 리프 이외의 노드에는 k-1 키가 포함되어 있습니다.

각 내부 노드의 키는 하위 트리를 나누는 분리 값 역할을 합니다.예를 들어 내부 노드에 3개의 하위 노드(또는 하위 트리)가 있는 경우 2개의 키(a₁₂ 및 a)가 있어야 합니다.맨 왼쪽 서브트리의 모든 값은 a보다₁ 작습니다.중간 서브트리의 모든 값은 a와₂ a 사이입니다₁.맨 오른쪽 서브트리의 모든 값은 a보다₂ 커집니다.

내부 노드

내부 노드(내부 노드라고도 함)는 리프 노드와 루트 노드를 제외한 모든 노드입니다.일반적으로 요소 및 하위 포인터의 순서 집합으로 표시됩니다.모든 내부 노드에는 최대 U자녀와 최소 L자녀가 포함됩니다.따라서 요소의 수는 항상 자 포인터의 수보다1개 적습니다(요소의 수는 L-1과 U-1 사이).U는 2L 또는 2L-1 중 하나여야 합니다.따라서 각 내부 노드는 적어도 절반 이상 채워져 있습니다.U와 L의 관계는 2개의 하프풀노드를 결합하여 합법적인 노드를 만들고 1개의 풀노드를 2개의 합법노드로 분할할 수 있음을 의미합니다(한 요소를 부모에 밀어 올릴 수 있는 공간이 있는 경우).이러한 속성을 통해 B-트리에 새 값을 삭제하고 삽입할 수 있으며 트리를 조정하여 B-트리 속성을 유지할 수 있습니다.

루트 노드

루트 노드의 자식 수는 내부 노드와 상한이 동일하지만 하한이 없습니다.예를 들어 트리 전체에 L-1 요소보다 적은 경우 루트는 트리에서 하위 노드가 전혀 없는 유일한 노드가 됩니다.

리프 노드

Knuth의 용어로는 리프 노드는 어떤 정보도 전달하지 않습니다.리프보다 한 단계 위에 있는 내부 노드는 다른 작성자에 의해 "leaves"라고 불릴 수 있습니다.이 노드는 키(최대 m-1, 루트가 아닌 경우 최소 m/2-1)와 정보를 포함하지 않는 노드에 대한 포인터만 저장합니다.

깊이 n+1의 B-tree는 깊이 n의 B-tree보다 약 U배 많은 항목을 보유할 수 있지만 트리의 깊이에 따라 검색, 삽입 및 삭제 작업 비용이 증가합니다.균형 잡힌 나무와 마찬가지로 비용은 요소의 수보다 훨씬 더 느리게 증가합니다.

일부 균형 트리는 리프 노드에만 값을 저장하며 리프 노드 및 내부 노드에 대해 서로 다른 종류의 노드를 사용합니다.B-트리는 리프 노드를 제외한 트리 내의 모든 노드에 값을 유지합니다.

용어의 차이

B-tree에 관한 문헌은 ^[8]용어가 통일되어 있지 않다.

Bayer와 McCreight(1972년),^[3] Comer(1979년)^[2] 등은 B-트리의 순서를 비루트 ^[9]노드의 최소 키 수로 정의합니다.는, 키의 최대수가 명확하지 않기 때문에, 용어가 애매하다고 지적하고 있습니다.주문 3 B-tree는 최대 6키 또는 최대 7키를 보유할 수 있습니다.Knuth(1998)는 최대 자식 수(최대 ^[7]키 수보다 1개 많은 수)로 순서를 정의함으로써 이 문제를 회피합니다.

리프라는 용어도 일관성이 없습니다.바이어와 맥크라이트(1972)^[3]는 잎의 높이가 가장 낮은 키 수준이라고 생각했지만 크누스는 잎의 높이가 가장 낮은 ^[10]키보다 한 단계 낮다고 생각했다.구현에는 많은 선택지가 있습니다.일부 설계에서는 잎이 전체 데이터 레코드를 보유할 수 있으며, 다른 설계에서는 잎이 데이터 레코드에 대한 포인터만 보유할 수 있습니다.이러한 선택은 B-Tree ^[11]개념의 기본이 아닙니다.

간단하게 하기 위해 대부분의 작성자는 노드에 맞는 키의 수가 고정되어 있다고 가정합니다.기본적인 전제조건은 키사이즈가 고정되어 노드사이즈가 고정되어 있는 것입니다.실제로는 가변 길이 키를 ^[12]사용할 수 있습니다.

비공식적인 설명

B-트리에서 내부(비리프) 노드는 미리 정의된 범위 내에서 가변 개수의 하위 노드를 가질 수 있습니다.데이터를 노드에 삽입하거나 노드에서 제거하면 하위 노드의 수가 변경됩니다.사전 정의된 범위를 유지하기 위해 내부 노드를 결합하거나 분할할 수 있습니다.자노드의 범위가 허용되므로 B-트리는 다른 자가 밸런싱 검색 트리만큼 자주 재밸런싱을 필요로 하지 않지만 노드가 완전히 가득 찬 것은 아니기 때문에 일부 공간을 낭비할 수 있습니다.자노드 수의 하한과 상한은 일반적으로 특정 구현에 대해 고정되어 있습니다.예를 들어 2-3 트리(2-3 B 트리라고도 함)에서는 각 내부 노드에 2개 또는 3개의 자 노드만 있을 수 있습니다.

B-트리의 각 내부 노드에는 다수의 키가 포함되어 있습니다.키는 서브트리를 분할하는 분리값으로 기능합니다.예를 들어 내부 노드에 3개의 자노드(또는 서브트리)가 있는 경우 노드에는$$1(\$displaystyle a_{1$})과 2$(\$의 2개의 키가 필요합니다.왼쪽 끝 서브트리의 모든 값은 1$(\$$displaystyle a_{1$보다 작습니다.중간 서브트리의 ${\displaystyle {모든\mathrm{}}_{}}$ 값은 1(\$displaystyle$ a_${1$}) 사이입니다.$$ ${\displaystyle {및\mathrm{}}_{}}$ 2$({$ 및 맨 오른쪽 서브트리의 모든 값은 2$({$보다 커집니다.

보통 키의 수는 d$\displaystyle$${\displaystyle \mathrm{d에서2<img\; alt="d"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="/immutable/placeholder.png"\; style="vertical-align:\; -0.338ex;\; width:\; 1.216ex;\; height:\; 2.176ex;\; object-fit:\; cover;"\; srcset="">}}$ d$($$displaystyle$ $2d$ $사이$에서 선택됩니다.$여기$서$$d\$displaystyle$d는$$ 최소 키 수,${\displaystyle }d{\displaystyle }$ +$(displaystyle d$+1$$)은 트리의 최소 정도 또는 분기 계수입니다.실제로는 키가 노드에서 가장 많은 공간을 차지합니다.계수 2는 노드를 분할 또는 결합할 수 있음을 보증합니다.내부 노드에 ${\displaystyle \mathrm{2개}}$의 d$\displaystyle 2d$키가$$ $있는{\displaystyle \mathrm{}}$ 경우 $가상$의 ${\displaystyle \mathrm{2d}}$ ${\displaystyle +}$(\$displaystyle 2d+1$) 키노드를$$ $2개$의 d$\displaystyle$ 키노드로 분할하여 중간에 있는 키를 부모 노드로 이동함으로써 해당 노드에 키를 추가할 수 있습니다.각 분할 노드에는 필요한 최소 개수의 키가 있습니다.마찬가지로 내부 노드와 그 네이버에 각각 d$\displaystyle$d 키가$$ $있는{\displaystyle }$ 경우 네이버와 조합하여 내부 노드에서 키를 삭제할 수 있습니다.키를 삭제하면 내부 노드의 키는${\displaystyle }$d -$$({$displaystyle$d-1})이$$ $됩니다{\displaystyle }$.네이버에 가입하면 d$\displaystyle$d 키와$$ 네이버 부모로부터 다운된 키가 $하나{\displaystyle }$ 더 추가됩니다.그 결과 2개의$$(\$displaystyle$ 2d$)$의 완전 노드가 됩니다.

노드로부터의 브랜치(또는 자노드)의 수는 노드에 저장되어 있는 키의 수보다1개 많아집니다.2-3 B 트리의 경우 내부 노드는 1개의 키(2개의 자식 노드 포함) 또는 2개의 키(3개의 자식 노드 포함) 중 하나를 저장합니다.B-tree는 ${\displaystyle \mathrm{파라미터}}$( ${\displaystyle \mathrm{d}}$+${\displaystyle }$1 $){ displaystyle$ ($d$+ ${\displaystyle 1}$ ) $$ (${\displaystyle }$${\displaystyle 2}$ ${\displaystyle \mathrm{d}}$+$$1 ){ $displaystyle$ ( $2 d$ +$$1${\displaystyle }$){$display$style ( 2 d + 1 )$$}{ display $style$ ($$ d + 1 )로 기술되는 경우가 있습니다.

${\displaystyle B}$ 트리는 삽입 후 2 d${\displaystyle }$+ ${\displaystyle 1}$ \$displaystyle 2$d + 1 \ displaystyle d \$$$}$ $and2{\displaystyle }$ d + 1 \ $displaystyle$ 1 \$$$siblings$$$ and2 d + 1 \ $displaystyle$ d \ siblings2 개의 키 형제 노드로 분할하여 중간값 키를 부모에 삽입함으로써 균형을 유지합니다.깊이는 루트가 분할될 때만 증가하여 균형을 유지합니다.$마찬가지$로 B-트리는 삭제 후에도 키를 형제간에 Marge 또는 재배포하여 균형을 유지하여 비루트 $노드의$최소 키를$$ $유지$합니다$.$Marge를 통해 부모 키 수가 감소하여 형제자매와의 키 병합 또는 재배포를 강제할 수 있습니다.깊이의 $유일$한 변화는 루트에$$d $키$와 d${\displaystyle }$키($전이$) $d{\displaystyle }$$$-$$ 키 두 $개$가 있을 때 발생합니다. 이 경우 두 개의 $형제$와 부모가 병합되어 깊이가 1개 줄어듭니다.

이 깊이는 요소가 트리에 추가됨에 따라 서서히 증가하지만 전체 깊이의 증가는 거의 없으며 모든 리프 노드가 루트에서 하나 더 떨어져 있게 됩니다.

노드의 데이터에 액세스하는 시간이 데이터 처리에 소요되는 시간을 크게 초과할 경우 B-tree는 대체 구현에 비해 상당한 이점이 있습니다. 그러면 노드 액세스 비용이 노드 내의 여러 작업에 걸쳐 상각될 수 있기 때문입니다.이 문제는 일반적으로 노드 데이터가 Disk 드라이브와 같은 보조 저장소에 있을 때 발생합니다.각 내부 노드 내의 키 수를 최대화함으로써 트리의 높이가 감소하고 고가의 노드 액세스 수가 감소합니다.또한 트리의 균형 재조정이 더 적게 발생합니다.자식 노드의 최대 수는 각 자식 노드에 대해 저장해야 하는 정보와 전체 디스크 블록 크기 또는 보조 스토리지의 유사한 크기에 따라 달라집니다.2-3 B-tree는 설명이 더 쉽지만, Secondary 스토리지를 사용하는 실용적인 B-Tree는 성능을 향상시키기 위해 많은 수의 하위 노드가 필요합니다.

변종

B-tree라는 용어는 특정 설계를 지칭할 수도 있고 일반적인 설계 클래스를 지칭할 수도 있다.좁은 의미에서 B-tree는 내부 노드에 키를 저장하지만, 그 키를 나머지 레코드에 저장할 필요는 없습니다.일반 클래스에는 B+ 트리, B 트리^* 및 B^*+ 트리와 같은 변형이 포함됩니다.

• B+ 트리에서 키의 복사본은 내부 노드에 저장되며 키와 레코드는 리프에 저장된다.또한 리프 노드는 시퀀셜 ^[2]액세스를 고속화하기 위해 다음 리프 노드에 대한 포인터를 포함할 수 있다.
• B^* 트리는 더 많은 인접 내부 노드의 균형을 조정하여 내부 노드의 패킹을 더 ^[2]촘촘히 유지합니다.이 변형에 의해 비루트노드는 ^[13]1/2가 아닌 적어도 2/3이 꽉 차게 됩니다.B-트리에 노드를 삽입할 때 가장 비용이 많이 드는 부분이 노드 분할이기 때문에 B-트리는^* 분할 작업을 가능한 ^[14]한 연기하도록 작성됩니다.이를 유지하기 위해 노드가 꽉 찼을 때 즉시 분할하는 대신 노드 옆에 있는 노드와 키를 공유합니다.이 유출 작업은 기존 ^[14]노드 간에 키를 이동하기만 하면 되고 새 노드에 메모리를 할당하지 않아도 되기 때문에 분할보다 비용이 적게 듭니다.삽입을 위해서는 먼저 노드에 빈 공간이 있는지 확인하고, 빈 공간이 있을 경우 노드에 새 키를 삽입하기만 하면 됩니다.단, 노드가 꽉 찬 경우(m - 1 키, 여기서 m은 한 노드에서 서브트리에 대한 포인터의 최대 수로서 트리의 순서), 올바른 형제자매가 존재하는지 및 사용 가능한 공간이 있는지 확인해야 합니다.오른쪽 형제 키가 j < m - 1인 경우 키는 두 형제 노드 간에 가능한 한 균등하게 재배포됩니다.이를 위해 현재 노드의 m - 1 키, 삽입된 새 키, 상위 노드의 1 키 및 형제 노드의 j 키는 m + j + 1 키의 순서 배열로 표시됩니다.어레이가 절반으로 분할되기 때문에 "(m + j + 1)/2" 가장 낮은 키가 현재 노드에 남고 다음(중간) 키가 부모 노드에 삽입되고 나머지는 오른쪽 ^[14]형제에게 전달됩니다.(새로 삽입된 키는 세 자리 중 하나에 배치될 수 있습니다.)오른쪽 형제자매가 꽉 찼을 때와 왼쪽이 그렇지 않을 때의 상황은 비슷합니다.^[14]두 형제 노드가 모두 가득 차면 두 노드(현재 노드 및 형제 노드)가 세 개로 분할되고 하나 이상의 키가 트리 위로 상위 ^[14]노드로 이동합니다.부모가 꽉 차면 스필/스플릿 조작이 루트노드로 ^[14]전파됩니다.그러나 노드를 삭제하는 것은 삽입하는 것보다 다소 복잡합니다.
• B^*+ 트리는 메인 B+ 트리와 B^* 트리 기능을 함께 ^[15]결합합니다.
• B-tree를 순서 통계 트리로 변환하여 키 순서로 N번째 레코드를 신속하게 검색하거나 두 레코드 사이의 레코드 수 및 기타 다양한 ^[16]관련 작업을 카운트할 수 있습니다.

데이터베이스의 B-트리 사용

이 문서는 Wikipedia의 품질 기준을 충족하기 위해 청소가 필요할 수 있습니다.구체적인 문제는 다음과 같습니다.어조가 백과사전과 일치하지 않는다. 가능한 한 이 문서를 개선해 주십시오. (2022년 5월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

정렬된 파일을 검색할 시간

일반적으로 정렬 및 검색 알고리즘은 순서 표기법을 사용하여 수행해야 하는 비교 연산 수에 따라 특성이 지정됩니다.예를 들어 N개의 레코드가 있는 정렬된 테이블의 바이너리 검색은 대략 「log₂ N」의 비교로 실시할 수 있습니다.테이블에 1,000,000개의 레코드가 있는 경우, 특정₂ 레코드는 최대 20개의 비교() log (1,000,000) ⌉ = 20)로 찾을 수 있습니다.

지금까지 대용량 데이터베이스는 디스크 드라이브에 보관되어 왔습니다.디스크 드라이브에서 레코드를 읽는 시간은 레코드를 사용할 수 있게 되면 키를 비교하는 데 필요한 시간을 훨씬 초과합니다.디스크 드라이브에서 레코드를 읽는 시간에는 시크 시간과 회전 지연이 포함됩니다.시크 시간은 0~20밀리초 이상이며 회전 지연은 평균 회전 주기의 약 절반입니다.7200 RPM 드라이브의 경우 회전 주기는 8.33 밀리초입니다.Seagate ST3500320 등의 드라이브용NS, 트랙 투 트랙 탐색 시간은 0.8밀리초이고 평균 읽기 탐색 시간은 8.5밀리초입니다.^[17]간단하게 하기 위해 디스크에서 읽는 데 약 10밀리초가 걸린다고 가정합니다.

따라서 100만 개 중 하나의 레코드를 찾는 데 걸리는 시간은 디스크 읽기당 20개의 10밀리초 곱하기 0.2초입니다.

개별 레코드는 디스크 블록에 그룹화되어 있기 때문에 시간은 그리 나쁘지 않습니다.디스크 블록은 16킬로바이트일 수 있습니다.각 레코드가 160바이트일 경우 각 블록에 100개의 레코드를 저장할 수 있습니다.위의 디스크 읽기 시간은 실제로 전체 블록에 대한 것입니다.디스크 헤드가 제자리에 배치되면 1개 이상의 디스크 블록을 거의 지연 없이 읽을 수 있습니다.블록당 레코드가 100개이므로 마지막 6개 정도의 비교는 Disk 읽기를 수행할 필요가 없습니다. 비교는 모두 마지막 Disk 블록 읽기에 포함됩니다.

검색 속도를 높이려면 첫 번째 13 대 14 비교(각각 디스크 액세스 필요)를 고속화할 필요가 있습니다.

인덱스는 검색 속도를 높입니다.

B-트리 색인은 데이터베이스를 고정 크기의 블록 또는 페이지로 분할하는 다단계 트리 구조를 만듭니다.이 트리의 각 레벨을 사용하여 주소 위치를 통해 이러한 페이지를 링크할 수 있습니다.이것에 의해, 1 페이지(노드 또는 내부 페이지)가 다른 페이지(노드 또는 내부 페이지)를 참조할 수 있습니다.일반적으로 한 페이지는 트리의 시작점 또는 "루트"입니다.여기서 특정 키 검색이 시작되고 리프에서 종료되는 경로를 통과합니다.이 구조체의 대부분의 페이지는 궁극적으로 특정 테이블 행을 참조하는 리프 페이지입니다.

B-tree 인덱스를 사용하면 성능을 크게 향상시킬 수 있습니다.각 노드(또는 내부 페이지)에는 세 개 이상의 하위 항목이 있을 수 있으므로 일반적으로 B-트리 인덱스는 이진 검색 트리보다 더 짧은 높이(루트에서 가장 먼 리프까지의 거리)를 가집니다.위의 예에서는 초기 디스크 판독으로 검색 범위가 2배 좁혀졌습니다.이는 각 디스크 블록에 첫 번째 레코드를 포함하는 보조 인덱스(소형 인덱스라고도 함)를 생성함으로써 크게 개선될 수 있습니다.이 보조 색인은 기존 데이터베이스 크기의 1%이지만 더 빠르게 검색할 수 있습니다.보조 인덱스에서 엔트리를 찾으면 메인 데이터베이스에서 어떤 블록을 검색할지 알 수 있습니다. 보조 인덱스를 검색한 후에는 디스크 읽기 1개를 더 들여 메인 데이터베이스의 해당 블록만 검색하면 됩니다.이 지수는 1만 개의 엔트리를 보유하기 때문에 최대 14개의 비교가 필요할 것이다.기본 데이터베이스와 마찬가지로 보조 인덱스의 마지막 6개 정도의 비교는 동일한 디스크 블록에 있습니다.인덱스는 약 8개의 디스크 판독으로 검색할 수 있으며 원하는 레코드는 9개의 디스크 판독으로 액세스할 수 있습니다.

보조 지수를 만드는 방법을 반복하여 보조 지수에 보조 지수를 만들 수 있다.그러면 100개의 엔트리만 필요하고 하나의 디스크 블록에 들어갈 수 있는 보조 인덱스가 생성됩니다.

원하는 레코드를 찾기 위해 14개의 디스크 블록을 읽는 대신 3개의 블록만 읽으면 됩니다.이 블로킹은 B-트리를 만드는 핵심 아이디어이며 디스크 블록은 인덱스를 구성하기 위해 레벨 계층을 채웁니다.트리의 루트인 aux-aux 인덱스의 첫 번째(및 유일한) 블록을 읽고 검색하면 다음 레벨의 aux-index에서 관련 블록을 식별합니다.이 보조 인덱스 블록을 읽고 검색하면 최종 레벨(리프 레벨)이 메인 데이터베이스 내의 레코드를 식별할 때까지 읽을 관련 블록을 식별할 수 있습니다.150밀리초가 아니라 30밀리초면 기록을 얻을 수 있습니다.

보조 인덱스는 대략적인₂ N개의 디스크 읽기를 필요로 하는 이진 검색에서 b가 차단 요인인 N개의_b 디스크 읽기만 필요로 하는 검색으로 검색 문제를 전환했습니다(이 예에서는 블록당 항목 수: b = 100개₁₀₀, log 1,000,000 = 3개의 읽기).

실제로 메인 데이터베이스가 자주 검색되는 경우 보조 인덱스와 보조 인덱스의 대부분은 디스크 캐시에 상주하므로 디스크 읽기가 발생하지 않습니다.B-트리는 거의 모든 관계형 데이터베이스에서 표준 인덱스 구현으로 유지되며,^[18] 많은 비관계형 데이터베이스에서도 사용됩니다.

삽입 및 삭제

데이터베이스가 변경되지 않는 경우 색인 컴파일은 간단하며 색인을 변경할 필요가 없습니다.변경사항이 있는 경우 데이터베이스 및 색인 관리가 더 복잡해집니다.

데이터베이스에서 레코드를 삭제하는 것은 비교적 쉽습니다.인덱스는 그대로 유지되고 레코드는 삭제된 것으로 표시될 수 있습니다.데이터베이스는 정렬된 순서대로 유지됩니다.삭제가 느리면 검색 및 저장 효율이 ^[19]떨어집니다.

삽입된 레코드를 위한 공간을 만들어야 하므로 정렬된 순차 파일에서 삽입이 매우 느릴 수 있습니다.첫 번째 레코드 전에 레코드를 삽입하려면 모든 레코드를 1개 아래로 이동해야 합니다.그런 수술은 비용이 너무 많이 들어 실용적이지는 않다.한 가지 해결책은 약간의 공간을 남기는 것입니다.블록 내의 모든 레코드를 조밀하게 채우는 대신 블록에 다음 삽입을 위한 여유 공간이 있을 수 있습니다.이러한 공간은 "삭제된" 기록으로 표시됩니다.

블록에 사용 가능한 공간이 있는 한 삽입 및 삭제가 모두 빠릅니다.삽입이 블록에 맞지 않을 경우 근처의 블록에서 사용 가능한 공간을 찾아 보조 인덱스를 조정해야 합니다.많은 블록을 재구성할 필요가 없도록 근처에 충분한 공간을 확보할 수 있기를 바랍니다.또는 순서가 맞지 않는 디스크 블록을 ^[18]사용할 수도 있습니다.

데이터베이스에 대한 B-Tree 사용의 이점

B-Tree는 위에서 설명한 모든 아이디어를 사용합니다.특히 B-tree는 다음과 같습니다.

• 키를 순차적으로 트래버싱할 수 있도록 정렬된 순서대로 유지
• 계층 인덱스를 사용하여 디스크 읽기 수를 최소화합니다.
• 부분 전체 블록을 사용하여 삽입 및 삭제 속도를 높입니다.
• 재귀 알고리즘으로 인덱스를 균형 있게 유지하다

또한 B-트리는 내부 노드가 절반 이상 채워져 있으므로 낭비를 최소화할 수 있습니다.B-트리는 임의의 수의 삽입 ^[18]및 삭제를 처리할 수 있습니다.

베스트 케이스와 워스트 케이스의 높이

h – - 1을 기존의 B-트리의 높이로 합니다(트리 높이 정의에 대해서는 "Tree (데이터 구조)"를 참조해 주세요).n 0 0은 트리 내의 엔트리 수입니다.m은 노드가 가질 수 있는 최대 자식 수입니다.각 노드는 최대 m-1 키를 가질 수 있습니다.

모든 노드가 완전히 채워진 높이 h의 B-트리는 n = m^h+1–1 엔트리를 가지고 있음을 (예를 들어 유도를 통해) 알 수 있다.따라서, B-트리의 최선의 케이스 높이(즉, 최소 높이)는 다음과 같습니다.

${\displaystyle h_{\mathrm {min}}=\lceil \log _{m}(n+1)\rceil -1}$

$\displaystyle$d는$$ 내부(루트 이외) 노드에 필요한 최소 자식 수입니다.일반 B 트리의 $경우{\displaystyle }$ d ${\displaystyle =}$"${\displaystyle m}$ ${\displaystyle /}$ ${\displaystyle 2\mathrm{}}$"$$. { $displaystyle$ d = \$left$ \ $lceil m/$2 \$right$ \ $rceil$}

Comer(1979)와 Cormen 등.(2001)는 B-트리의^[20] 최악의 경우 높이(최대 높이)를 다음과 같이 나타냅니다.

$\displaystyle h_{\mathrm {max}=\left\lfloor \log _{d}{\frac {n+1}{2}}\right\loor .}$

알고리즘

이 기사는 독자들에게 혼란스럽거나 불분명할 수 있다.특히, 아래 설명에서는 기본적으로 동일한 것을 의미하는 "요소", "가치", "키", "구분자" 및 "분리 값"을 사용합니다.그 용어들은 명확하게 정의되어 있지 않다.근원적으로 미묘한 문제가 몇 가지 있다. 글의 명확화를 도와주세요. 토크 페이지에 이 건에 대한 논의가 있을 수 있습니다.(2012년 2월) (이 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다)

서치

검색은 이진 검색 트리를 검색하는 것과 비슷합니다.루트에서 시작하여 트리는 위에서 아래로 재귀적으로 통과합니다.각 수준에서 검색 범위는 검색 값을 포함하는 하위 포인터(하위 트리)로 축소됩니다.서브트리의 범위는 상위 노드에 포함된 값(또는 키)에 의해 정의됩니다.이러한 제한치는 분리값이라고도 합니다.

바이너리 검색은 일반적으로 노드 내에서 대상 분리 값과 하위 트리를 찾기 위해 사용됩니다(반드시 그렇지는 않습니다).

삽입

모든 삽입은 리프 노드에서 시작합니다.새 요소를 삽입하려면 트리를 검색하여 새 요소를 추가해야 하는 리프 노드를 찾습니다.다음 절차에 따라 해당 노드에 새 요소를 삽입합니다.

1. 노드에 허용되는 최대 요소 수보다 적은 수의 요소가 포함된 경우 새 요소를 사용할 수 있는 공간이 있습니다.노드의 요소를 순서대로 유지하면서 노드에 새 요소를 삽입합니다.
2. 그렇지 않으면 노드가 가득 찼습니다.이렇게 하려면 노드를 2개의 노드로 균등하게 분할합니다.
   1. 리프 요소와 삽입 중인 새 요소 중에서 단일 중위수가 선택됩니다.
   2. 중앙값보다 작은 값은 새 왼쪽 노드에 배치되고 중앙값보다 큰 값은 새 오른쪽 노드에 배치되며 중앙값은 분리값으로 작용합니다.
   3. 분리 값은 노드의 부모에 삽입되어 노드의 분할 등이 발생할 수 있습니다.노드에 부모가 없는 경우(즉, 노드가 루트) 이 노드 위에 새 루트를 만듭니다(트리 높이 증가).

분할이 루트까지 진행되면 단일 구분자 값과 두 개의 자식 값을 가진 새 루트가 생성되므로 내부 노드 크기 하한이 루트에 적용되지 않습니다.노드당 요소의 최대 수는 U-1입니다.노드가 분할되면 하나의 요소가 부모로 이동하지만 하나의 요소가 추가됩니다.따라서 요소의 최대수 U-1을 2개의 합법적 노드로 분할할 수 있어야 합니다.이 수가 홀수일 경우 U=2L 및 새 노드 중 하나에 (U-2)/2 = L-1 요소가 포함되어 있으므로 합법적인 노드이며, 다른 노드에는 하나 이상의 요소가 포함되어 있으므로 합법적인 노드이기도 합니다.U-1이 짝수이면 U=2L-1이므로 노드에는 2L-2 요소가 있습니다.이 숫자의 절반은 노드당 허용되는 최소 요소 수인 L-1입니다.

대체 알고리즘은 루트로부터 삽입이 이루어지는 노드까지의 단일 패스다운트리를 지원하며, 도중에 발견된 모든 노드를 프리엠프티브하게 분할합니다.이로 인해 부모 노드를 메모리로 호출할 필요가 없어지고 노드가 세컨더리 스토리지에 있는 경우 비용이 많이 들 수 있습니다.단, 이 알고리즘을 사용하려면 새로운 요소를 추가하지 않고1개의 요소를 부모에게 송신하고 나머지 U-2 요소를 2개의 합법적 노드로 분할할 수 있어야 합니다.이를 위해서는 U = 2L-1 대신 U = 2L가 필요하며, 이는 일부 교과서가 B-트리를 정의할 때 이 요구사항을 부과하는 이유를^[which?] 설명한다.

삭제

B-tree에서 삭제하기 위한 두 가지 일반적인 방법이 있습니다.

1. 항목을 찾아서 삭제한 다음 트리를 재구성하여 해당 불변수를 유지합니다.
2. 트리를 1회 패스다운합니다만, 노드를 개시(방문)하기 전에, 삭제할 키가 발견되면, 추가 재구성의 필요 없이 삭제할 수 있도록 트리를 재구축합니다.

다음 알고리즘은 앞의 전략을 사용합니다.

요소를 삭제할 때 고려해야 할 특별한 경우가 두 가지 있습니다.

1. 내부 노드의 요소는 하위 노드의 구분자입니다.
2. 요소를 삭제하면 해당 노드가 최소 요소 및 자식 수보다 적을 수 있습니다.

이러한 경우의 순서는 다음과 같습니다.

리프 노드에서 삭제

1. 삭제할 값을 검색합니다.
2. 값이 리프 노드에 있는 경우 노드에서 해당 값을 삭제하기만 하면 됩니다.
3. 언더플로우가 발생하면 아래의 "삭제 후 재조정" 섹션에 설명된 대로 트리의 균형을 재조정하십시오.

내부 노드에서 삭제

내부 노드의 각 요소는 2개의 서브트리의 분리값으로 기능하기 때문에 분리를 대체할 대체 요소를 찾아야 합니다.왼쪽 서브트리에서 가장 큰 요소는 여전히 구분자보다 작습니다.마찬가지로 오른쪽 서브트리에서 가장 작은 요소는 여전히 구분자보다 큽니다.이러한 요소는 모두 리프 노드에 있으며, 어느 한쪽이 2개의 서브트리의 새로운 구분자가 될 수 있습니다.알고리즘은 다음과 같습니다.

1. 새 구분자(왼쪽 하위 트리에서 가장 큰 요소 또는 오른쪽 하위 트리에서 가장 작은 요소)를 선택하고 해당 요소를 리프 노드에서 제거한 후 삭제할 요소를 새 구분자로 바꿉니다.
2. 이전 단계에서는 리프 노드에서 요소(새 구분 기호)를 삭제했습니다.해당 리프 노드가 부족한 경우(필요한 노드 수보다 적음) 리프 노드부터 트리의 균형을 재조정합니다.

삭제 후 재조정

리밸런싱은 리프에서 시작하여 트리가 밸런싱될 때까지 루트를 향해 진행됩니다.노드에서 요소를 삭제하여 최소 크기를 밑돌 경우 모든 노드를 최소 크기로 만들기 위해 일부 요소를 재배포해야 합니다.일반적으로 재배포에는 최소 노드 수를 초과하는 요소를 형제 노드에서 이동하는 작업이 포함됩니다.이 재배포 조작을 로테이션이라고 부릅니다.요소를 스페어할 수 있는 형제 노드가 없는 경우 부족한 노드를 형제 노드와 병합해야 합니다.Marge로 인해 부모가 구분 요소를 잃게 되므로 부모가 부족해져 재조정이 필요할 수 있습니다.머지 및 재밸런싱은 루트까지 계속됩니다.최소 요소 수는 루트에 적용되지 않으므로 루트를 유일한 결함 노드로 만드는 것은 문제가 되지 않습니다.트리의 균형을 재조정하는 알고리즘은 다음과 같습니다.

• 부족한 노드의 오른쪽 형제자매가 존재하며 최소 요소 수보다 많은 경우 왼쪽으로 회전합니다.
  1. 세퍼레이터를 부모 노드에서 결함이 있는 노드의 끝에 복사합니다(세퍼레이터가 아래로 이동합니다. 결함이 있는 노드는 최소의 요소 수를 가집니다).
  2. 부모에서 오른쪽 형제자매의 첫 번째 요소로 구분 기호 바꾸기(오른쪽 형제자매는 노드 하나를 잃었지만 최소 개수의 요소가 있음)
  3. 나무는 이제 균형을 잡았습니다.
• 그렇지 않으면 부족한 노드의 왼쪽 형제자매가 존재하며 최소 요소 수보다 많은 경우 오른쪽으로 회전합니다.
  1. 세퍼레이터를 부모 노드에서 결함이 있는 노드의 선두로 복사합니다(세퍼레이터가 아래로 이동합니다.이제 결함이 있는 노드의 요소 수는 최소가 됩니다).
  2. 부모의 구분 기호를 왼쪽 형제의 마지막 요소로 바꿉니다(왼쪽 형제는 노드 하나를 잃었지만 최소 수 이상의 요소가 있음).
  3. 나무는 이제 균형을 잡았습니다.
• 그렇지 않으면 두 직계 형제 모두 최소 수의 요소만 가지고 있는 경우 부모로부터 분리한 구분 기호를 사용하여 형제와 병합하십시오.
  1. 왼쪽 노드의 끝에 구분 기호를 복사합니다(왼쪽 노드가 부족한 노드이거나 요소의 수가 최소인 형제 노드일 수 있음).
  2. 모든 요소를 오른쪽 노드에서 왼쪽 노드로 이동합니다(왼쪽 노드는 최대 수의 요소가 있으며 오른쪽 노드는 비어 있습니다).
  3. 부모에서 빈 오른쪽 자식과 함께 구분자를 제거합니다(부모가 요소를 손실함).
     • 부모가 루트이고 요소가 없는 경우 부모 노드를 해방하여 새 루트로 만듭니다(트리는 더 얕아짐).
     • 그렇지 않은 경우 부모 요소의 수가 필요한 수보다 적을 경우 부모 요소의^[21] 균형을 재조정합니다.

주의: 재조정 조작은 B+ 트리(예를 들어 부모가 키의 복사본을 가지고 있기 때문에 순환이 다르다)와 B 트리^*(예를 들어, 3명의 형제자매가 2개의 형제자매로 병합됨)에 따라 다릅니다.

시퀀셜 액세스

새로 로드된 데이터베이스는 순차적으로 양호한 동작을 보이는 경향이 있지만, 데이터베이스가 증가함에 따라 이 동작을 유지하기가 점점 더 어려워지고 랜덤 I/^[22]O 및 성능 문제가 발생합니다.

초기 시공

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 소스되지 않은 소재는 이의를 제기하여 삭제될 수 있습니다. (2018년 4월) (이 템플릿메시지 삭제 방법 및 시기에 대해 알아보기)

일반적인 특수한 경우는 사전에 정렬된 대량의 데이터를 초기 빈 B-트리에 추가하는 것입니다.일련의 연속 삽입을 간단하게 수행할 수 있지만 정렬된 데이터를 삽입하면 거의 전체가 절반으로 구성된 트리가 됩니다.대신 특별한 "벌크 로드" 알고리즘을 사용하여 분기 계수가 높은 보다 효율적인 트리를 생성할 수 있습니다.

입력이 정렬되면 모든 삽입이 트리의 오른쪽 끝에 있으며, 특히 노드가 분할될 때마다 왼쪽 절반에서 삽입이 더 이상 수행되지 않음을 보증합니다.벌크 로딩 시에는 이 점을 이용하여 오버풀노드를 균등하게 분할하지 말고 가능한 한 균등하게 분할합니다.왼쪽 노드를 완전히 가득 채우고 키가 제로이고 하위 노드가 1개 있는 오른쪽 노드를 만듭니다(통상적인 B-트리 규칙을 위반).

벌크 로딩이 끝나면 트리는 거의 완전히 완전한 노드로 구성됩니다.각 레벨의 오른쪽 끝 노드만 가득 찰 수 있습니다.이러한 노드도 절반 미만일 수 있으므로 일반 B-트리 규칙을 재정립하려면 이러한 노드를 (완전하게 보장된) 왼쪽 형제와 결합하여 키를 분할하여 2개의 노드를 적어도 절반으로 만듭니다.전체 왼쪽 형제 노드가 없는 유일한 노드는 절반 미만일 수 있는 루트입니다.

파일 시스템 내

B 트리(또는 「바리안트」)는, 데이타베이스에서의 사용에 가세해 파일 시스템에서도 사용되어 특정의 파일의 임의의 블록에의 신속한 랜덤 액세스가 가능하게 됩니다.기본적인 문제는 파일 $블록{\displaystyle }$i $주소$를 디스크 블록(또는 실린더 헤드 섹터) 주소로 변경하는 것입니다.

일부 운영 체제에서는 파일 생성 시 사용자가 파일의 최대 크기를 할당해야 합니다.그런 다음 파일을 연속된 디스크 블록으로 할당할 수 있습니다.이 경우 파일 $블록$ $i를$디스크$$ 블록 주소로 변환하기 위해 운영체제는 파일을 구성하는 첫 번째 디스크 $블록$ 주소에 파일 블록 $i$를 추가합니다$$.구성은 단순하지만 파일은 생성된 크기를 초과할 수 없습니다.

다른 운영 체제에서는 파일을 확장할 수 있습니다.결과 디스크 블록은 연속되지 않을 수 있으므로 논리 블록을 실제 블록에 매핑하는 것이 더 중요합니다.

예를 들어 MS-DOS는 단순한 파일 할당 테이블(FAT)을 사용했습니다.FAT에는 각 디스크 ^{[note 1]}블록에 대한 엔트리가 있으며, 이 엔트리는 해당 블록이 파일에 의해 사용되는지 여부와 사용되는 경우 동일한 파일의 다음 디스크 블록(있는 경우)을 식별합니다.따라서 각 파일의 할당은 표에서 링크된 목록으로 나타납니다.파일 $블록{\displaystyle }$ i$\backslash$$displaystyle$i의 디스크 주소를 찾으려면 운영 체제(또는 디스크 유틸리티)가 FAT에 있는 파일의 링크 목록을 순서대로 따라야 합니다.게다가 빈 디스크 블록을 찾으려면 FAT를 순차적으로 스캔해야 합니다.MS-DOS의 경우 디스크와 파일이 작고 FAT에는 엔트리가 거의 없고 파일 체인이 비교적 짧기 때문에 큰 단점이 되지 않았습니다.FAT12 파일 시스템(플로피 디스크 및 초기 하드 디스크에서 사용)에서는 엔트리가 4,080개를 넘지 않았으며 FAT는 보통 메모리에 상주합니다.디스크가 커짐에 따라 FAT 아키텍처는 처벌에 직면하기 시작했습니다.FAT를 사용하는 대용량 디스크에서는 읽거나 쓸 파일 블록의 디스크 위치를 학습하기 위해 디스크 읽기를 수행해야 할 수 있습니다.

TOPS-20(및 TENEX)에서는 B 트리와^{[citation needed]} 유사한0 ~ 2레벨 트리가 사용되었습니다.디스크 블록은 512개의 36비트 워드입니다.파일이 512(2⁹) 워드 블록에 들어갈 경우 파일 디렉토리가 해당 물리적 디스크 블록을 가리킵니다.파일이 2단어로 되어 있으면¹⁸ 디렉토리는 보조 인덱스를 가리킵니다.이 인덱스의 512단어는 NULL(블록이 할당되지 않음)이거나 블록의 물리 주소를 가리킵니다.파일이 2단어로 되어 있는²⁷ 경우 디렉토리는 aux 인덱스를 보유하고 있는 블록을 가리킵니다.각 엔트리는 NULL이거나 aux 인덱스를 가리킵니다.따라서 2워드 파일의²⁷ 물리 디스크 블록은 2개의 디스크 읽기 및 3번째 디스크 읽기 내에 배치될 수 있습니다.

Apple의 파일 시스템 HFS+ 및 APFS, Microsoft의 ^[23]NTFS, AIX(jfs2) 및 btrfs 및 Ext4와 같은 일부 Linux 파일 시스템은 B-tree를 사용합니다.

B-tree는^* HFS 및 Reiser4 파일시스템에서 사용됩니다.

DragonFly BSD의 HAMMER 파일 시스템은 수정된 B+ ^[24]트리를 사용합니다.

성능

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2020년 5월) (이 템플릿메시지 삭제 방법 및 삭제 타이밍 확인)

B-트리는 데이터 양이 증가함에 따라 링크된 목록의 선형성보다 느리게 증가합니다.스킵 리스트와 비교하면 양쪽 구조는 같은 퍼포먼스를 가지지만 B-트리는 확장성이 뛰어나고 메인 메모리 데이터베이스 시스템의 경우 T-트리는 비슷하지만 더 콤팩트합니다.

바리에이션

액세스 동시성

리먼과^[25] 야오는 각 레벨의 트리 블록을 "다음" 포인터와 함께 링크함으로써 모든 읽기 잠금을 피할 수 있다는 것을 보여주었다.이로 인해 삽입 작업과 검색 작업이 모두 루트에서 리프로 내려오는 트리 구조가 생성됩니다.쓰기 잠금은 트리 블록을 수정할 때만 필요합니다.이것에 의해, 복수의 유저에 의한 액세스의 동시성이 최대화됩니다.이것에 의해, 데이터베이스나 그 외의 B-tree 베이스의 ISAM 스토리지 방식에 있어서 중요한 고려사항이 됩니다.이 개선과 관련된 비용은 일반 작업 중에 빈 페이지를 Btree에서 제거할 수 없다는 것입니다.(단, 노드 머지 및 소스 코드를 실장하는 다양한 전략에 대해서는, 을 참조해 주세요).^[27]

1994년에 부여된 미국 특허 5283894는 '메타 액세스 방법'을 사용하여 잠금 없이 B+ 트리에 동시에 액세스하고 수정할 수 있는 방법을 보여주는 것으로 보입니다.이 기술은 블록 캐시의 각 레벨의 블록을 가리키는 추가 인메모리 인덱스를 통해 검색 및 업데이트를 위해 트리에 '상향'으로 액세스합니다.삭제를 위한 재구성은 필요하지 않으며, 각 블록에는 리먼이나 야오처럼 '다음' 포인터가 없습니다.

병렬 알고리즘

B-트리는 레드-블랙 트리와 구조가 비슷하기 때문에 레드-블랙 트리의 병렬 알고리즘을 B-트리에 적용할 수도 있다.

「 」를 참조해 주세요.

• B+ 트리
• R 트리
• 붉은색-검은색
• 2~3 트리
• 2-3-4 트리

메모들

레퍼런스

일반

• Bayer, R.; McCreight, E. (1972), "Organization and Maintenance of Large Ordered Indexes" (PDF), Acta Informatica, 1 (3): 173–189, doi:10.1007/bf00288683, S2CID 29859053
• 를 클릭합니다Comer, Douglas (June 1979), "The Ubiquitous B-Tree", Computing Surveys, 11 (2): 123–137, doi:10.1145/356770.356776, ISSN 0360-0300, S2CID 101673.
• Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2001), Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, pp. 434–454, ISBN 0-262-03293-7. 18장: B-Tree.
• Folk, Michael J.; Zoellick, Bill (1992), File Structures (2nd ed.), Addison-Wesley, ISBN 0-201-55713-4
• Knuth, Donald (1998), Sorting and Searching, The Art of Computer Programming, vol. 3 (Second ed.), Addison-Wesley, ISBN 0-201-89685-0. 섹션 6.2.4: 다중 방향 나무, 페이지 481–491.또한 섹션 6.2.3(균형수)의 476–477페이지에서는 2-3개의 나무를 논의한다.

오리지널 페이퍼

• 를 클릭합니다Bayer, Rudolf; McCreight, E. (July 1970), Organization and Maintenance of Large Ordered Indices, vol. Mathematical and Information Sciences Report No. 20, Boeing Scientific Research Laboratories.
• 를 클릭합니다Bayer, Rudolf (1971), Binary B-Trees for Virtual Memory, Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego, California.

외부 링크

• 데이비드 스코트 테일러의 B-tree 강의, SJU
• B-Tree 시각화("init" 클릭)
• 애니메이션 B-Tree 시각화
• Scholarpedia 큐레이터 B-Tree와 UB-Tree: Dr. Rudolf Bayer
• B-Tree: 균형 잡힌 트리 데이터 구조
• NIST 알고리즘 및 데이터 구조 사전: B-tree
• B-Tree 튜토리얼
• InfinityDB BTree 구현
• 캐시 언센시드 B(+) 트리
• B* 트리의 알고리즘 및 데이터 구조 엔트리 사전
• 개방형 데이터 구조 - 섹션 14.2 - B-Tree, Pat Morin
• 카운트된 B-Tree
• B-Tree 입니다.Net, 최신 가상화 RAM 및 디스크 구현

벌크 로딩

• Shetty, Soumya B. (2010). A user configurable implementation of B-trees (Thesis). Iowa State University.
• Kaldırım, Semih (28 April 2015). "File Organization, ISAM, B+ Tree and Bulk Loading" (PDF). Ankara, Turkey: Bilkent University. pp. 4–6.
• "ECS 165B: Database System Implementation: Lecture 6" (PDF). University of California, Davis. 9 April 2010. p. 23.
• "BULK INSERT (Transact-SQL) in SQL Server 2017". Microsoft Docs. 6 September 2018.