B-Tree

: B트리는 Binary Tree에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리이다. 정렬된 순서를 보장하고, 멀티레벨 인덱싱을 통해 빠른 검색을 할 수 있기 때문에 DB에서 사용하는 자료구조이다.

최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 한다.

• 노드는 최대 M개부터 M/2개 까지의 자식을 가질 수 있다.
• 노드에는 최대 M - 1 개 부터 [M/2] - 1 개의 키가 포함될 수 있다.
• 노드의 키가 x개라면 자식의 수는 x + 1 개이다
  • 포인터가 앞과 뒤에 추가로 붙기 때문
• 최소차수는 자식 수의 하한 값이며, 최소차수가 t라면 M = 2t - 1을 만족한다 (최소차수 t가 2라면 3차 B트리이며, Key의 하한은 1개이다)

3차 B 트리의 예

• 각 key의 앞 쪽 포인터는, 해당 key 보다 작은 key를 가르키는 포인터가 존재한다.
• 각 key의 뒤 쪽 포인터는, 해당 key 보다 큰 key를 가르키는 포인터가 존재한다.
• key들은 노드 안에서 항상 정렬된 값을 가진다.

Key 검색 과정

검색하고자 하는 값을 k 라고 가정한다면,

1. 루트 노드에서 시작하여 key들을 순회하며 k값의 범위를 찾는다
   • k와 같은 key를 찾았다면 검색을 종료한다.
   • 검색하는 key들의 대소관계를 비교하여 k값이 해당하는 자식으로 내려간다
2. 리프노드에 도달할 때 까지 1번을 반복한다, 만약 리프노드에 도달하여 k와 같은 key가 없을 경우, 검색을 실패한다.