B-Tree란?

1. B-Tree의 정의

 

  B-Tree란 디스크 등의 보조기억장치에서 데이터를 검색하는데 시간을 최소화하기 위하여 고안된 자료구조이다.

 

2. B-Tree를 사용하는 이유

  특정 Data를 CPU에서 사용하기 위해서는, 원하는 데이터를 디스크에서 찾은 뒤 메인 메모리에 올려야 한다. 원하는 데이터를 찾기 위해서는 특정 데이터를 메인 메모리에 올린 후 원하는 데이터인지 비교함으로써 알 수 있는데, B-Tree를 사용하면 이 비교하는 횟수를 작게할 수 있다.

  임의의 Tree에서, 하나의 노드가 가진 데이터의 크기가 메모리의 크기와 동일하다고 하자. 원하는 데이터를 찾기 위해서는, 하나의 노드에 접근할 때마다 노드가 가진 데이터를 메인 메모리에 올려서 찾는 데이터가 맞는지 확인하는 과정이 필요하다. 트리의 높이가 낮을수록 비교하는 연산이 줄어들게 되며, B-Tree의 높이 h는 다음과 같이 정의된다.(t : 최소 차수, 뒤에서 추가 설명)

3. B-Tree의 정의

  B-Tree를 구현하는 방법은 다양하다. 여기서는 Introductions to Algorithms에서 정의하는 방식을 사용한다. (최대차수는 짝수만 가능하다.) 모든 노드는 KEY와 CHILD이라는 구성요소를 가진다. KEY는 트리 안에서 찾아야 하는 값이며, CHILD은 자식 노드를 가리키는 포인터이다.

 

1. B-Tree의 모든 노드는 아래와 같은 정의를 가진다.

  1) 모든 노드는 포함할 수 있는 KEY의 개수의 범위가 정해져 있다. 범위를 정하는 숫자 t를 최소 차수라고 하며, 최소 차수는 2 이상의 정수이다. 특정 노드의 KEY의 개수가 x개라면, CHILD의 개수는 x+1개이다.

  2) 루트를 제외한 모든 노드는 t-1 개 이상의 KEY를 가진다.(최소 KEY의 개수)

  3) 루트를 제외한 모든 노드는 t개 이상의 CHILD를 가진다.(최소 CHILD의 개수)

  4) 리프는 CHILD을 가지지 않는다.

  5) 모든 노드의 최대 KEY의 개수는 2t-1개이며, 최대 CHILD의 개수는 2t이다.(이 때 가득 차 있다고 표현한다.)

  6) 노드 내의 KEY는 정렬되어 있다.

  7) 특정 키 X의 왼쪽 CHILD에는 X보다 작은 KEY 값들만 존재하며, 오른쪽 CHILD에는 큰 KEY 값들만 존재한다.

이를 만족하는 최소 트리(t=2)는 아래와 같다.

 

다음 포스팅에서 B-Tree를 구현해본다.