B-Tree

• 자가 균형 이진 탐색 트리의 일종으로, 데이터베이스와 파일 시스템에서 널리 사용된다.
• 높은 차수의 균형 트리로, 각 노드가 여러 자식을 가질 수 있다.
• 모든 리프 노드는 동일한 레벨에 존재하기 때문에, B 트리는 O(logN)의 시간 복잡도를 갖는다.

 

특징

1. 각 노드는 최대 M개의 자식을 가질 수 있다. 이러한 트리를 M차 B 트리라고 부른다.
2. 루트 노드를 제외한 모든 노드는 최소 ⌈M/2⌉개의 자식을 가져야 한다.
3. 노드는 데이터와 포인터로 구성되며, 데이터는 오름차순으로 정렬되어 있다. 정렬된 순서에 따라 자녀 노드들의 키 값의 범위가 결정된다.
4. 각 노드는 최대 ⌈M/2⌉ - 1개에서 최대 M - 1개의 키를 가질 수 있다.

 

데이터 삽입

1. 삽입은 항상 리프 노드에서 시작한다.
2. 해당 리프 노드에 여유 공간이 있다면 데이터를 삽입한다.
3. 노드가 가득 찬 경우, 가운데 키를 기준으로 좌우 키들을 분할하고, 가운데 키는 부모 노드로 올린다.
4. 필요에 따라 루트 노드까지 반복적으로 분할 작업을 수행한다.

 

데이터 삭제

1. 내부 노드에 있는 데이터를 삭제하려면 삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.
   1. 선임자나 후임자는 리프 노드에 위치한다.
   2. 따라서 삭제는 항상 리프 노드에서 발생한다.
2. 삭제 후 노드가 최소 키 수를 만족하지 않는 경우:
   1. 키 수가 여유 있는 형제 노드에서 키를 받는다.
      1. 동생(왼쪽 형제)이 여유가 있으면:
         1. 동생의 가장 큰 키를 부모 노드의 나와 동생 사이에 둔다.
         2. 원래 그 자리에 있던 키는 나의 가장 왼쪽에 둔다.
      2. 형(오른쪽 형제)이 여유가 있으면:
         1. 형의 가장 작은 키를 부모 노드의 나와 형 사이에 둔다.
         2. 원래 그 자리에 있던 키는 나의 가장 오른쪽에 둔다.
   2. 1번이 불가능하면 부모 노드에서 키를 받고 형제와 병합된다.
      1. 동생이 있으면:
         1. 동생과 나 사이의 키를 부모로부터 받는다.
         2. 그 키와 나의 키를 차례대로 동생에게 합친다.
         3. 나의 노드를 삭제한다.
      2. 동생이 없으면:
         1. 형과 나 사이의 키를 부모로부터 받는다.
         2. 그 키와 형의 키를 차례대로 나에게 합친다.
         3. 형의 노드를 삭제한다.
3. 루트 노드까지 필요한 경우 병합 및 키 이동 작업을 반복한다.
   1. 루트 노드가 비어있다면:
      1. 루트 노드를 삭제한다.
      2. 직전에 병합된 노드가 새로운 루트 노드가 된다.

 

B Tree가 DB 인덱스로 사용되는 이유

B 트리, AVL 트리, RB 트리 모두 O(logN)의 시간 복잡도를 가지지만, B 트리가 데이터베이스 인덱스로 널리 사용되는 이유는 그 구조가 디스크 I/O와 잘 맞아떨어지기 때문이다.

• 데이터베이스는 대량의 데이터를 저장하고 관리하기 위해 디스크에 의존한다. 디스크 I/O는 시스템 성능의 주요 병목 중 하나로, 가능한 한 적은 횟수로 많은 데이터를 읽는 것이 중요하다.
• B 트리는 각 노드에 여러 개의 키와 자식 포인터를 저장할 수 있다. 이러한 노드는 디스크의 하나의 블록에 해당하며, 디스크 I/O 한 번으로 다수의 키를 메모리로 불러올 수 있다. 때문에 디스크에 접근하는 횟수가 적으며 블록 단위의 저장 공간을 알차게 사용할 수 있다.
• B 트리는 높은 차수(degree)를 가질 수 있어, 트리의 높이가 낮다. 트리의 높이가 낮을수록 데이터에 접근할 때 필요한 디스크 I/O 횟수가 줄어들어 성능이 향상된다.

블록은 데이터를 저장하고 관리하는 기본적인 단위로, 디스크에서의 읽기/쓰기 작업의 최소 단위다.