B+나무

B+나무
B+나무
유형	트리(데이터 구조)
작동
빅 O 표기법의 시간 복잡도
작동	평균
서치	O(로그인)
삽입	O(로그인)
삭제	O(로그인)
공간복잡도
공간	O(n)

B+ 트리는 변수가 있지만 노드당 자식 수가 많은 m-ary 트리입니다. B+ 트리는 뿌리, 내부 노드 및 잎으로 구성됩니다.^[1] 루트는 리프 또는 둘 이상의 자식이 있는 노드일 수 있습니다.

B+ 트리는 각 노드가 키만 포함하고(키-값 쌍이 아닌), 연결된 리프와 함께 하단에 추가 레벨이 추가되는 B-트리로 볼 수 있습니다.

B+ 트리의 주요 가치는 블록 지향 스토리지 컨텍스트, 특히 파일 시스템에서 효율적인 검색을 위해 데이터를 저장하는 것입니다. 이것은 주로 이진 검색 트리와 달리 B+ 트리는 매우 높은 팬아웃(일반적으로 100 이상의 순서로 노드의 하위 노드에 대한 포인터 수)^[1]을 가지므로 트리에서 요소를 찾는 데 필요한 I/O 작업 수가 줄어듭니다.

역사

B+ 트리 개념을 소개하는 논문은 단 한 편도 없습니다. 대신 모든 데이터를 리프 노드에 유지한다는 개념이 흥미로운 변형으로 반복적으로 제기됩니다. Douglas Comer는 B-tree(B+ tree도 포함)에 대한 초기 조사에서 B+ tree가 IBM의 VSAM 데이터 액세스 소프트웨어에 사용되었으며 1973년 IBM에서 발표한 기사를 참조합니다.^[2]

구조.

포인터 구조

B+ 트리는 다른 트리와 마찬가지로 뿌리, 내부(일명 내부), 잎의 세 가지 노드의 집합으로 표현될 수 있습니다. B+ 트리에서는 이러한 노드에 대해 다음 속성이 유지됩니다.

${\textstyle k_{i}}$ + 트리의 $임의$ 의 노드에 $ki {\$ textstyle k_{ $i}}$ 가 존재하는 경우, $k_{i-1}$ - 1 $k_{i-1}$ {\ $displaystyle k_{i-1}}$ 은 i가 ≥ 1 {\ $displaystyle$ i $i\geq 1$ geq 1}인 노드에 존재합니다.
모든 리프 노드는 동일한 수의 조상을 갖습니다(즉, 모두 동일한 깊이에 있음).

노드의 포인터 속성은 아래 표에 요약되어 있습니다.

$K$ : B+ 트리의 각 노드에 대한 잠재적 검색 키의 최대 수. (이 값은 트리 전체에서 일정합니다.)
$p_{i}$ ${\$ : 제로 기반 노드 $인덱스$ i ${\displaystyle$ i $}$ 의 $포인터$ 입니다 $i$
$k_{i}$ ${\$ : 제로 기반 노드 인덱스 $i$ $i$ 의 검색 키입니다 $i$

내부 노드 포인터 구조
$p_{0}$ $k_{0}$ $p_{0}$ ${\$ k $k_{0}$ ${\$ 존재 $p_{0}$ $k_{0}$ 시	$p_{i}$ ${\$ $k_{i-1}$ - $k_{i-1}$ ${\$ 및 $k_{i-1}$ $k_{i}$ ${\$ 가 $p_{i}$ $k_{i}$ 존재할 때	$p_{i}$ ${\$ $k_{i-1}$ - $k_{i-1}$ ${\$ 이 $p_{i}$ $k_{i-1}$ 존재하고 $k_{i}$ ${\$ 가 존재하지 $k_{i}$ 않을 때	$p_{i}$ ${\$ $k_{i-1}$ - $k_{i-1}$ ${\$ 및 $k_{i-1}$ $k_{i}$ ${\$ 가 $k_{i}$ 존재하지 않을 $p_{i}$ 때
모든 검색 키가 $k_{0}$ 0 ${\$ 미만인 하위 트리를 가리킵니다 $k_{0}$	모든 검색 키가 $k_{i-1}$ - $k_{i-1}$ ${\$ 이상이고 $k_{i-1}$ $k_{i}$ ${\$ 미만인 부분 트리를 가리킵니다 $k_{i}$	모든 검색 키가 $k_{i-1}$ - $k_{i-1}$ ${\$ 이상인 부분 트리를 가리킵니다 $k_{i-1}$	$p_{i}$ 서 $p_{i}$ ${\$ 는 비어 $p_{i}$ 있습니다.

리프 노드 포인터 구조
$p_{i}$ ${\$ $k_{i}$ ${\$ 존재 $p_{i}$ $k_{i}$ 시	$p_{i}$ $p_{i}$ $k_{i}$ $k_{i}$ 가 존재하지 않을 때 $ki {\displaystyle$ $p_{i}$ i\n $≠$ $eq K}$	$p_{K}$
$k_{i}$ ${\$ 와 같은 값을 가진 레코드를 가리킵니다 $k_{i}$	$p_{i}$ 서 $p_{i}$ ${\$ 는 비어 $p_{i}$ 있습니다.	나무의 다음 잎을 가리킵니다.

노드 경계

노드 경계는 아래 표에 요약되어 있습니다.

노드 유형	최소 키 수	최대 키 수	하위 노드의 최소 수	최대 하위 노드 수
루트 노드(리프 노드인 경우)	0	$K$	0	0
루트 노드(내부 노드인 경우)	1	$K$	2^[1]	$K+1$
내부 노드	$\lfloor K/2\rfloor$	$K$	$\lceil (K+1)/2\rceil$ $\equiv \lfloor K/2\rfloor +1$	$K+1$
리프 노드	$\lceil K/2\rceil$	$K$	0	0

^[3]^[4]

내부 노드의 간격

키 1~7을 데이터 값 d-d에₁₇ 연결하는 간단한 B+ 트리 예제입니다. 연결된 목록(빨간색)을 사용하면 빠른 순서 순회가 가능합니다. 이 트리의 분기 인자는 $b$ $b$ = 4 입니다. 리프와 내부 노드의 키는 모두 여기에서 회색으로 표시됩니다.

정의에 따라 B+ 트리 내에 포함된 각 값은 정확히 하나의 리프 노드에 포함된 키입니다. 각 키는 전체 순서를 형성하는 다른 모든 키와 직접 비교해야 합니다.^[5] 이를 통해 각 리프 노드는 모든 키를 항상 정렬된 상태로 유지할 수 있으며, 이를 통해 각 내부 노드는 주어진 리프에 포함된 값의 연속 범위를 나타내는 간격의 순서화된 컬렉션을 구성할 수 있습니다. 그러면 트리의 상위에 있는 내부 노드는 자신의 자식 내부 노드에 포함된 간격을 재귀적으로 집계하는 자신의 간격을 구성할 수 있습니다. 결국 B+ 트리의 루트는 트리의 전체 값 범위를 나타내며, 여기서 모든 내부 노드는 하위 구간을 나타냅니다.

이 재귀 간격 정보를 유지하려면 $i\in [1,m-1]$ $l_{i}$ 에 $m-1$ i ∈ $i\in [1,m-1]$ [ $i\in [1,m-1]$ , m $i\in [1,m-1]$ - 1] ${\displaystyle$ $i$ $\$ in [1,] ${\$ $displaystyle i$ $\in$ [1 $,$ $m-1]}$ 은(자체가 내부 노드 또는 리프일 수 있음) 인덱스 $i$ 인 자식이 포함하는 간격 내에서 최소 요소를 나타냅니다 $i\in [1,m-1]$ . 여기서 $m$ 은 특정 내부 노드의 실제 자식 수를 나타냅니다.

특성.

B+ 트리의 순서 또는 분기 인자 $b$ 는 내부 노드의 용량, 즉 직접 자식 노드의 최대 허용 수를 측정합니다. 이 값은 트리 전체에서 일정합니다. $h$ 수준의 지수를 가진 b차 B+ 트리의 경우:^{[citation needed]}

저장된 레코드의 최대 수는 $n_{\max }=b^{h}-b^{h-1}$ = $n_{\max }=b^{h}-b^{h-1}$ - $bh$ - 1 {\displaystyle n_{\max } = b^{h}-b^{h-1 $}}$ 입니다.
저장된 최소 레코드 수는 $n_{\min }=2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-2}$ = 2 ⌈ $b$ 2 ⌉ h - 1 - 2 ⌈ b 2 ⌉ h - 2 {\displaystyle n_{\min} = 2\left\lceil {\tfrac {b}{2}\right\rceil ^{h-1}-2\left\lceil {\tfrac ${$ b}{2}\right\rceil ^{h-2}}
$n_{\mathrm {kmin} }=2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-1$ 키 $n_{\mathrm {kmin} }=2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-1$ 는 $n_{\mathrm {kmin} }=2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-1$ 입니다 = $n_{\mathrm {kmin} }=2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-1$ 2 $n_{\mathrm {kmin} }=2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-1$ ⌉ b 2 ⌈ h - 1 ${\$ displaystyle n_{\mathrm {kmin} = 2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-1}
최대 키 수는 $n_{\mathrm {kmax} }=b^{h}-1$ $n_{\mathrm {kmax} }=b^{h}-1$ = $n_{\mathrm {kmax} }=b^{h}-1$ - 1 {\displaystyle n_{\mathrm {kmax $}$ = b^{h}-1}입니다.
트리를 저장하는 데 필요한 공간은 $O(n)$ ${\displaystyle$ O $(n)}$ 입니다.
레코드를 삽입하려면 $O(\log _{b}n)$ $O(\log _{b}n)$ ⁡ $n$ ) ${\displaystyle O(\log$ _{b}n)} 작업이 필요합니다.
레코드를 찾으려면 $O(\log _{b}n)$ $O(\log _{b}n)$ ⁡ $n$ ) ${\displaystyle O(\log$ _{b}n)} 작업이 필요합니다.
(이전에 위치한) 레코드를 제거하려면 $O(\log _{b}n)$ $O(\log _{b}n)$ ⁡ $n$ ) ${\displaystyle O(\log$ _{b}n)} 작업이 필요합니다.
범위 내에서 발생하는 k개 요소로 범위 쿼리를 수행하려면 $O(\log _{b}n+k)$ $O(\log _{b}n+k)$ ⁡ $n$ + k) ${\displaystyle O(\log$ _{b}n+k)} 작업이 필요합니다.
B+ 트리 구조는 레코드 수가 증가/감소함에 따라 확장/수축됩니다. B+ 나무의 크기에는 제한이 없습니다. 따라서 데이터베이스 시스템의 사용성이 향상됩니다.
균형 잡힌 트리 특성으로 인해 구조의 변경은 성능에 영향을 미치지 않습니다.^[6]
데이터는 잎 노드에 저장되며 내부 노드의 분기가 늘어나면 트리의 높이가 줄어 검색 시간이 단축됩니다. 결과적으로 2차 저장 장치에서 잘 작동합니다.^[7]
모든 레코드는 리프 노드에만 저장되고 연결된 목록에서 순차적으로 정렬되기 때문에 검색이 매우 간단해집니다.
B+ 트리를 사용하여 범위 검색 또는 부분 검색을 검색할 수 있습니다. 이것은 나무 구조물을 횡단함으로써 더 쉽고 빠르게 만들어 집니다. 이 기능은 B+ 트리 구조를 다양한 검색 방법에 적용합니다.^[6]

알고리즘

서치

우리는 B+ Tree에서 $k값$ 을 찾고 있습니다. 이는 뿌리에서 시작하여 $k$ 값을 포함할 수 있는 잎을 찾고 있음을 의미합니다. 각 노드에서 우리가 따라야 할 내부 노드를 파악합니다. 내부 B+ 트리 노드에는 $m\leq b$ $m\leq b$ b $m\leq b$ 개의 $m\leq b$ 자식이 있으며, 이들 모두는 서로 다른 하위 구간을 나타냅니다. $m개$ 의 항목을 선형 검색하여 해당 하위 항목을 선택한 다음 최종적으로 리프에 도달하면 원하는 키에 대해 $n개$ 의 요소를 선형 검색합니다. 트리의 각 링에서 모든 자식의 한 가지 분기만 통과하기 때문에 $O(\log N)$ ⁡ N) ${\displaystyle O(\$ log N)} 런타임을 달성하며, $여기$ 서 N은 B+ 트리의 잎에 저장된 키의 총 수이다.

function search(k, root)는 leaf = leaf_search(k, root)로 leaf.keys (): 만약 k = leaf_key: true return false

function leaf_search(k, node)는 노드가 리프인 경우: return node llet p = node. $children$  ()은 l = node.left_side_intervals() assert p = l + 1 {\displaystyle p = l + 1} 이 1에서 m - 1까지의 i에 대해 m = p.len ()을 허용합니다: k ≤ l [ i ] {\displaystyle k\leq l[i]} : return leaf_search(k, p[i]) return leaf_search (k, p[m])

이 의사 코드는 1-기반 배열 인덱싱을 사용합니다.

삽입

검색을 수행하여 새 레코드가 어떤 노드로 들어가야 하는지 결정합니다.
노드가 가득 차 있지 않으면(삽입 후 최대 b - $b-1$ $b-1$ 항목 $b-1$ ) 레코드를 추가합니다.
그렇지 않으면 새 레코드를 삽입하기 전에
- 노드를 분할합니다.
  - 원래 노드에 ⎡(L+1)/2개의 ⎤ 항목이 있습니다.
  - 새 노드에 ⎣(L+1)/2개의 ⎦ 항목이 있습니다.
- ⎡(L+1)/2 ⎤번째 키를 부모에 복사하고 새 노드를 부모에 삽입합니다.
- 분할할 필요가 없는 부모를 찾을 때까지 반복합니다.
- 새 노드에 새 레코드를 삽입합니다.
뿌리가 갈라지면 부모가 빈 것처럼 처리하고 위의 윤곽선으로 갈라집니다.

B+ 나무는 잎이 아닌 뿌리에서 자랍니다.^[1]

벌크로딩

데이터 레코드 모음이 주어지면 일부 키 필드에 B+ 트리 인덱스를 만들고자 합니다. 하나의 접근법은 각 레코드를 빈 트리에 삽입하는 것입니다. 그러나 각 항목은 루트에서 시작하여 적절한 리프 페이지로 내려가야 하기 때문에 상당히 비쌉니다. 효율적인 대안은 대량 적재를 사용하는 것입니다.

첫 번째 단계는 데이터 항목을 오름차순으로 검색 키에 따라 정렬하는 것입니다.
루트 역할을 할 빈 페이지를 할당하고 첫 번째 페이지의 항목에 포인터를 삽입합니다.
루트가 가득 차면 루트를 분할하고 새로운 루트 페이지를 만듭니다.
모든 항목이 인덱싱될 때까지 리프 레벨 바로 위의 가장 오른쪽 인덱스 페이지에 항목을 계속 삽입합니다.

참고:

리프 레벨 위의 가장 오른쪽 인덱스 페이지가 채워지면 분할됩니다.
이 작업은 결과적으로 가장 오른쪽 인덱스 페이지를 루트에 한 단계 더 가깝게 분할하게 할 수 있습니다.
분할은 뿌리에서 잎 수준까지의 가장 오른쪽 경로에서만 발생합니다.^[8]

삭제

삭제 알고리즘의 목적은 트리 구조에서 원하는 엔트리 노드를 제거하는 것입니다. 노드가 발견되지 않을 때까지 해당 노드에서 삭제 알고리즘을 재귀적으로 호출합니다. 각 함수 호출에 대해 인덱스를 사용하여 노드를 찾을 때까지 탐색한 다음 다시 루트로 작업합니다.

제거하고자 하는 항목 L에서:

- 만약 L이 반 이상 차면 끝입니다.

- L에 d-1개의 항목만 있는 경우 형제(L과 동일한 부모를 가진 인접 노드)에서 빌려 다시 배포합니다.

두 형제 노드의 재배포가 발생한 후에는 부모 노드를 업데이트하여 이 변경 사항을 반영해야 합니다. 두 번째 형제를 가리키는 인덱스 키는 해당 노드의 가장 작은 값을 가져와야 인덱스 키가 됩니다.

- 재배포에 실패할 경우 L과 형제를 병합합니다. 병합 후 삭제된 항목을 가리키는 인덱스 키를 삭제하여 상위 노드를 업데이트합니다. 즉, 병합이 발생한 경우 L의 부모에서 항목(L 또는 형제자매를 가리킴)을 삭제해야 합니다.

참고: 병합은 루트로 전파될 수 있으며, 이는 높이가 감소함을 의미합니다.^[9]

실행

B+ 트리의 잎(가장 아래쪽 인덱스 블록)은 종종 연결된 목록에서 서로 연결됩니다. 이는 블록을 통한 범위 쿼리 또는 (순서화된) 반복을 더 간단하고 효율적으로 만듭니다(비록 이러한 추가 없이도 위에서 언급한 상한을 달성할 수 있지만). 이것은 트리의 공간 소모나 유지 보수를 실질적으로 증가시키지 않습니다. 이것은 B-트리보다 B+트리의 중요한 장점 중 하나를 보여줍니다. B-트리에서는 모든 키가 잎에 존재하지 않기 때문에 이러한 순서 연결 목록을 구성할 수 없습니다. 따라서 B+트리는 데이터베이스 시스템 인덱스로서 특히 유용하며, 여기서 데이터는 일반적으로 디스크에 존재합니다. 이는 B+트리가 실제로 데이터 자체를 수용하기 위한 효율적인 구조를 제공하기 때문입니다(이를 인덱스 구조 "대체 1"에서^[10]^{: 238} 설명함).

저장 시스템의 블록 크기가 B바이트이고 저장할 키의 크기가 k인 경우, 가장 효율적인 B+ 트리는 $b={\tfrac {B}{k}}-1$ = $b={\tfrac {B}{k}}-1$ - ${\$ displaystyle b = {\tfrac {B}{k}-1}인 경우입니다. 이론적으로 일회성이 필요하지는 않지만 실제로는 인덱스 블록이 차지하는 공간이 약간 있습니다(예: 리프 블록의 링크된 목록 참조). 인덱스 블록이 스토리지 시스템의 실제 블록보다 약간 큰 경우 성능이 크게 저하되므로 주의해야 합니다.

B+ 트리의 노드가 요소의 배열로 구성된 경우, 요소를 삽입하거나 삭제하는 데 상당한 시간이 걸릴 수 있습니다. 이 경우 배열의 절반이 평균적으로 이동해야 하기 때문입니다. 이 문제를 극복하기 위해 노드 내부의 요소를 배열 대신 이진 트리나 B+ 트리로 구성할 수 있습니다.

B+ 트리는 RAM에 저장된 데이터에도 사용할 수 있습니다. 이 경우 블록 크기에 대한 합리적인 선택은 프로세서의 캐시 라인 크기일 것입니다.

일부 압축 기법을 사용하여 B+ 트리의 공간 효율성을 향상시킬 수 있습니다. 한 가지 가능성은 델타 인코딩을 사용하여 각 블록에 저장된 키를 압축하는 것입니다. 내부 블록의 경우 키나 포인터를 압축하여 공간을 절약할 수 있습니다. 문자열 키의 경우 다음과 같은 기술을 사용하여 공간을 절약할 수 있습니다. 일반적으로 내부 블록의 i번째 항목에는 $i+1$ $i+1$ + $i+1$ 1 {\ $display i+$ 1}의 첫 번째 키가 포함됩니다 $i+1$ 전체 키를 저장하는 대신 블록 i의 마지막 키보다 엄밀하게 큰(사전식 순서로) 블록 $i+1$ $i+1$ + 1 $i+1$ 의 첫 번째 키의 가장 짧은 접두사를 저장할 수 있습니다. 포인터를 압축하는 간단한 방법도 있습니다. $i,i+1,...i+k$ 우리가 어떤 연속적인 블록 $i,i+1,...i+k$ $i,i+1,...i+k$ + $i,i+1,...i+k$ $i,i+1,...i+k$ i + k {\ $displaystyle$ i, $i,i+1,...i+k$ i + 1, $...$ $i+k}$ 은 $i,i+1,...i+k$ (는) 연속적으로 저장되며, 그러면 첫 번째 블록에 대한 포인터와 연속적인 블록의 카운트만 저장하면 됩니다.

위의 모든 압축 기술에는 몇 가지 단점이 있습니다. 먼저, 단일 요소를 추출하려면 전체 블록을 압축 해제해야 합니다. 이 문제를 극복하기 위한 하나의 기법은 각 블록을 서브 블록으로 나누어 별도로 압축하는 것입니다. 이 경우 요소를 검색하거나 삽입하면 전체 블록 대신 하위 블록의 압축을 해제하거나 압축하기만 하면 됩니다. 압축 기법들의 또 다른 단점은 저장된 요소들의 수가 각 블록 내에서 요소들이 얼마나 잘 압축되는지에 따라 블록마다 상당히 다를 수 있다는 것입니다.

적용들

파일 시스템

ReiserFS, NSS, XFS, JFS, ReFS 및 BFS 파일 시스템은 모두 메타데이터 인덱싱을 위해 이러한 트리를 사용하며, BFS는 디렉토리 저장을 위해 B+ 트리를 사용합니다. NTFS는 디렉토리 및 보안 관련 메타데이터 인덱싱에 B+ 트리를 사용합니다. EXT4는 파일 익스텐트 인덱싱을 위해 익스텐트 트리(수정된 B+ 트리 데이터 구조)를 사용합니다.^[11] APFS는 B+ 트리를 사용하여 파일 시스템 개체 ID에서 디스크의 위치로 매핑을 저장하고 파일 시스템 레코드(디렉토리 포함)를 저장합니다.^[12]

데이터베이스 시스템

IBM Db2,^[10] Informix,^[10] Microsoft SQL Server,^[10] Oracle 8,^[10] Sybase ASE ^[10]및 SQLite와^[13] 같은 관계형 데이터베이스 관리 시스템은 테이블 인덱스의 경우 이러한 유형의 트리를 지원하지만 각 시스템은 기본 B+ 트리 구조를 변형 및 확장으로 구현합니다. CouchDB^[14] 및 Tokyo Cabinary와^[15] 같은 많은 NoSQL 데이터베이스 관리 시스템에서도 데이터 액세스 및 저장을 위해 이러한 유형의 트리를 지원합니다.

고차원 데이터베이스에서 특정 쿼리 객체와 유사한 객체를 찾는 것은 이러한 시스템에서 가장 자주 사용되지만 비용이 많이 드는 절차 중 하나입니다.^{[citation needed]} 이러한 상황에서 B+ 트리를 사용하여 가장 가까운 이웃을 찾는 것이 생산적입니다.^[16]

아이디스턴스

B+ 트리는 아이디스턴스라는 인덱스 검색 방법을 효율적으로 구성하는 데 사용됩니다. 아이디스턴스는 고차원 메트릭 공간에서 k개의 가장 가까운 이웃(kNN)을 검색합니다. 이러한 고차원 공간의 데이터는 공간 또는 파티션 전략에 따라 분할되며 각 파티션은 파티션에 대해 근접한 인덱스 값을 갖습니다. 여기서 이러한 지점은 B+ 트리를 사용하여 효율적으로 구현할 수 있으므로 쿼리는 단일 차원 범위 검색에 매핑됩니다. 즉, iDistance 기법은 순차 스캔을 가속화하는 방법으로 볼 수 있습니다. iDistance는 데이터 파일의 처음부터 끝까지 레코드를 스캔하는 대신 가장 가까운 이웃을 일찍 얻을 수 있는 지점에서 매우 높은 확률로 스캔을 시작합니다.^[17]

NVRAM

비휘발성 랜덤 액세스 메모리(NVRAM)는 비정전 전력 소모 및 셀 메모리의 높은 견고성 때문에 B+ 트리 구조를 사물 인터넷(IoT) 시스템의 주요 메모리 액세스 기법으로 사용해 왔습니다. B+는 메모리로의 데이터 트래픽을 효율적으로 규제할 수 있습니다. 또한, 일부 많이 사용되는 리프 또는 기준점의 주파수에 대한 고급 전략으로 B+ 트리는 데이터베이스 시스템의 내구성을 높이는 데 상당한 결과를 보여줍니다.^[18]

참고 항목

참고문헌

^ ^a ^b ^c ^d Navathe, Ramez Elmasri, Shamkant B. (2010). Fundamentals of database systems (6th ed.). Upper Saddle River, N.J.: Pearson Education. pp. 652–660. ISBN 9780136086208.{{cite book}}: CS1 maint: 다중 이름: 저자 목록 (링크)
^ Comer, Douglas (1979). "Ubiquitous B-Tree". ACM Computing Surveys. 11 (2): 121–137. doi:10.1145/356770.356776. S2CID 101673.
^ ^a ^b Pollari-Malmi, Kerttu. ""B+ trees"" (PDF). Computer Science, Faculty of Science, University of Helsinki. p. 3. Archived from the original (PDF) on 2021-04-14.
^ Silberschatz, Abraham; Korth, Henry F.; Sudarshan, S. (2020). Database system concepts (Seventh ed.). New York, NY: McGraw-Hill Education. ISBN 978-1-260-08450-4.
^ Grust, Torsten (Summer 2013). ""Tree-Structured Indexing: ISAM and B+-trees"" (PDF). Logo der Universität Tübingen Department of Computer Science: Database Systems. p. 84. Archived from the original (PDF) on 2020-10-31.
^ ^a ^b Zeitler, Erik; Risch, Tore (2010). "Scalable Splitting of Massive Data Streams". Database Systems for Advanced Applications. Lecture Notes in Computer Science. Vol. 5982. pp. 184–198. doi:10.1007/978-3-642-12098-5_15. ISBN 978-3-642-12097-8.
^ Xu, Chang; Shou, Lidan; Chen, Gang; Yan, Cheng; Hu, Tianlei (2010). "Update Migration: An Efficient B+ Tree for Flash Storage". Database Systems for Advanced Applications. Lecture Notes in Computer Science. Vol. 5982. pp. 276–290. doi:10.1007/978-3-642-12098-5_22. ISBN 978-3-642-12097-8.
^ "ECS 165B: Database System Implementation Lecture 6" (PDF). UC Davis CS department. April 9, 2010. pp. 21–23.
^ Ramakrishnan, Raghu; Johannes Gehrke (2003). Database management systems (3rd ed.). Boston: McGraw-Hill. ISBN 0-07-246563-8. OCLC 49977005.
^ ^a ^b ^c ^d ^e ^f Ramakrishnan Raghu, Gerke Johannes – 데이터베이스 관리 시스템, McGraw-Hill Higher Education (2000), 2판 (en) 267페이지
^ Giampaolo, Dominic (1999). Practical File System Design with the Be File System (PDF). Morgan Kaufmann. ISBN 1-55860-497-9. Archived from the original (PDF) on 2017-02-13. Retrieved 2014-07-29.
^ "B-Trees". Apple File System Reference (PDF). Apple Inc. 2020-06-22. p. 122. Retrieved 2021-03-10.
^ SQLite 버전 3 개요
^ CouchDB 가이드(3번째 단락 이후 참고 참조)
^ 도쿄 내각 참고 자료 2009년 9월 12일 웨이백 기계에서 보관
^ Database Systems for Advanced Applications. Japan. 2010.{{cite book}}: CS1 maint: 위치 누락 게시자(링크)
^ Jagadish, H. V.; Ooi, Beng Chin; Tan, Kian-Lee; Yu, Cui; Zhang, Rui (June 2005). "iDistance: An adaptive B+-tree based indexing method for nearest neighbor search". ACM Transactions on Database Systems. 30 (2): 364–397. doi:10.1145/1071610.1071612. ISSN 0362-5915. S2CID 967678.
^ Dharamjeet; Chen, Tseng-Yi; Chang, Yuan-Hao; Wu, Chun-Feng; Lee, Chi-Heng; Shih, Wei-Kuan (December 2021). "Beyond Write-Reduction Consideration: A Wear-Leveling-Enabled B⁺-Tree Indexing Scheme Over an NVRAM-Based Architecture". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 40 (12): 2455–2466. doi:10.1109/TCAD.2021.3049677. ISSN 0278-0070. S2CID 234157183.

외부 링크

구현

[Navathe-1] Navathe, Ramez Elmasri, Shamkant B. (2010). Fundamentals of database systems (6th ed.). Upper Saddle River, N.J.: Pearson Education. pp. 652–660. ISBN 9780136086208.{{cite book}}: CS1 maint: 다중 이름: 저자 목록 (링크)

[2] Comer, Douglas (1979). "Ubiquitous B-Tree". ACM Computing Surveys. 11 (2): 121–137. doi:10.1145/356770.356776. S2CID 101673.

[algorithms-pdf-3] Pollari-Malmi, Kerttu. ""B+ trees"" (PDF). Computer Science, Faculty of Science, University of Helsinki. p. 3. Archived from the original (PDF) on 2021-04-14.

[4] Silberschatz, Abraham; Korth, Henry F.; Sudarshan, S. (2020). Database system concepts (Seventh ed.). New York, NY: McGraw-Hill Education. ISBN 978-1-260-08450-4.

[total-order-5] Grust, Torsten (Summer 2013). ""Tree-Structured Indexing: ISAM and B+-trees"" (PDF). Logo der Universität Tübingen Department of Computer Science: Database Systems. p. 84. Archived from the original (PDF) on 2020-10-31.

[:0-6] Zeitler, Erik; Risch, Tore (2010). "Scalable Splitting of Massive Data Streams". Database Systems for Advanced Applications. Lecture Notes in Computer Science. Vol. 5982. pp. 184–198. doi:10.1007/978-3-642-12098-5_15. ISBN 978-3-642-12097-8.

[7] Xu, Chang; Shou, Lidan; Chen, Gang; Yan, Cheng; Hu, Tianlei (2010). "Update Migration: An Efficient B+ Tree for Flash Storage". Database Systems for Advanced Applications. Lecture Notes in Computer Science. Vol. 5982. pp. 276–290. doi:10.1007/978-3-642-12098-5_22. ISBN 978-3-642-12097-8.

[8] "ECS 165B: Database System Implementation Lecture 6" (PDF). UC Davis CS department. April 9, 2010. pp. 21–23.

[9] Ramakrishnan, Raghu; Johannes Gehrke (2003). Database management systems (3rd ed.). Boston: McGraw-Hill. ISBN 0-07-246563-8. OCLC 49977005.

[DMS-10] ^ ^a ^b ^c ^d ^e ^f Ramakrishnan Raghu, Gerke Johannes – 데이터베이스 관리 시스템, McGraw-Hill Higher Education (2000), 2판 (en) 267페이지

[practical-book-11] Giampaolo, Dominic (1999). Practical File System Design with the Be File System (PDF). Morgan Kaufmann. ISBN 1-55860-497-9. Archived from the original (PDF) on 2017-02-13. Retrieved 2014-07-29.

[12] "B-Trees". Apple File System Reference (PDF). Apple Inc. 2020-06-22. p. 122. Retrieved 2021-03-10.

[SQLite-13] SQLite 버전 3 개요

[CouchDB-14] CouchDB 가이드(3번째 단락 이후 참고 참조)

[TC-15] 도쿄 내각 참고 자료 2009년 9월 12일 웨이백 기계에서 보관

[16] Database Systems for Advanced Applications. Japan. 2010.{{cite book}}: CS1 maint: 위치 누락 게시자(링크)

[17] Jagadish, H. V.; Ooi, Beng Chin; Tan, Kian-Lee; Yu, Cui; Zhang, Rui (June 2005). "iDistance: An adaptive B+-tree based indexing method for nearest neighbor search". ACM Transactions on Database Systems. 30 (2): 364–397. doi:10.1145/1071610.1071612. ISSN 0362-5915. S2CID 967678.

[18] Dharamjeet; Chen, Tseng-Yi; Chang, Yuan-Hao; Wu, Chun-Feng; Lee, Chi-Heng; Shih, Wei-Kuan (December 2021). "Beyond Write-Reduction Consideration: A Wear-Leveling-Enabled B⁺-Tree Indexing Scheme Over an NVRAM-Based Architecture". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 40 (12): 2455–2466. doi:10.1109/TCAD.2021.3049677. ISSN 0278-0070. S2CID 234157183.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

v t 트리 데이터 구조
트리 검색 (동적 집합/연관 배열)	2–3 2–3–4 AA (a,b) AVL B B+ B* 나^x (최적) 이진 검색 댄싱 HT트리 간격 주문통계 (좌측)레드-블랙 희생양 스플레이 T 트랩 UB 무게 균형을 이루다
수북이	이진법 이항 브로달 피보나치 레프트 페어링 스큐 반 엠데 보아스 약한
시도하다	크트리 C-trie(압축 ADT) 해쉬 라딕스 접미사 삼원검색 엑스패스트 와이패스트
공간 데이터 분할 트리	공 BK BSP 데카르트 힐베르트 R k-d(implicit k-d) M 미터법 MVP 옥트리 PH 우선순위 R 쿼드 R R+ R* 부분 VP X
다른 나무들	덮다 지수적 펜윅 손가락. 프랙탈 트리 인덱스 퓨전 해시달력 아이디스턴스 카아리 좌충우돌 링크/컷 로그 구조 병합 머클 p q. 범위 SPQR 정상

Search