B Tree

BST(Binary Search Tree)의 개념과 특징

• 모든 노드의 왼쪽 서브트리는 해당 노드보다 작은 값을 가지며, 오른쪽 서브트리는 해당 노드보다 큰 값을 가진다.
• 자녀 노드는 최대 두개를 가질 수 있다.

B Tree의 개념

• 이진탐색트리(BST)를 일반화한 Tree
• 자녀 노드의 최대 개수를 동적으로 조정할 수 있는 자료구조.
• 최대 M개의 자녀를 가질 수 있는 B Tree를 M차 B Tree라고 한다.

B Tree의 속성

• M: 각 노드의 최대 자녀 노드 개수
• M-1: 각 노드의 최대 키 개수
• [M/2]: 각 노드의 최소 자녀 노드 개수
• [M/2]-1: 각 노드의 최소 키 개수

root node, leaf node는 위 속성을 따르지 않는다.

B Tree의 특징

• internal 노드의 key 수가 x개라면 자녀 노드의 개수는 언제나 x+1개이다.
• 노드가 최소 하나의 key는 가지기 때문에 몇차 B Tree인지와 상관없이 internal노드는 최소 두개의 자녀 노드는 가진다.
• M이 정해지면, root 노드를 제외하고 internal 노드는 최소 [M/2]개의 자녀 노드를 가진다.
• 노드 내의 key들은 오름차순으로 정렬되어 저장된다.
• 모든 leaf 노드는 같은 레벨에 있다. (모든 leaf 노드가 같은 깊이에 있다.)
• balanced tree이기 때문에, 검색의 avg/worst case 시간복잡도는 O(logN)이다.

B Tree 데이터 삽입 방식

• 추가는 항상 leaf 노드에 이루어진다.
• 노드가 넘치면 가운데 key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.

B Tree 데이터 삭제 방식

• 삭제는 항상 leaf 노드에서 이루어진다.
• 삭제 후 최소 key 수보다 적어졌다면 재조정한다.
• internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 leaf 노드에서 삭제한다. (삭제할 데이터의 선임자나 후임자를 찾아서 위치를 바꾼다.)

predecessor: 삭제할 데이터보다 작은 값 중 가장 큰 값
successor: 삭제할 데이터보다 큰 값 중 가장 작은 값

재조정 방식

1. key수가 여유있는 형제의 지원을 받는다.
2. 1.이 불가능하다면 부모의 지원을 받고 형제와 합친다. (부모의 key를 왼쪽으로 내려보내고 형제와 합친다.)
3. 2번 후 부모에 문제가 있다면 거기서 다시 재조정한다.

B Tree가 DB index에 사용되는 이유

• DB는 secondary storage에 저장되기 때문에, 디스크 I/O가 성능에 큰 영향을 미친다. (최대한 디스크 I/O를 줄여야 한다.)
• block 단위로 데이터를 읽고 쓰기 때문에 연관된 데이터를 모아서 저장하면 더 효율적으로 읽고 쓸 수 있다.
• B Tree index는 self-balancing BST(AVL Tree)에 비해 디스크 I/O를 최소화할 수 있는 구조로 설계되어 있다.
• B Tree 노드는 연관된 데이터를 모아서 저장하기 때문에, block 단위의 저장 공간을 효율적으로 사용할 수 있다.

vs Hash Index : 동등 검색에 최적화되어 있지만, 범위 검색이나 정렬된 순서로 데이터를 읽는 데는 B Tree가 더 효율적이다.