그리고 이어 다음과 같이 두 번째 레코드가 삽입되었다고 합시다.

▲ 그림 10-5 split

그림 10-5를 보면 첫 번째 레코드가 삽입되면 B 트리가 생성되면서 키 1을 가진 루트 노드가 만들어집니다. 루트 노드이자 리프 노드입니다. 다음으로 두 번째 레코드가 삽입되면 키 2가 루트 노드에 추가됩니다. 2-3 트리는 키를 최대 두 개 가질 수 있습니다.

세 번째 키가 삽입된다면 어떻게 될까요? 다음 그림과 같이 키 3을 노드 끝에 삽입하면 노드에서의 최대 키 개수를 넘게 되는군요. 이때는 다음 그림과 같이 split 연산이 일어납니다.

▲ 그림 10-6 insert 1

그림 10- 6을 보면 먼저 키 3을 노드 끝에 삽입합니다. 최대 키 개수를 넘기 때문에 이를 분리시켜야 합니다. 가운데 키 2를 새로운 노드에 삽입하여 부모로 올립니다. 키 1이 있는 노드는 키 2가 있는 노드의 왼쪽 서브 트리로 만들고, 키 3이 있는 노드는 키 2가 있는 노드의 오른쪽 서브 트리로 만듭니다. 최종적으로 트리 높이가 하나 더 높아졌군요. 이렇게 하면 B 트리가 가져야 할 모든 특징을 가지게 됩니다.