Update of B+-Trees - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:데이터베이스 시스템(\|[^\]]+)?\]\] +분류:데이터베이스\1)

2026-01-15T12:52:33Z

봇: 자동으로 텍스트 교체 (-\[\[분류:데이터베이스 시스템(\|[^\]]+)?\]\] +분류:데이터베이스\1)

← 이전 판		2026년 1월 15일 (목) 12:52 판
1번째 줄:		1번째 줄:
	[[분류:데이터베이스 ~~시스템~~]]		[[분류:데이터베이스]]
	==개요==		==개요==
	레코드(Record)가 릴레이션(relation)에 삽입/삭제(insert/delete)될 때, 해당 릴레이션에 대한 인덱스들도 이에 맞게 갱신되어야 한다. 이때 레코드에 대한 갱신(upadate) 작업은 기존 레코드를 삭제한 후, 그 위치에 갱신된 레코드를 삽입하는 것으로 수행될 수 있다. 따라서 삽입/삭제 작업만을 고려하면 된다. 이때 삽입과 삭제 작업은 조회(lookup)보다 더 복잡한데, 삽입 결과로 노드가 너무 커질 경우, 분할(split)이 필요하고, 삭제 결과로 노드가 너무 적어질 경우(⌈n/2⌉ 포인터보다 적은 경우)에는 노드 사이의 결합이 필요할 수 있기 때문이다. 이때 노드를 분할하거나 병합할 때는 트리의 균형(balance)이 유지되도록 해야 한다.		레코드(Record)가 릴레이션(relation)에 삽입/삭제(insert/delete)될 때, 해당 릴레이션에 대한 인덱스들도 이에 맞게 갱신되어야 한다. 이때 레코드에 대한 갱신(upadate) 작업은 기존 레코드를 삭제한 후, 그 위치에 갱신된 레코드를 삽입하는 것으로 수행될 수 있다. 따라서 삽입/삭제 작업만을 고려하면 된다. 이때 삽입과 삭제 작업은 조회(lookup)보다 더 복잡한데, 삽입 결과로 노드가 너무 커질 경우, 분할(split)이 필요하고, 삭제 결과로 노드가 너무 적어질 경우(⌈n/2⌉ 포인터보다 적은 경우)에는 노드 사이의 결합이 필요할 수 있기 때문이다. 이때 노드를 분할하거나 병합할 때는 트리의 균형(balance)이 유지되도록 해야 한다.

Pinkgo: /* Complexity of B+-Tree Updates */

2025-06-11T04:57:55Z

Complexity of B+-Tree Updates

← 이전 판		2025년 6월 11일 (수) 04:57 판
110번째 줄:		110번째 줄:

	==Complexity of B<sup>+</sup>-Tree Updates==		==Complexity of B<sup>+</sup>-Tree Updates==
	B<sup>+</sup>-트리 구조의 삽입/삭제 연산이 복잡하더라도, 이는 상대적으로 적은 수의 I/O 연산을 필요로 하며, 이는 중요한 이점이다. 삽입/삭제 연산에 대해 요구되는 I/O 연산의 수는 최악의 경우 <code>log<sub>⌈n∕2⌉</sub>(N)</code>에 비례하기 때문이다. <ref>삭제 연산의 경우는, 검색키가 중복되지 않는다는 전제 조건을 필요로 한다.</ref> 이에 따라 B<sup>+</sup>-트리 구조의 삽입/삭제 연산은 속도가 빠르다.		B<sup>+</sup>-트리 구조의 삽입/삭제 연산이 복잡하더라도, 이는 상대적으로 적은 수의 I/O 연산을 필요로 하며, 이는 중요한 이점이다. 삽입/삭제 연산에 대해 요구되는 I/O 연산의 수는 최악의 경우 <code>log<sub>⌈n∕2⌉</sub>(N)</code>에 비례하기 때문이다. <ref>삭제 연산의 경우는, 검색키가 중복되지 않는다는 전제 조건을 필요로 한다.</ref> 이에 따라 B<sup>+</sup>-트리 구조의 삽입/삭제 연산은 속도가 빠르다.

			B<sup>+</sup>-트리에서 실제로 필요한 연산의 수는 더 적다. 예를 들어 fan-out<ref>트리 기반 자료구조에서 하나의 노드가 가질 수 있는 최대 자식 수이다.</ref>이 100이고, 각 leaf 노드에 대한 접근이 균등하다면, leaf 노드의 부모 노드는 leaf 노드보다 100배 더 자주 접근된다. 반대로 말하면, non-leaf 노드 부모 개수는 leaf 노드의 개수의 1/100보다 약간 더 많은 수준이다. 따라서 대부분의 non-leaf 노드는 데이터베이스 버퍼에 존재하며, 결과적으로 한번의 탐색에 1~2회의 I/O 연산만이 필요하다. 또한 대부분의 삽입/삭제 연산은 분할, 합병 등을 필요로 하지 않으며, 분할, 합병은 매우 적은 빈도로 일어난다. 이에 따라 대부분의 삽입/삭제 연산은 leaf 노드에만 영향을 준다.

			B<sup>+</sup>-트리는 최소한 노드가 절반은 차있도록 강제하지만, 실제 상황에서는 삽입되는 항목들의 정렬 여부에 따라 그 결과가 다르다. 항목들이 무작위 순서로 삽입된다면 트리 구조 내의 노드는 평균적으로 2/3 이상 차있다. 하지만 정렬된 순서로 삽입될 경우, 노드는 1/2 정도만 점유된다.

	==각주==		==각주==

Pinkgo: /* 각주 */

2025-06-11T04:11:08Z

각주

← 이전 판		2025년 6월 11일 (수) 04:11 판
108번째 줄:		108번째 줄:
	</syntaxhighlight>		</syntaxhighlight>
	위 코드에서 <code>swap variables(N, N')</code> 함수는 단순히 변수 N과 N'의 값을 바꾸는 역할을 하며, 트리 구조 자체에는 영향이 없다.		위 코드에서 <code>swap variables(N, N')</code> 함수는 단순히 변수 N과 N'의 값을 바꾸는 역할을 하며, 트리 구조 자체에는 영향이 없다.

			==Complexity of B<sup>+</sup>-Tree Updates==
			B<sup>+</sup>-트리 구조의 삽입/삭제 연산이 복잡하더라도, 이는 상대적으로 적은 수의 I/O 연산을 필요로 하며, 이는 중요한 이점이다. 삽입/삭제 연산에 대해 요구되는 I/O 연산의 수는 최악의 경우 <code>log<sub>⌈n∕2⌉</sub>(N)</code>에 비례하기 때문이다. <ref>삭제 연산의 경우는, 검색키가 중복되지 않는다는 전제 조건을 필요로 한다.</ref> 이에 따라 B<sup>+</sup>-트리 구조의 삽입/삭제 연산은 속도가 빠르다.

	==각주==		==각주==

Pinkgo: /* = */

2025-06-11T04:03:42Z

@@ 64번째 줄: / 64번째 줄: @@
 * 이 과정은 root 노드까지 재귀적으로 적용되거나, 부모 노드가 삭제 후에도 충분히 크거나, 삭제가 아닌 재분배가 일어날 때까지 반복한다.
-===
+===Pseudocode of the Deletion Algorithm===
 ==각주==

Pinkgo: /* Deletion */

2025-06-11T03:57:44Z

Deletion

← 이전 판		2025년 6월 11일 (수) 03:57 판
59번째 줄:		59번째 줄:
	Figure 6에서 "Gold"를 삭제하면, 그 결과는 figure 7과 같다. "Gold"의 삭제는 leaf 노드를 조건에 미달하도록 하며, 형제 노드와 병합하여 이를 해결한다. 이 과정에서 부모 노드("Kim"을 포함한 비리프 노드)에서의 항목이 삭제되며, 이에 따라 부모 노드도 미달 상태가 된다. 이 상황에서는 부모 노드가 형제 노드와 결합 가능하며, 따라서 부모 노드가 서로 병합되면서 부모의 부모 노드(root 노드)에 있던 "Gold"가 병합된 노드로 내려온다. 이에 따라 root 노드 또한 조건에 미달하게 되어 삭제되고, 부모 노드가 root 노드가 되며 B<sup>+</sup>-트리의 높이가 1 감소한다.		Figure 6에서 "Gold"를 삭제하면, 그 결과는 figure 7과 같다. "Gold"의 삭제는 leaf 노드를 조건에 미달하도록 하며, 형제 노드와 병합하여 이를 해결한다. 이 과정에서 부모 노드("Kim"을 포함한 비리프 노드)에서의 항목이 삭제되며, 이에 따라 부모 노드도 미달 상태가 된다. 이 상황에서는 부모 노드가 형제 노드와 결합 가능하며, 따라서 부모 노드가 서로 병합되면서 부모의 부모 노드(root 노드)에 있던 "Gold"가 병합된 노드로 내려온다. 이에 따라 root 노드 또한 조건에 미달하게 되어 삭제되고, 부모 노드가 root 노드가 되며 B<sup>+</sup>-트리의 높이가 1 감소한다.

	이때 주의할 점은 삭제 결과로 인해 leaf 노드에는 더 이상 존재하지 않는 검색키값이 non-leaf 노드에는 존재할 수 있다는 것이다. 예를 들어 figure 7에서 "Gold"는 leaf 노드에서 삭제되었으나, non-leaf 노드에는 계속 존재한다.		이때 주의할 점은 삭제 결과로 인해 leaf 노드에는 더 이상 존재하지 않는 검색키값이 non-leaf 노드에는 존재할 수 있다는 것이다. 예를 들어 figure 7에서 "Gold"는 leaf 노드에서 삭제되었으나, non-leaf 노드에는 계속 존재한다. 아래는 B<sup>+</sup>트리에 대한 일반적인 삽입 기법이다:
			* leaf 노드에서 목표한 값을 삭제한다.
			* 해당 leaf 노드가 너무 작아져서 삭제해야 한다면, 부모 노드에서도 해당 항목을 삭제한다.
			* 이 과정은 root 노드까지 재귀적으로 적용되거나, 부모 노드가 삭제 후에도 충분히 크거나, 삭제가 아닌 재분배가 일어날 때까지 반복한다.

			===

	==각주==		==각주==

Pinkgo: /* Deletion */

2025-06-11T03:54:22Z

Deletion

← 이전 판		2025년 6월 11일 (수) 03:54 판
48번째 줄:		48번째 줄:

	==Deletion==		==Deletion==
			[[파일:Deletion of “Srinivasan” from the B+-tree of Figure 3.png\|가운데\|섬네일\|500x500픽셀\|Figure 5. Deletion of “Srinivasan” from the B+-tree of Figure 3]]
	노드 내 항목의 삭제는 해당 노드 안에 너무 적은 수의 포인터가 남는 상황을 야기할 수 있다. 우선, figure 3의 B<sup>+</sup>-트리에서 “Srinivasan”을 삭제하는 상황을 고려하자. 이 결과는 figure 5에 나타나 있다. 이를 위해서는 먼저 [[Indexing#Queries on B+-Trees\|find()]] 알고리즘을 바탕으로 “Srinivasan” 항목을 찾는다. “Srinivasan” 항목을 리프 노드에서 삭제하면, 해당 노드는 “Wu” 항목 하나만 남는다. 이때 해당 figure 에서 n = 4이고, <code>1 < ⌈(n−1)/2⌉</code>이므로, 최소 절반은 차 있어야 한다는 조건을 만족시키기 위해 해당 노드를 같은 레벨에서의 노드(형제 노드)와 병합하거나 항목을 재분배 해야 한다.		노드 내 항목의 삭제는 해당 노드 안에 너무 적은 수의 포인터가 남는 상황을 야기할 수 있다. 우선, figure 3의 B<sup>+</sup>-트리에서 “Srinivasan”을 삭제하는 상황을 고려하자. 이 결과는 figure 5에 나타나 있다. 이를 위해서는 먼저 [[Indexing#Queries on B+-Trees\|find()]] 알고리즘을 바탕으로 “Srinivasan” 항목을 찾는다. “Srinivasan” 항목을 리프 노드에서 삭제하면, 해당 노드는 “Wu” 항목 하나만 남는다. 이때 해당 figure 에서 n = 4이고, <code>1 < ⌈(n−1)/2⌉</code>이므로, 최소 절반은 차 있어야 한다는 조건을 만족시키기 위해 해당 노드를 같은 레벨에서의 노드(형제 노드)와 병합하거나 항목을 재분배 해야 한다.

	이 에제에서는 삭제당한 노드의 항목들을 왼쪽에 존재하는 형제 노드로 옮기고, 비어있는 오른쪽의 형제 노드를 삭제할 수 있다. 이때 노드가 삭제되면, 해당 노드를 가리키고 있던 부모 노드의 항목들도 삭제해야 한다. 예제에서 삭제할 항목은 (Srinivasan, n3)이고, n3은 “Srinivasan”이 들어 있는 leaf를 가리킨다. 해당 항목을 삭제하면, 부모 노드는 “Srinivasan”과 두 개의 포인터를 가졌던 상태에서 이제 하나의 포인터만 남게 되며, 검색키 값은 없어진다. n = 4이므로 1 < ⌈n/2⌉가 되어 부모 노드 역시 부족해진다. 이 경우 부모의 형제 노드를 살펴야 한다. Figure에서 형제 노드는 “Califieri”, “Einstein”, “Gold”를 포함하는 non-leaf 노드이다. 이때 이 노드와 병합하고 싶지만, 이 경우 포인터가 총 5개가 되어 최대값인 4를 초과하므로 병합할 수 없다. 따라서 포인터들을 재분배하여 두 노드가 최소 ⌈n/2⌉ = 2개의 자식 포인터를 갖도록 한다.		이 에제에서는 삭제당한 노드의 항목들을 왼쪽에 존재하는 형제 노드로 옮기고, 비어있는 오른쪽의 형제 노드를 삭제할 수 있다. 이때 노드가 삭제되면, 해당 노드를 가리키고 있던 부모 노드의 항목들도 삭제해야 한다. 예제에서 삭제할 항목은 (Srinivasan, n3)이고, n3은 “Srinivasan”이 들어 있는 leaf를 가리킨다. 해당 항목을 삭제하면, 부모 노드는 “Srinivasan”과 두 개의 포인터를 가졌던 상태에서 이제 하나의 포인터만 남게 되며, 검색키 값은 없어진다. n = 4이므로 1 < ⌈n/2⌉가 되어 부모 노드 역시 부족해진다. 이 경우 부모의 형제 노드를 살펴야 한다. Figure에서 형제 노드는 “Califieri”, “Einstein”, “Gold”를 포함하는 non-leaf 노드이다. 이때 이 노드와 병합하고 싶지만, 이 경우 포인터가 총 5개가 되어 최대값인 4를 초과하므로 병합할 수 없다. 따라서 포인터들을 재분배하여 두 노드가 최소 ⌈n/2⌉ = 2개의 자식 포인터를 갖도록 한다.

	재분배를 위해 왼쪽 형제 노드의 가장 오른쪽 포인터("Gold"를 가리키는 포인터)를 오른쪽에 있는 노드로 옮긴다. 이를 통해 오른쪽 형제 노드는 원래 포인터를 부족하게 가지고 있었지만, 비로소 2개의 포인터를 가짐으로서 전제 조건을 만족한다. 하지만 이 두개의 포인터는 어떤 검색키값에 의해서 구분되지 않으므로, 이 두 포인터가 가리키는 노드를 구분하기 위해서 해당 노드의 부모 노드에 있던 "Mozart"를 부족한 노드로 옮기고, "Gold" 노드를 부모 노드로 올린다.		재분배를 위해 왼쪽 형제 노드의 가장 오른쪽 포인터("Gold"를 가리키는 포인터)를 오른쪽에 있는 노드로 옮긴다. 이를 통해 오른쪽 형제 노드는 원래 포인터를 부족하게 가지고 있었지만, 비로소 2개의 포인터를 가짐으로서 전제 조건을 만족한다. 하지만 이 두개의 포인터는 어떤 검색키값에 의해서 구분되지 않으므로, 이 두 포인터가 가리키는 노드를 구분하기 위해서 해당 노드의 부모 노드에 있던 "Mozart"를 부족한 노드로 옮기고, "Gold" 노드를 부모 노드로 올린다.
			[[파일:Deletion of “Singh” and “Wu” from the B+-tree of Figure 5.png\|가운데\|섬네일\|500x500픽셀\|Figure 6. Deletion of “Singh” and “Wu” from the B+-tree of Figure 5]]
			다음으로, fiugre 5의 B<sup>+</sup>트리에서 검색키 값 "Singh"와 "Wu"를 삭제한다고 가정하자. 그 결과는 figure 6와 같다. 이 중 "Singh"의 삭제는 구조적으로 문제를 일으키지 않지만, "Wu"의 삭제는 leaf 노드가 조건<ref>Leaf 노드들은 ⌈(n-1)/2⌉ ~ n-1개의 검색키 값들을 가져야 한다.</ref>에 미달하도록 한다. 이때 왼쪽의 형제노드는 이미 최대 크기이므로, 값을 재분배해야 한다. 따라서 "Kim"이 속한 항목을 오른쪽의 "Mozart"가 속한 노드로 이동시켜 재분배한다. 또한, 부모 노드에서의 구분값은 "Mozart"에서 "Kim"으로 갱신된다.
			[[파일:Deletion of “Gold” from the B+-tree of Figure 6.png\|가운데\|섬네일\|500x500픽셀\|Figure 7. Deletion of “Gold” from the B+-tree of Figure 6]]
			Figure 6에서 "Gold"를 삭제하면, 그 결과는 figure 7과 같다. "Gold"의 삭제는 leaf 노드를 조건에 미달하도록 하며, 형제 노드와 병합하여 이를 해결한다. 이 과정에서 부모 노드("Kim"을 포함한 비리프 노드)에서의 항목이 삭제되며, 이에 따라 부모 노드도 미달 상태가 된다. 이 상황에서는 부모 노드가 형제 노드와 결합 가능하며, 따라서 부모 노드가 서로 병합되면서 부모의 부모 노드(root 노드)에 있던 "Gold"가 병합된 노드로 내려온다. 이에 따라 root 노드 또한 조건에 미달하게 되어 삭제되고, 부모 노드가 root 노드가 되며 B<sup>+</sup>-트리의 높이가 1 감소한다.

			이때 주의할 점은 삭제 결과로 인해 leaf 노드에는 더 이상 존재하지 않는 검색키값이 non-leaf 노드에는 존재할 수 있다는 것이다. 예를 들어 figure 7에서 "Gold"는 leaf 노드에서 삭제되었으나, non-leaf 노드에는 계속 존재한다.

	==각주==		==각주==

Pinkgo: /* Deletion */

2025-06-11T03:28:34Z

Deletion

Pinkgo: /* Insertion */

2025-06-11T03:14:52Z

Insertion

← 이전 판		2025년 6월 11일 (수) 03:14 판
9번째 줄:		9번째 줄:

	==Insertion==		==Insertion==
	[[파일:B+-tree for instructor file (n = 4).png\|섬네일\|Figure 1. B<sup>+</sup>-tree for ''instructor'' file (''n'' = 4)\|~~300x300px~~]]		[[파일:B+-tree for instructor file (n = 4).png\|섬네일\|Figure 1. B<sup>+</sup>-tree for ''instructor'' file (''n'' = 4)\|400x400px]]
	노드를 분할해야 하는 삽입 예제를 고려하기 위해, name 속성의 값이 "Adams"인 레코드를 instructor 릴레이션에 삽입한다고 하자. 그러기 위해서는 Figure 1의 B<sup>+</sup>트리에 "Adams" 항목을 삽입해야 한다. 이때 [[Indexing#Queries on B+-Trees\|find() 함수]]에서의 알고리즘에서의 동일한 방식을 사용하면 Adams"는 "Brandt", "Califieri", "Crick"을 포함하는 leaf 노드에 들어가야 한다. 하지만 이 leaf 노드에는 "Adams"를 삽입할 공간이 없으므로, 해당 leaf 노드는 두개의 노드로 분할되어야 한다. Figure 2는 "Adams" 삽입으로 인해 leaf 노드가 분할된 모습을 보여준다. "Adams"와 "Brandt"는 하나의 리프에, "Califieri"와 "Crick"은 다른 리프에 위치한다.		노드를 분할해야 하는 삽입 예제를 고려하기 위해, name 속성의 값이 "Adams"인 레코드를 instructor 릴레이션에 삽입한다고 하자. 그러기 위해서는 Figure 1의 B<sup>+</sup>트리에 "Adams" 항목을 삽입해야 한다. 이때 [[Indexing#Queries on B+-Trees\|find() 함수]]에서의 알고리즘에서의 동일한 방식을 사용하면 Adams"는 "Brandt", "Califieri", "Crick"을 포함하는 leaf 노드에 들어가야 한다. 하지만 이 leaf 노드에는 "Adams"를 삽입할 공간이 없으므로, 해당 leaf 노드는 두개의 노드로 분할되어야 한다. Figure 2는 "Adams" 삽입으로 인해 leaf 노드가 분할된 모습을 보여준다. "Adams"와 "Brandt"는 하나의 리프에, "Califieri"와 "Crick"은 다른 리프에 위치한다.
	[[파일:Split of leaf node on insertion of “Adams”.png\|섬네일\|Figure 2. Split of leaf node on insertion of “Adams”]]		[[파일:Split of leaf node on insertion of “Adams”.png\|섬네일\|Figure 2. Split of leaf node on insertion of “Adams”\|400x400픽셀]]
	[[파일:Insertion of “Adams” into the B+-tree of Figure 1.png\|섬네일\|Figure 3. Insertion of “Adams” into the B+-tree of Figure 1\|~~300x300px~~]]		[[파일:Insertion of “Adams” into the B+-tree of Figure 1.png\|섬네일\|Figure 3. Insertion of “Adams” into the B+-tree of Figure 1\|400x400px]]
	일반적으로는 n개의 검색키 값(리프 노드의 n−1개 키 값 + 삽입하려는 값)에서, 처음 <code>⌈n/2⌉</code> 개를 기존 노드에 유지하고 나머지를 새로 생성된 노드에 넣는다. 이때 leaf 노드를 분할한 이후에는 새 leaf 노드를 B<sup>+</sup>-트리 구조에 삽입해야 한다. 이 예제에서는 새롭게 생성된 노드의 최소 검색키 값이 "Califieri"이므로, <code>K = "Califieri"</code>이고, <code>P -> ("Califieri"로 시작하는 노드)</code>인 항목의 쌍을 부모 노드에 삽입해야 한다. Figure 3는 삽입 후의 B<sup>+</sup>트리를 보여준다. 이 경우 부모 노드에는 새 항목을 저장할 공간이 있었으므로, 추가적인 분할없이 가능했다. 만약 공간이 없었다면 부모 노드도 분할해야 하며, 이 경우, 부모의 부모에도 항목을 삽입해야 한다. 최악의 경우에는 root까지의 모든 노드가 분할되어야 할 수 있으며, root 노드가 분할되어야 할 수 있으며, 루트가 분할되면 전체 트리의 높이(height)는 1 증가한다.		일반적으로는 n개의 검색키 값(리프 노드의 n−1개 키 값 + 삽입하려는 값)에서, 처음 <code>⌈n/2⌉</code> 개를 기존 노드에 유지하고 나머지를 새로 생성된 노드에 넣는다. 이때 leaf 노드를 분할한 이후에는 새 leaf 노드를 B<sup>+</sup>-트리 구조에 삽입해야 한다. 이 예제에서는 새롭게 생성된 노드의 최소 검색키 값이 "Califieri"이므로, <code>K = "Califieri"</code>이고, <code>P -> ("Califieri"로 시작하는 노드)</code>인 항목의 쌍을 부모 노드에 삽입해야 한다. Figure 3는 삽입 후의 B<sup>+</sup>트리를 보여준다. 이 경우 부모 노드에는 새 항목을 저장할 공간이 있었으므로, 추가적인 분할없이 가능했다. 만약 공간이 없었다면 부모 노드도 분할해야 하며, 이 경우, 부모의 부모에도 항목을 삽입해야 한다. 최악의 경우에는 root까지의 모든 노드가 분할되어야 할 수 있으며, root 노드가 분할되어야 할 수 있으며, 루트가 분할되면 전체 트리의 높이(height)는 1 증가한다.
	[[파일:Insertion of “Lamport” into the B+-tree of Figure 3.png\|섬네일\|Figure 4. Insertion of “Lamport” into the B+-tree of Figure 3\|~~300x300px~~]]		[[파일:Insertion of “Lamport” into the B+-tree of Figure 3.png\|섬네일\|Figure 4. Insertion of “Lamport” into the B+-tree of Figure 3\|400x400px]]
	non-leaf 노드의 분할은 leaf 노드의 분할과는 약간 다르다. Figure 4는 figure 3에 "Lamport" 키 값을 가진 레코드를 삽입한 결과를 보여준다. "Lamport"가 삽입될 리프 노드는 이미 "Gold", "Katz", "Kim" 항목을 포함하고 있어 분할이 필요하다. 분할 결과 생성된 오른쪽 노드에는 "Kim"과 "Lamport"가 들어간다. 이 경우 <code>(Kim, n1)</code> 항목이 부모 노드에 추가되어야 하며, 여기서 n1은 새 노드를 가리키는 포인터이다. 그러나 부모 노드에 공간이 없기 때문에, 부모 노드도 분할해야 한다. 이때 부모 노드는 임시로 확장되어 항목을 추가한 후, 과도한 항목 수를 분할하여 처리한다.<br>		non-leaf 노드의 분할은 leaf 노드의 분할과는 약간 다르다. Figure 4는 figure 3에 "Lamport" 키 값을 가진 레코드를 삽입한 결과를 보여준다. "Lamport"가 삽입될 리프 노드는 이미 "Gold", "Katz", "Kim" 항목을 포함하고 있어 분할이 필요하다. 분할 결과 생성된 오른쪽 노드에는 "Kim"과 "Lamport"가 들어간다. 이 경우 <code>(Kim, n1)</code> 항목이 부모 노드에 추가되어야 하며, 여기서 n1은 새 노드를 가리키는 포인터이다. 그러나 부모 노드에 공간이 없기 때문에, 부모 노드도 분할해야 한다. 이때 부모 노드는 임시로 확장되어 항목을 추가한 후, 과도한 항목 수를 분할하여 처리한다.<br>
	non-leaf 노드를 분할할 때는, 자식 노드를 지시하는 포인터들을 기존의 노드와 새로 생성된 노드 사이에 나누어 배치한다. Figure 4에서는 기존의 노드가 첫 세개의 포인터를 유지하고, 새 노드는 나머지 두 개의 포인터를 가진다. 하지만 기존 노드에서의 검색키값은 이와 조금 다르게 처리된다. 새 노드로 이동된 포인터들 사이에 있는 검색 키 값들("Kim")은 해당 포인터들과 함께 이동한다. 반면, 기존 노드에 그대로 남아 있는 포인터들 사이에 있는 키 값들<code>("Califieri", "Einstein")</code>은 그대로 남는다. 이때, 기존 노드에 남는 포인터들과 새 노드로 이동하는 포인터들 사이에 위치한 검색 키 값("Gold")은 별도로 처리된다. 이는 어느 노드에도 삽입되지 않고, (Gold, n2) 항목으로 상위 부모 노드에 삽입되며, 여기서 n2는 새로 생성된 노드를 가리키는 포인터이다. 이 예제에서 부모 노드는 루트이고, 새 항목을 위한 공간이 충분했다. 아래는 B<sup>+</sup>트리에 대한 일반적인 삽입 기법이다.		non-leaf 노드를 분할할 때는, 자식 노드를 지시하는 포인터들을 기존의 노드와 새로 생성된 노드 사이에 나누어 배치한다. Figure 4에서는 기존의 노드가 첫 세개의 포인터를 유지하고, 새 노드는 나머지 두 개의 포인터를 가진다. 하지만 기존 노드에서의 검색키값은 이와 조금 다르게 처리된다. 새 노드로 이동된 포인터들 사이에 있는 검색 키 값들("Kim")은 해당 포인터들과 함께 이동한다. 반면, 기존 노드에 그대로 남아 있는 포인터들 사이에 있는 키 값들<code>("Califieri", "Einstein")</code>은 그대로 남는다. 이때, 기존 노드에 남는 포인터들과 새 노드로 이동하는 포인터들 사이에 위치한 검색 키 값("Gold")은 별도로 처리된다. 이는 어느 노드에도 삽입되지 않고, (Gold, n2) 항목으로 상위 부모 노드에 삽입되며, 여기서 n2는 새로 생성된 노드를 가리키는 포인터이다. 이 예제에서 부모 노드는 루트이고, 새 항목을 위한 공간이 충분했다. 아래는 B<sup>+</sup>트리에 대한 일반적인 삽입 기법이다.

Pinkgo: /* Insertion */

2025-06-11T03:13:57Z

Insertion

← 이전 판		2025년 6월 11일 (수) 03:13 판
13번째 줄:		13번째 줄:
	[[파일:Split of leaf node on insertion of “Adams”.png\|섬네일\|Figure 2. Split of leaf node on insertion of “Adams”]]		[[파일:Split of leaf node on insertion of “Adams”.png\|섬네일\|Figure 2. Split of leaf node on insertion of “Adams”]]
	[[파일:Insertion of “Adams” into the B+-tree of Figure 1.png\|섬네일\|Figure 3. Insertion of “Adams” into the B+-tree of Figure 1\|300x300px]]		[[파일:Insertion of “Adams” into the B+-tree of Figure 1.png\|섬네일\|Figure 3. Insertion of “Adams” into the B+-tree of Figure 1\|300x300px]]
	일반적으로는 n개의 검색키 값(리프 노드의 n−1개 키 값 + 삽입하려는 값)에서, 처음 <code>⌈n/2⌉</code> 개를 기존 노드에 유지하고 나머지를 새로 생성된 노드에 넣는다. 이때 leaf 노드를 분할한 이후에는 새 leaf 노드를 B<sup>+</sup>-트리 구조에 삽입해야 한다. 이 예제에서는 새 노드의 최소 검색키 값이 "Califieri"이므로, <code>K = "Califieri"</code>이고, <code>P -> ("Califieri"로 시작하는 노드)</code>인 항목의 쌍을 부모 노드에 삽입해야 한다. Figure 3는 삽입 후의 B<sup>+</sup>트리를 보여준다. 이 경우 부모 노드에는 새 항목을 저장할 공간이 있었으므로, 추가적인 분할없이 가능했다. 만약 공간이 없었다면 부모 노드도 분할해야 하며, 이 경우, 부모의 부모에도 항목을 삽입해야 한다. 최악의 경우에는 root까지의 모든 노드가 분할되어야 할 수 있으며, root 노드가 분할되어야 할 수 있으며, 루트가 분할되면 전체 트리의 높이(height)는 1 증가한다.		일반적으로는 n개의 검색키 값(리프 노드의 n−1개 키 값 + 삽입하려는 값)에서, 처음 <code>⌈n/2⌉</code> 개를 기존 노드에 유지하고 나머지를 새로 생성된 노드에 넣는다. 이때 leaf 노드를 분할한 이후에는 새 leaf 노드를 B<sup>+</sup>-트리 구조에 삽입해야 한다. 이 예제에서는 새롭게 생성된 노드의 최소 검색키 값이 "Califieri"이므로, <code>K = "Califieri"</code>이고, <code>P -> ("Califieri"로 시작하는 노드)</code>인 항목의 쌍을 부모 노드에 삽입해야 한다. Figure 3는 삽입 후의 B<sup>+</sup>트리를 보여준다. 이 경우 부모 노드에는 새 항목을 저장할 공간이 있었으므로, 추가적인 분할없이 가능했다. 만약 공간이 없었다면 부모 노드도 분할해야 하며, 이 경우, 부모의 부모에도 항목을 삽입해야 한다. 최악의 경우에는 root까지의 모든 노드가 분할되어야 할 수 있으며, root 노드가 분할되어야 할 수 있으며, 루트가 분할되면 전체 트리의 높이(height)는 1 증가한다.
	[[파일:Insertion of “Lamport” into the B+-tree of Figure 3.png\|섬네일\|Figure 4. Insertion of “Lamport” into the B+-tree of Figure 3\|300x300px]]		[[파일:Insertion of “Lamport” into the B+-tree of Figure 3.png\|섬네일\|Figure 4. Insertion of “Lamport” into the B+-tree of Figure 3\|300x300px]]
	non-leaf 노드의 분할은 leaf 노드의 분할과는 약간 다르다. Figure 4는 figure 3에 "Lamport" 키 값을 가진 레코드를 삽입한 결과를 보여준다. "Lamport"가 삽입될 리프 노드는 이미 "Gold", "Katz", "Kim" 항목을 포함하고 있어 분할이 필요하다. 분할 결과 생성된 오른쪽 노드에는 "Kim"과 "Lamport"가 들어간다. 이 경우 <code>(Kim, n1)</code> 항목이 부모 노드에 추가되어야 하며, 여기서 n1은 새 노드를 가리키는 포인터이다. 그러나 부모 노드에 공간이 없기 때문에, 부모 노드도 분할해야 한다. 이때 부모 노드는 임시로 확장되어 항목을 추가한 후, 과도한 항목 수를 분할하여 처리한다.<br>		non-leaf 노드의 분할은 leaf 노드의 분할과는 약간 다르다. Figure 4는 figure 3에 "Lamport" 키 값을 가진 레코드를 삽입한 결과를 보여준다. "Lamport"가 삽입될 리프 노드는 이미 "Gold", "Katz", "Kim" 항목을 포함하고 있어 분할이 필요하다. 분할 결과 생성된 오른쪽 노드에는 "Kim"과 "Lamport"가 들어간다. 이 경우 <code>(Kim, n1)</code> 항목이 부모 노드에 추가되어야 하며, 여기서 n1은 새 노드를 가리키는 포인터이다. 그러나 부모 노드에 공간이 없기 때문에, 부모 노드도 분할해야 한다. 이때 부모 노드는 임시로 확장되어 항목을 추가한 후, 과도한 항목 수를 분할하여 처리한다.<br>

Pinkgo: /* Deletion */

2025-06-05T14:00:05Z

Deletion

← 이전 판		2025년 6월 5일 (목) 14:00 판
47번째 줄:		47번째 줄:

	==Deletion==		==Deletion==
	노드 내 항목의 삭제는 해당 노드 안에 너무 적은 수의 포인터가 남는 상황을 야기할 수 있다. 우선, figure 3의 B<sup>+</sup>-트리에서 “Srinivasan”을 삭제하는 상황을 고려하자. 이 결과는 figure 5에 나타나 있다. 이를 위해서는 먼저 [[find()]] 알고리즘을 바탕으로 “Srinivasan” 항목을 찾는다. “Srinivasan” 항목을 리프 노드에서 삭제하면, 해당 노드는 “Wu” 항목 하나만 남는다. 이때 해당 figure 에서 n = 4이고, 1 < ⌈(n−1)/~~2⌉이므로~~, 최소 절반은 차 있어야 한다는 조건을 만족시키기 위해 해당 노드를 같은 레벨에서의 노드(형제 노드)와 병합하거나 항목을 재분배 해야 한다.		노드 내 항목의 삭제는 해당 노드 안에 너무 적은 수의 포인터가 남는 상황을 야기할 수 있다. 우선, figure 3의 B<sup>+</sup>-트리에서 “Srinivasan”을 삭제하는 상황을 고려하자. 이 결과는 figure 5에 나타나 있다. 이를 위해서는 먼저 [[Indexing#Queries on B+-Trees\|find()]] 알고리즘을 바탕으로 “Srinivasan” 항목을 찾는다. “Srinivasan” 항목을 리프 노드에서 삭제하면, 해당 노드는 “Wu” 항목 하나만 남는다. 이때 해당 figure 에서 n = 4이고, <code>1 < ⌈(n−1)/2⌉</code>이므로, 최소 절반은 차 있어야 한다는 조건을 만족시키기 위해 해당 노드를 같은 레벨에서의 노드(형제 노드)와 병합하거나 항목을 재분배 해야 한다.

	이 에제에서는 삭제당한 노드의 항목들을 왼쪽에 존재하는 형제 노드로 옮기고, 비어있는 오른쪽의 형제 노드를 삭제함으로서 이루어질 수 있다. 이때 노드가 삭제되면, 해당 노드를 가리키고 있던 부모 노드의 항목들도 삭제해야 한다. 예제에서 삭제할 항목은 (Srinivasan, n3)이고, n3은 “Srinivasan”이 들어 있는 leaf를 가리킨다. 해당 항목을 삭제하면, 부모 노드는 “Srinivasan”과 두 개의 포인터를 가졌던 상태에서 이제 하나의 포인터만 남게 되며, 검색 키 값은 없어진다. n = 4이므로 1 < ⌈n/2⌉가 되어 부모 노드 역시 부족해진다. 이 경우 부모의 형제 노드를 살펴야 한다. Figure에서 형제 노드는 “Califieri”, “Einstein”, “Gold”를 포함하는 non-leaf 노드이다. 이때 이 노드와 병합하고 싶지만, 이 경우 포인터가 총 5개가 되어 최대값인 4를 초과하므로 병합할 수 없다. 따라서 포인터들을 재분배하여 두 노드가 최소 ⌈n/2⌉ = 2개의 자식 포인터를 갖도록 한다.		이 에제에서는 삭제당한 노드의 항목들을 왼쪽에 존재하는 형제 노드로 옮기고, 비어있는 오른쪽의 형제 노드를 삭제함으로서 이루어질 수 있다. 이때 노드가 삭제되면, 해당 노드를 가리키고 있던 부모 노드의 항목들도 삭제해야 한다. 예제에서 삭제할 항목은 (Srinivasan, n3)이고, n3은 “Srinivasan”이 들어 있는 leaf를 가리킨다. 해당 항목을 삭제하면, 부모 노드는 “Srinivasan”과 두 개의 포인터를 가졌던 상태에서 이제 하나의 포인터만 남게 되며, 검색 키 값은 없어진다. n = 4이므로 1 < ⌈n/2⌉가 되어 부모 노드 역시 부족해진다. 이 경우 부모의 형제 노드를 살펴야 한다. Figure에서 형제 노드는 “Califieri”, “Einstein”, “Gold”를 포함하는 non-leaf 노드이다. 이때 이 노드와 병합하고 싶지만, 이 경우 포인터가 총 5개가 되어 최대값인 4를 초과하므로 병합할 수 없다. 따라서 포인터들을 재분배하여 두 노드가 최소 ⌈n/2⌉ = 2개의 자식 포인터를 갖도록 한다.

	재분배를 위해 왼쪽 형재 노드의 가장 오른쪽 포인터("Gold"를 가리키는 포인터)를 ~~오른쪽의 부족한~~ 노드로 옮긴다. 이를 통해 ~~오른쪽의 부족한~~ 노드는 왼		재분배를 위해 왼쪽 형제 노드의 가장 오른쪽 포인터("Gold"를 가리키는 포인터)를 오른쪽에 있는 노드로 옮긴다. 이를 통해 오른쪽 노드는 원래 포인터를 부족하게 가지고 있었지만, 비로소

	==각주==		==각주==

← 이전 판		2025년 6월 11일 (수) 03:28 판
12번째 줄:		12번째 줄:
	노드를 분할해야 하는 삽입 예제를 고려하기 위해, name 속성의 값이 "Adams"인 레코드를 instructor 릴레이션에 삽입한다고 하자. 그러기 위해서는 Figure 1의 B<sup>+</sup>트리에 "Adams" 항목을 삽입해야 한다. 이때 [[Indexing#Queries on B+-Trees\|find() 함수]]에서의 알고리즘에서의 동일한 방식을 사용하면 Adams"는 "Brandt", "Califieri", "Crick"을 포함하는 leaf 노드에 들어가야 한다. 하지만 이 leaf 노드에는 "Adams"를 삽입할 공간이 없으므로, 해당 leaf 노드는 두개의 노드로 분할되어야 한다. Figure 2는 "Adams" 삽입으로 인해 leaf 노드가 분할된 모습을 보여준다. "Adams"와 "Brandt"는 하나의 리프에, "Califieri"와 "Crick"은 다른 리프에 위치한다.		노드를 분할해야 하는 삽입 예제를 고려하기 위해, name 속성의 값이 "Adams"인 레코드를 instructor 릴레이션에 삽입한다고 하자. 그러기 위해서는 Figure 1의 B<sup>+</sup>트리에 "Adams" 항목을 삽입해야 한다. 이때 [[Indexing#Queries on B+-Trees\|find() 함수]]에서의 알고리즘에서의 동일한 방식을 사용하면 Adams"는 "Brandt", "Califieri", "Crick"을 포함하는 leaf 노드에 들어가야 한다. 하지만 이 leaf 노드에는 "Adams"를 삽입할 공간이 없으므로, 해당 leaf 노드는 두개의 노드로 분할되어야 한다. Figure 2는 "Adams" 삽입으로 인해 leaf 노드가 분할된 모습을 보여준다. "Adams"와 "Brandt"는 하나의 리프에, "Califieri"와 "Crick"은 다른 리프에 위치한다.
	[[파일:Split of leaf node on insertion of “Adams”.png\|섬네일\|Figure 2. Split of leaf node on insertion of “Adams”\|400x400픽셀]]		[[파일:Split of leaf node on insertion of “Adams”.png\|섬네일\|Figure 2. Split of leaf node on insertion of “Adams”\|400x400픽셀]]
	[[파일:Insertion of “Adams” into the B+-tree of Figure 1.png\|섬네일\|Figure 3. Insertion of “Adams” into the B+-tree of Figure 1\|~~400x400px~~]]		[[파일:Insertion of “Adams” into the B+-tree of Figure 1.png\|섬네일\|Figure 3. Insertion of “Adams” into the B+-tree of Figure 1\|500x500px\|가운데]]
			[[파일:Insertion of “Lamport” into the B+-tree of Figure 3.png\|섬네일\|Figure 4. Insertion of “Lamport” into the B+-tree of Figure 3\|500x500px\|가운데]]
	일반적으로는 n개의 검색키 값(리프 노드의 n−1개 키 값 + 삽입하려는 값)에서, 처음 <code>⌈n/2⌉</code> 개를 기존 노드에 유지하고 나머지를 새로 생성된 노드에 넣는다. 이때 leaf 노드를 분할한 이후에는 새 leaf 노드를 B<sup>+</sup>-트리 구조에 삽입해야 한다. 이 예제에서는 새롭게 생성된 노드의 최소 검색키 값이 "Califieri"이므로, <code>K = "Califieri"</code>이고, <code>P -> ("Califieri"로 시작하는 노드)</code>인 항목의 쌍을 부모 노드에 삽입해야 한다. Figure 3는 삽입 후의 B<sup>+</sup>트리를 보여준다. 이 경우 부모 노드에는 새 항목을 저장할 공간이 있었으므로, 추가적인 분할없이 가능했다. 만약 공간이 없었다면 부모 노드도 분할해야 하며, 이 경우, 부모의 부모에도 항목을 삽입해야 한다. 최악의 경우에는 root까지의 모든 노드가 분할되어야 할 수 있으며, root 노드가 분할되어야 할 수 있으며, 루트가 분할되면 전체 트리의 높이(height)는 1 증가한다.		일반적으로는 n개의 검색키 값(리프 노드의 n−1개 키 값 + 삽입하려는 값)에서, 처음 <code>⌈n/2⌉</code> 개를 기존 노드에 유지하고 나머지를 새로 생성된 노드에 넣는다. 이때 leaf 노드를 분할한 이후에는 새 leaf 노드를 B<sup>+</sup>-트리 구조에 삽입해야 한다. 이 예제에서는 새롭게 생성된 노드의 최소 검색키 값이 "Califieri"이므로, <code>K = "Califieri"</code>이고, <code>P -> ("Califieri"로 시작하는 노드)</code>인 항목의 쌍을 부모 노드에 삽입해야 한다. Figure 3는 삽입 후의 B<sup>+</sup>트리를 보여준다. 이 경우 부모 노드에는 새 항목을 저장할 공간이 있었으므로, 추가적인 분할없이 가능했다. 만약 공간이 없었다면 부모 노드도 분할해야 하며, 이 경우, 부모의 부모에도 항목을 삽입해야 한다. 최악의 경우에는 root까지의 모든 노드가 분할되어야 할 수 있으며, root 노드가 분할되어야 할 수 있으며, 루트가 분할되면 전체 트리의 높이(height)는 1 증가한다.
	~~[[파일:Insertion of “Lamport” into the B+-tree of Figure 3.png\|섬네일\|Figure 4. Insertion of “Lamport” into the B+-tree of Figure 3\|400x400px]]~~
	non-leaf 노드의 분할은 leaf 노드의 분할과는 약간 다르다. Figure 4는 figure 3에 "Lamport" 키 값을 가진 레코드를 삽입한 결과를 보여준다. "Lamport"가 삽입될 리프 노드는 이미 "Gold", "Katz", "Kim" 항목을 포함하고 있어 분할이 필요하다. 분할 결과 생성된 오른쪽 노드에는 "Kim"과 "Lamport"가 들어간다. 이 경우 <code>(Kim, n1)</code> 항목이 부모 노드에 추가되어야 하며, 여기서 n1은 새 노드를 가리키는 포인터이다. 그러나 부모 노드에 공간이 없기 때문에, 부모 노드도 분할해야 한다. 이때 부모 노드는 임시로 확장되어 항목을 추가한 후, 과도한 항목 수를 분할하여 처리한다.<br>		non-leaf 노드의 분할은 leaf 노드의 분할과는 약간 다르다. Figure 4는 figure 3에 "Lamport" 키 값을 가진 레코드를 삽입한 결과를 보여준다. "Lamport"가 삽입될 리프 노드는 이미 "Gold", "Katz", "Kim" 항목을 포함하고 있어 분할이 필요하다. 분할 결과 생성된 오른쪽 노드에는 "Kim"과 "Lamport"가 들어간다. 이 경우 <code>(Kim, n1)</code> 항목이 부모 노드에 추가되어야 하며, 여기서 n1은 새 노드를 가리키는 포인터이다. 그러나 부모 노드에 공간이 없기 때문에, 부모 노드도 분할해야 한다. 이때 부모 노드는 임시로 확장되어 항목을 추가한 후, 과도한 항목 수를 분할하여 처리한다.<br>
	non-leaf 노드를 분할할 때는, 자식 노드를 지시하는 포인터들을 기존의 노드와 새로 생성된 노드 사이에 나누어 배치한다. Figure 4에서는 기존의 노드가 첫 세개의 포인터를 유지하고, 새 노드는 나머지 두 개의 포인터를 가진다. 하지만 기존 노드에서의 검색키값은 이와 조금 다르게 처리된다. 새 노드로 이동된 포인터들 사이에 있는 검색 키 값들("Kim")은 해당 포인터들과 함께 이동한다. 반면, 기존 노드에 그대로 남아 있는 포인터들 사이에 있는 키 값들<code>("Califieri", "Einstein")</code>은 그대로 남는다. 이때, 기존 노드에 남는 포인터들과 새 노드로 이동하는 포인터들 사이에 위치한 검색 키 값("Gold")은 별도로 처리된다. 이는 어느 노드에도 삽입되지 않고, (Gold, n2) 항목으로 상위 부모 노드에 삽입되며, 여기서 n2는 새로 생성된 노드를 가리키는 포인터이다. 이 예제에서 부모 노드는 루트이고, 새 항목을 위한 공간이 충분했다. 아래는 B<sup>+</sup>트리에 대한 일반적인 삽입 기법이다.		non-leaf 노드를 분할할 때는, 자식 노드를 지시하는 포인터들을 기존의 노드와 새로 생성된 노드 사이에 나누어 배치한다. Figure 4에서는 기존의 노드가 첫 세개의 포인터를 유지하고, 새 노드는 나머지 두 개의 포인터를 가진다. 하지만 기존 노드에서의 검색키값은 이와 조금 다르게 처리된다. 새 노드로 이동된 포인터들 사이에 있는 검색 키 값들("Kim")은 해당 포인터들과 함께 이동한다. 반면, 기존 노드에 그대로 남아 있는 포인터들 사이에 있는 키 값들<code>("Califieri", "Einstein")</code>은 그대로 남는다. 이때, 기존 노드에 남는 포인터들과 새 노드로 이동하는 포인터들 사이에 위치한 검색 키 값("Gold")은 별도로 처리된다. 이는 어느 노드에도 삽입되지 않고, (Gold, n2) 항목으로 상위 부모 노드에 삽입되며, 여기서 n2는 새로 생성된 노드를 가리키는 포인터이다. 이 예제에서 부모 노드는 루트이고, 새 항목을 위한 공간이 충분했다. 아래는 B<sup>+</sup>트리에 대한 일반적인 삽입 기법이다.
49번째 줄:		50번째 줄:
	노드 내 항목의 삭제는 해당 노드 안에 너무 적은 수의 포인터가 남는 상황을 야기할 수 있다. 우선, figure 3의 B<sup>+</sup>-트리에서 “Srinivasan”을 삭제하는 상황을 고려하자. 이 결과는 figure 5에 나타나 있다. 이를 위해서는 먼저 [[Indexing#Queries on B+-Trees\|find()]] 알고리즘을 바탕으로 “Srinivasan” 항목을 찾는다. “Srinivasan” 항목을 리프 노드에서 삭제하면, 해당 노드는 “Wu” 항목 하나만 남는다. 이때 해당 figure 에서 n = 4이고, <code>1 < ⌈(n−1)/2⌉</code>이므로, 최소 절반은 차 있어야 한다는 조건을 만족시키기 위해 해당 노드를 같은 레벨에서의 노드(형제 노드)와 병합하거나 항목을 재분배 해야 한다.		노드 내 항목의 삭제는 해당 노드 안에 너무 적은 수의 포인터가 남는 상황을 야기할 수 있다. 우선, figure 3의 B<sup>+</sup>-트리에서 “Srinivasan”을 삭제하는 상황을 고려하자. 이 결과는 figure 5에 나타나 있다. 이를 위해서는 먼저 [[Indexing#Queries on B+-Trees\|find()]] 알고리즘을 바탕으로 “Srinivasan” 항목을 찾는다. “Srinivasan” 항목을 리프 노드에서 삭제하면, 해당 노드는 “Wu” 항목 하나만 남는다. 이때 해당 figure 에서 n = 4이고, <code>1 < ⌈(n−1)/2⌉</code>이므로, 최소 절반은 차 있어야 한다는 조건을 만족시키기 위해 해당 노드를 같은 레벨에서의 노드(형제 노드)와 병합하거나 항목을 재분배 해야 한다.

	이 에제에서는 삭제당한 노드의 항목들을 왼쪽에 존재하는 형제 노드로 옮기고, 비어있는 오른쪽의 형제 노드를 ~~삭제함으로서 이루어질~~ 수 있다. 이때 노드가 삭제되면, 해당 노드를 가리키고 있던 부모 노드의 항목들도 삭제해야 한다. 예제에서 삭제할 항목은 (Srinivasan, n3)이고, n3은 “Srinivasan”이 들어 있는 leaf를 가리킨다. 해당 항목을 삭제하면, 부모 노드는 “Srinivasan”과 두 개의 포인터를 가졌던 상태에서 이제 하나의 포인터만 남게 되며, ~~검색 키~~ 값은 없어진다. n = 4이므로 1 < ⌈n/2⌉가 되어 부모 노드 역시 부족해진다. 이 경우 부모의 형제 노드를 살펴야 한다. Figure에서 형제 노드는 “Califieri”, “Einstein”, “Gold”를 포함하는 non-leaf 노드이다. 이때 이 노드와 병합하고 싶지만, 이 경우 포인터가 총 5개가 되어 최대값인 4를 초과하므로 병합할 수 없다. 따라서 포인터들을 재분배하여 두 노드가 최소 ⌈n/2⌉ = 2개의 자식 포인터를 갖도록 한다.		이 에제에서는 삭제당한 노드의 항목들을 왼쪽에 존재하는 형제 노드로 옮기고, 비어있는 오른쪽의 형제 노드를 삭제할 수 있다. 이때 노드가 삭제되면, 해당 노드를 가리키고 있던 부모 노드의 항목들도 삭제해야 한다. 예제에서 삭제할 항목은 (Srinivasan, n3)이고, n3은 “Srinivasan”이 들어 있는 leaf를 가리킨다. 해당 항목을 삭제하면, 부모 노드는 “Srinivasan”과 두 개의 포인터를 가졌던 상태에서 이제 하나의 포인터만 남게 되며, 검색키 값은 없어진다. n = 4이므로 1 < ⌈n/2⌉가 되어 부모 노드 역시 부족해진다. 이 경우 부모의 형제 노드를 살펴야 한다. Figure에서 형제 노드는 “Califieri”, “Einstein”, “Gold”를 포함하는 non-leaf 노드이다. 이때 이 노드와 병합하고 싶지만, 이 경우 포인터가 총 5개가 되어 최대값인 4를 초과하므로 병합할 수 없다. 따라서 포인터들을 재분배하여 두 노드가 최소 ⌈n/2⌉ = 2개의 자식 포인터를 갖도록 한다.

	재분배를 위해 왼쪽 형제 노드의 가장 오른쪽 포인터("Gold"를 가리키는 포인터)를 오른쪽에 있는 노드로 옮긴다. 이를 통해 오른쪽 노드는 원래 포인터를 부족하게 가지고 있었지만, 비로소		재분배를 위해 왼쪽 형제 노드의 가장 오른쪽 포인터("Gold"를 가리키는 포인터)를 오른쪽에 있는 노드로 옮긴다. 이를 통해 오른쪽 형제 노드는 원래 포인터를 부족하게 가지고 있었지만, 비로소 2개의 포인터를 가짐으로서 전제 조건을 만족한다. 하지만 이 두개의 포인터는 어떤 검색키값에 의해서 구분되지 않으므로, 이 두 포인터가 가리키는 노드를 구분하기 위해서 해당 노드의 부모 노드에 있던 "Mozart"를 부족한 노드로 옮기고, "Gold" 노드를 부모 노드로 올린다.

	==각주==		==각주==