여기서 B-트리에 삽입을 수행하는 방법을 살펴보겠습니다. 아래와 같은 B-Tree가 있다고 가정합니다. -
B-트리의 예 -
요소를 삽입하는 아이디어는 BST와 매우 유사하지만 몇 가지 규칙을 따라야 합니다. 각 노드에는 m개의 자식과 m-1개의 요소가 있습니다. 하나의 노드에 요소를 삽입하면 두 가지 상황이 발생합니다. 노드에 m-1보다 작은 요소가 있으면 새 요소가 노드에 직접 삽입됩니다. m-1개의 요소가 있는 경우 모든 요소와 삽입될 요소를 취하여 그 중 중간값을 취하고 동일한 기준을 수행하여 중간값을 해당 노드의 루트로 보낸 다음 두 개를 만듭니다. 노드의 왼쪽 절반과 오른쪽 절반에서 별도의 목록
트리에 79를 삽입한다고 가정합니다. 처음에는 루트로 검사합니다. 이 값은 56보다 큽니다. 그런 다음 가장 오른쪽의 하위 트리로 이동합니다. 이제 81보다 작으므로 왼쪽 하위 트리로 이동합니다. 그런 다음 루트에 삽입됩니다. 이제 세 가지 요소[66, 78, 79]가 있습니다. 중앙값은 78이므로 78이 올라가고 루트 노드는 [79, 81]이 되며 노드의 요소는 두 개의 노드로 분할됩니다. 하나는 66, 다른 하나는 79입니다.
79를 삽입한 후의 B-Tree.
알고리즘
BTreeInsert(루트, 키)-
입력 − 트리의 루트와 삽입할 키 키가 목록에 없다고 가정합니다.
x := Read root if x is full, then y := new node z := new node Locate the middle object oi, stored in x, move the objects to the left of oi in to node y Move the object to the right of oi into node z. If x is an index node, then move the child pointers accordingly x->child[1] := address of y x->child[2] := address of z end if