B-Tree

개념

B 트리는 균형잡힌 트리이며 많은 수의 키를 가진 노드로 구성되어 다방향 탐색이 가능한 트리이다. balanced tree이자 multi-way search tree이다. 루트를 제외한 한 노드의 키수가 많은 만큼 자식 노드의 수도 많이 가질 수 있다. 그렇기 때문에 B-트리의 높이는 avl tree에 비해 상대적으로 낮다. 한 노드에 많은 키가 들어간다면 상대적으로 많은 데이터가 있어도 상대적으로 적은 노드의 수가 만들어진다는 것을 의미하고 데이터에 빠른 접근이 가능해진다는 것을 의미한다. B-트리는 많은 데이터베이스 시스템에서 정보를 저장하기 위해 B-트리나 B-트리 변형을 사용한다.

특징

1. 노드의 특징
   • 내부 노드의 키는 오름차순으로 정렬되어 있는 배열로 저장된다.
     • 내부노드의 키 탐색에 있어서 앞이나 뒤부터 순차적으로 찾거나, 혹은 더 효율적으로 중간값을 찾아 탐색할 수도 있다.
   • 노드의 키값은 자식 노드들의 키 값을 분할하는 범위가 된다.
   • 리프 노드는 자식 노드가 없는 노드이며, 루트에서 리프 노드까지 높이가 트리 전체 높이가 된다.
2. 포인터
   • 트리 내의 모든 노드는 자식 노드를 가리키는 포인터를 가진다. 키의 개수가 n개라면 포인터의 개수는 n+1개이다. 리프 노드는 자식 노드가 없으므로 포인터를 갖지 않는다.
3. 노드의 키의 개수 제한
   • B 트리의 최소 차수 t는 2 이상이다. 그리고 루트를 제외한 모든 노드는 t-1개 이상의 키를 갖는다.
   • 때문에 트리가 비어있지 않다면, 루트 노드는 적어도 한 개의 키(t-1 = 2-1)를 가진다.
   • B 트리에서 가득찬 노드에 키를 삽입 시, 노드 분할 과정에서도 B 트리의 특성(위 특성)을 위반하지 않기 위해서는 한 노드에서는 최대 2t-1개의 키를 가진다.
4. 높이
   • B 트리의 최소 차수를 t라고 할 때, 한 노드에서 최소한 가질 수 있는 자식수는 t개이다. n개의 키를 가진 B 트리의 높이는 log_t n의 높이를 가진다.
   • 자식 노드가 t개 있으면, 그 노드의 자식 노드 또한 t개를 가질 수 있게된다. t값이 크다면, B-트리의 높이는 같은 키의 개수 n개가 있는 완전이진탐색트리의 높이에 비해 상당히 낮은 높이가 될 수 있다. 트리의 낮은 높이는 자식 노드의 개수가 많다는 것이고 이는 빠른 탐색이 가능해진다.

검색

• 루트 노드에서 시작하여 하향식으로 값을 비교해 검색 연산을 수행한다.
• log_t n 의 높이와 한 노드에서 키의 비교 시간 O(t)을 곱한 CPU 시간은 O(t log_tn)이다.
  1. 루트 노드에서 시작해 key들을 순회하면서 비교한다.
  1. k와 같은 key를 찾았다면 키가 속한 노드 y와 인덱스i 쌍을 리턴하며 검색을 종료한다.
  2. 리프 노드에 도달했다면, 더 이상 찾을 수 없으므로 null을 반환하며 검색을 종료한다.
  3. k를 찾을 때 까지 루트에서 자식 노드로 재귀적으로 검색한다.

삽입

• 새로운 키가 삽입될 노드의 위치를 찾는다. 그리고 삽입한다. 삽입 과정에서 해당 노드가 가득 차 있을 경우, 그렇지 않을 경우를 나누어 삽입한다.
• 삽입 연산은 분할, 노드가 가득 차 있지 않을 경우 삽입 연산으로 나눈다. 삽입 연산은 두 가지 경우를 호출한다.
• 분할 연산은 O(1), 삽인 연산은 검색하여 삽입되므로 O(t log_t n) 이다.
  1. 빈 트리라면 루트 노드를 할당하고 k를 삽입한다. 루트 노드가 가득 찼다면 루트가 분할되고 새 노드 s가 자식을 두 개 가지는 루트가 된다.
  2. 그 이후 부터는 k값의 삽입 위치를 검색하고 삽입한다.
  1. 리프 노드가 가득 찼지 않았다면 오름차순으로 k를 삽입한다.
  2. 리프 노드가 아니라면 자식 노드로 내려가 k가 삽입 될 자리를 검색한다.
  3. 리프 노드가 가득 찼다면 노드의 중간키 근처에서 t-1, t개의 키를 가지는 두 노드로 분할한다. 그리고 분할 지점이 되는 중간키는 부모 노드로 병합되거나 새로 생성된다.

삭제

• 삭제 연산 또한 삭제할 키를 탐색하여 삭제하는 연산이므로 걸리는 시간은 O(t log_t n) 이다.
  1. k가 리프에 있으면, k를 노드에서 삭제한다.
  2. k가 리프 노드에 있다면 다음과 같이 삭제한다.
  1. 왼쪽 또는 오른쪽 형제 노드의 키가 최소 키수보다 많다면, k에 부모키로 대체한 후 후, 최소키 개수 이상을 가진 형제 노드가 왼쪽이라면 가장 큰 값을, 오른쪽이라면 가장 작은 값을 부모 키에 넣는다. 그리고 그 키를 삭제한다.
  2. 왼쪽, 오른쪽 형제 노드의 키가 최소 키수이고, 부모 노드의 키가 최소 키수 이상히면, k를 삭제한 후 부모키를 형제 노드와 병합한다. 부모노드의 키의 개수를 줄이고 자식 수도 줄인다.
     1. k가 내부 노드에 있으면 다음과 같이 삭제한다. - 노드나 자식에 키가 최소 키수(t-1)보다 많을 경우, 현재 노드의 선행 또는 후행키를 찾아 k와 자리를 바꾸고 삭제한다. - 노드와 노드의 자식 노드의 키가 최소 키수(t-1)을 가질 경우, 재구조화가 일어난다.
  3. k를 삭제하고 k의 자식을 병합하여 하나의 노드로 만든다.
  4. k의 부모 key를 인접한 k의 형제 노드로 병합시킨다. 그리고 k의 자식을 병합하여 만든 노드를 그의 자식 노드로 정한다.
     1. 새로 구성된 인접한 형제 노드가 최대 키 수를 넘겼다면, 노드 분할 과정을 수행한다.
     2. k의 부모 노드가 최소 키의 개수보다 작아진다면, 그 부모 노드에 대하여 2번 과정을 다시 수행한다.