B 트리에서 탐색은 BST와 같습니다. 찾고자 하는 키가 키 K₁보다 크고 키 K₂보다 작으면 K₁과 K₂ 사이에 있는 서브 트리로 내려가 다시 탐색을 시작합니다. 그렇게 계속 내려가다 보면 찾고자 하는 키를 찾을 수 있을 것입니다. 그래서 이 절에서는 B 트리에서 삽입과 삭제에 집중하려고 합니다. 먼저 insert 연산을 알아보겠습니다.

예제로 쓸 2-3 트리를 다시 한 번 정리하고 넘어가겠습니다. 다음 그림은 2-3 트리입니다.

▲ 그림 10-4 2-3 트리

그림 10-4에서 한 노드에 들어갈 수 있는 최대 키 개수는 2입니다. 모든 리프 노드가 같은 레벨에 있다는 점도 주목하기 바랍니다. 그림에 있는 노드의 키는 이전 절에서 만든 example 테이블의 ID로 생각하면 됩니다. 여기서는 실제 레코드를 노드에 저장하는 대신 키 옆에 그 키가 가리키는 레코드에 대한 참조를 저장해 둡니다. 이렇게 하면 레코드 크기가 굉장히 크더라도 실제 노드에서 필요한 메모리는 참조의 크기일 뿐입니다. 테이블에 레코드가 아무것도 없었다고 합시다. 이 상태에서 첫 번째 레코드가 ID 1을 가지고 삽입됩니다.