#11 트리(Tree) 5 - B-Tree

이전에 설명했던 자가균형 이진트리인 AVL 트리나 레드블랙 트리는 메모리상에서 데이터를 빠르게 삽입, 삭제하고

탐색하는데에는 충분한 성능을 보인다.  하지만 읽고 쓰는 대상이 메모리상의 데이터가 아닌 외부 저장장치가 되면

이야기는 달라진다.  기본적으로 외부 저장장치에 대한 입출력은 입출력의 단위인 버퍼의 크기 내에서는 데이터가

많든 적든 똑같은 속도를 보이며 이 속도는 기본적으로 굉장히 느리기때문에 메모리 내에서의 처리속도가 느려지더라도

입출력 횟수를 줄이는 쪽이 성능 개선으로 이어진다.  즉, 하나의 노드당 하나의 데이터와 2개의 자식노드만을 가질 수

있는 이진트리는 외부 저장장치에의 입출력을 고려하면 효율적이지 못한것이다.

 

 

1. 다원 탐색 트리(Multi-way Search Tree)

 이를 해결하기 위해 이진탐색트리와 동일하게 좌측 자식노드는 부모노드보다 키 값이 작고 우측 자식노드는

부모노드보다 키 값이 크지만 하나의 노드가 다수의 데이터와 2개보다 많은 자식노드를 가질 수 있도록 하는

다원 탐색 트리(Multi-way Search Tree, 이하 MST)를 사용할 수 있다. 

 

위 그림처럼 하나의 노드에 n개의 데이터가 들어간다면 자식노드는 n+1개까지 가질 수 있는 것이다.

 

 

2. B-Tree

 그런데 이진탐색트리의 문제점이 MST에서도 마찬가지로 발생한다.  균형이 어긋날 경우 탐색속도를 보장할 수

없다는 것이다. 필연적으로 MST에도 균형을 유지하도록 삽입, 삭제가 이루어지는 트리가 생겼다. 이것이 B-Tree 이다. 

B가 무엇을 의미하는지는 창시자가 따로 밝힌바가 없기에 알 수없지만 균형잡힌 MST이니 Balanced의 B라고 생각해도

좋을 것이다. 

 

 ① B-Tree 의 용어

• 하나의 노드가 가질 수 있는 자식노드의 최대 갯수를 트리의 차수(degree)라고 한다.
• 차수가 M 인 B-Tree 를 M차 B트리라고 한다.

 

 ② B-Tree 의 규칙 (M차 B트리)

• 루트 노드는 최소 2개의 자식노드를 가져야한다.
• 루트 노드를 제외한 모든 노드는 최소 floor(M/2) 개의 데이터를 가져야한다.
• 모든 내부 노드는 데이터갯수+1 개의 자식노드를 가져야한다
• 모든 노드는 최대 M 개의 자식노드만 가질 수 있다.
• 모든 리프 노드는 같은 레벨이어야한다.
• 노드 내의 데이터는 정렬된 상태여야한다.
• 입력되는 자료는 중복될 수 없다.

 

 ③ B-Tree 의 특징

• 자료의 삽입이 항상 리프 노드에서 이루어지며 트리가 아래로 뻗어나가는 것이 아닌 위로 자라는
  Bottom-up 방식이다.
• 일반적으로 하나의 노드가 가질 수 있는 데이터의 갯수는 저장장치의 블록 크기와 유사하게 설정된다.
• 항상 노드내에 데이터가 최소 반 이상은 채워져있기 때문에 블록(노드)단위의 입출력이 효율적이다.
• 순차탐색을 위해서는 inorder 순회를 해야하기 때문에 순차탐색이 비효율적이다.

 

 

3.  B-Tree 의 삽입 연산

① 공통 부분

• 트리가 비어있다면 루트노드를 할당.
• 이진 탐색 트리와 같은 요령으로 삽입할 노드를 탐색

 

② Case 1. 분할이 발생하지 않는 경우

• 단순히 삽입할 노드에 오름차순 정렬상태를 유지하도록 키 값 삽입

 

③ Case 2. 분할이 발생하는 경우

• 삽입할 노드에 오름차순 정렬상태를 유지하도록 키 값 삽입
• 노드에 들어있는 데이터 갯수가 한도를 넘어섰을 경우 노드의 중간값을 기준으로 노드를 반으로 분할
• 분할의 기준이 된 중간값은 부모노드로 올려보낸다.  부모노드가 없을 경우 중간값을 새로운 루트 노드로 설정
• 부모노드에 올라간 중간값으로 인해 부모노드가 데이터 갯수 한도를 넘겼을 경우 같은 방식으로 분할

 

 

4. B-Tree 의 삭제 연산

① 공통 부분

• 트리가 비어있다면 종료
• 이진 탐색 트리와 같은 요령으로 삭제할 노드를 검색
• 삭제할 노드를 찾지못했다면 종료

 

② Case 1. 삭제할 키 값이 리프노드에 있고 해당 노드의 키 갯수가 최소 키 갯수보다 많을 경우

• 단순히 노드에서 해당 데이터를 찾아서 삭제

 

③ Case 2. 삭제할 키 값이 리프노드에 있고 해당 노드의 키 갯수가 최소 키 갯수와 같으며
               인접한 형제노드 중 키 값을 빌려올 노드가 있을 경우

• 노드에서 해당 데이터를 찾아서 삭제
• 삭제로 인해 노드의 최소 키 갯수를 만족하지 못하게 됨
• 왼쪽 형제노드중 최댓값 혹은 오른쪽 형제노드중 최솟값을 부모 key 값으로 올리고
  기존 부모 key 값을 가져와서 최소 키 갯수를 맞춤

 

④ Case 3. 삭제할 키 값이 리프노드에 있으며 해당 노드의 키 갯수가 최소 키 갯수와 같으며
               인접한 형제노드의 키 갯수가 모두 최소 키 갯수와 같을 경우 

• 노드에서 해당 데이터를 찾아서 삭제
• 삭제로 인해 노드의 최소 키 갯수를 만족하지 못하게 됨
• 형제노드로부터 값을 빌려올 수 없기 때문에 한쪽 형제 노드와 부모key값, 해당노드를 하나의 노드로 병합
• 병합을 위해 부모노드의 key 값 하나가 삭제되기 때문에 부모노드를 리프노드로 간주하고 Case1~3 의 작업을
  부모노드에 대해 수행해준다. 

 

⑤ Case 4. 삭제할 키 값이 내부노드에 있을 경우

• 이진 탐색 트리때와 마찬가지로 좌측 서브트리중 최댓값 또는 우측 서브트리중 최솟값을 후임자로
  가져와 삭제할 데이터를 대체
• 후임자 데이터는 리프노드의 값이기 때문에 리프노드에서의 삭제과정으로 이행한다.

 

5. B+Tree

 B+Tree 는 B-Tree의 개량버전으로 기본적으론 B트리와 거의 유사하지만 다음과 같은 차이점이 있다.

① 내부 노드에는 key 값만이 존재한다.

   B+Tree 는 B-Tree 와는 달리 내부 노드에는 데이터가 존재하지 않는다. 즉, 내부 노드는 데이터를 찾아가기

   위한 key값을 가질 뿐 실제 데이터는 모두 리프노드에 존재한다.  데이터를 저장하지 않는 덕분에 하나의

   Disk Block에 더 많은 노드를 저장할 수 있으며 결과적으로 key 탐색시에 읽어야할 Disk Block의 갯수가 

   줄어들어 B-Tree 보다 효율적인 탐색이 가능하다.

 

② 리프 노드끼리는 Linked List 형태로 연결되어있다.

   B+Tree의 리프 노드들은 서로 연결리스트 형태로 이어져있기 때문에 순차탐색의 효율이 B-Tree보다 뛰어나다.

   

 많은 파일시스템들이 블록 인덱싱을 위해 B+트리를 사용하며 데이터베이스에서도 테이블 인덱싱을 위해

 B+트리가 종종 사용된다.