알고리즘...72

B 트리 삽입 오버플로우 처리 진행

삽입 가능한 형제 노드가 없는 경우 기존 노드의 중간 값을 기준으로 두 개의 노드로 분리하고 중간 값을 부모로 삽입한 뒤 좌, 우 자식 노드로 기존 중간 값을 저장해 줘야 한다.

 

또, 삽입된 부모 노드에서 형제 키 값이 가리키는 노드를 적절하게 수정해 줘야 한다.

 

이후 부모 노드의 크기가 오버된 경우 오버플로우 처리를 부모 노드에 대해 반복한다.

 

※ 만약 처리한 노드가 루트 노드면 중간 키 값을 새로운 노드로 추가하고 새 노드를 루트로 변경한다.

 

BTreeNode::GetMiddleKey

/// <summary>
/// 노드의 키 중 중간 값을 가진 키를 떼어내 반환한다.
/// </summary>
/// <returns>중간 키</returns>
BTreeNodeKey* BTreeNode::GetMiddleKey()
{
	size_t midIdx = TotalKeyCount / 2;

	BTreeNodeKey* key{ nullptr };
	if (keyRoot != nullptr)
	{
		key = keyRoot;
		while (key->next != nullptr && midIdx > 0)
		{
			key = key->next;
			midIdx--;
		}

		BTreeNodeKey* prev{ key->prev };
		BTreeNodeKey* next{ key->next };
		if (prev != nullptr)
		{
			prev->next = next;
			key->prev = nullptr;
		}
		if (next != nullptr)
		{
			next->prev = prev;
			key->next = nullptr;
		}
	}
	size--;
	return key;
}