B-트리 (B-Tree)

B-트리 (B-Tree)

 

B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.

ex) 6차 B-트리의 일부

• B-트리는 디스크 환경에서 사용하기에 적합한 외부 다진 검색 트리이다.
• B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있다.
• 최대 M개의 자식을 가질 수 있는 B-트리를 M차 B-트리라고 한다.
• 노드는 최대 M개의 자식 노드를 가질 수 있다.
  ex) 3차 B-트리라면 최대 3개의 자식 노드를 가질 수 있다.
• 노드에는 최대 M-1개의 KEY를 가질 수 있다.
  ex) 3차 B-트리라면 최대 2개의 KEY를 가질 수 있다.
• 각 노드는 최소 ⌈M/2⌉개의 자식 노드를 가진다. (루트 노드와 leaf 노드 제외)
  ex) 3차 B-트리라면 각 노드는 최소 2개의 자식 노드를 가진다.
• 각 노드는 최소 ⌈M/2⌉-1개의 키를 가진다. (루트 노드 제외)
  ex) 3차 B-트리라면 각 노드는 최소 1개의 키를 가진다.
• internal 노드의 KEY가 x개라면 자녀 노드의 수는 언제나 x+1 개다.

 

디스크에 데이터를 읽고 쓰기 위해서는 블록 단위로 접근을 한다. 단 한 바이트만 읽거나 쓰고 싶어도 한 블록을 통째로 읽어오거나 써야 한다. 디스크의 한 블록은 보통 8K(8192Byte), 16K(16384Byte) 등이다. 이 블록을 소프트웨어 레벨에서는 보통 페이지(Page)라 한다.

디스크 블록의 크기와 노드의 크기를 일치시키는 것은 디스크에서 정보를 읽어올 때는 블록(페이지)단위로 읽어오기 때문에 최대한 효율을 높이기 위해서다.

 

Ex) B-트리 구조

B-트리에서 검색

B-트리에서 검색은 기본적으로 이진 탐색 트리에서 검색과 같다.

이진 탐색 트리에서는 컴색키가 노드의 키와 일치하는 것이 있는지 확인하는 반면, B-트리에서는 노드의 여러 키 중 검색키와 일치하는 것이 있는지 확인한다. 또한 검색키에 대한 값을 찾기 위해 두 키(Key1 < x < key2)를 찾아 분기를 한다.

자식으로 분기를 하고 나면 깊이만 하나 내려간 똑같은 검색 문제가 되어 재귀 호출로 처리할 수 있다.

 

B-트리에서 삽입

1. x를 삽입할 리프 노드 r을 찾는다.
2. 노드 r에 공간의 여유가 있으면 키를 삽입하고 끝낸다.
3. 노드 r에 여유가 없으면 형제 노드를 살펴 공간의 여유가 있으면 형제 노드에 키를 하나 넘기고 끝낸다.
4. 형제 노드에 여유가 없으면 가운데 키를 부모 노드로 넘기고 노드를 두개로 분리한다.

5 삽입

5를 해당 리프노드에 삽입하면 오버플로가 발생한다.

바로 오른쪽의 형제 노드에 공간의 여유가 있으므로 키를 하나 넘긴다.

6을 형제 노드로 넘기면 트리의 성질이 깨지므로 부모 노드에 있는 7을 넘기고 그 자리에 6을 놓는다.

이것을 재분배(Redistribution)라 한다.

 

B-트리에서 삭제

1. x를 키로 갖고 있는 노드를 찾는다.
2. 이 노드가 리프 노드가 아니면 x의 직후 원소 y를 가진 리프 노드 r을 찾아 x와 y를 맞바꾼다.
3. 리프 노드에서 x를 제거한다.
4. x제거 후 노드에 언더플로가 발생하면 적절히 해소한다.

언더플로가 발생하면 우선 키를 가져올 수 있는 형제 노드가 있는지 본다. 노드가 있을 경우 채우고 끝낸다.

그렇지 않을 경우 형제 노드와 병합을 진행하는데, 부모 노드의 키 중 하나가 필요 없으므로 키 하나와 두 노드를 합쳐 병합한다.

4를 삭제하려 한다.

4가 리프 노드에 있지 않으므로 4의 바로 다음 원소를 갖고 있는 리프를 찾는다.

4의 다음 원소는 5이다.

4와 5를 교환한다.

4를 제거하면 해당 리프에서 6하나만 남아 언더플로가 발생한다.

형제 노드 중 키를 내놓을 수 있는 여분이 있는 노드가 있는지 확인한다.

왼쪽의 노드가 여분을 갖고 있으므로 키 3을 가져온다.

키 3을 바로 6옆에 놓을 수 없으므로 부모 노드에 있는 5를 끌어내리고 그 자리에 3을 놓는다.