[자료구조] B-Tree란 무엇인가?

B-Tree란?

• B-Tree는 트리 자료구조의 일종으로 이진 탐색 트리(Binary Search Tree, BST)를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.
→ B-Tree를 이해하기 위해서는 이진 탐색 트리(BST)에 대해 먼저 이해하고 있어야 한다.

• B-Tree의 각 노드는 여러 개의 키(데이터)와 자식 노드의 주소를 저장할 수 있다. 노드의 키는 항상 정렬된 순서로 유지된다.

• 주로 데이터베이스와 파일 시스템에서 사용된다.

B-Tree의 특징?

• 이진 탐색 트리(BST)를 일반화한 트리다.

• 부모 노드는 자식 노드를 두 개 이상 가질 수 있다.

• 노드가 자식 노드를 $O(logN)$개 가졌다면 key 는 $O(logN)$개를 갖는다.

• 노드 내의 키(데이터) 들은 오름차순으로 저장된다.

• 모든 leaf 노드들은 같은 레벨에 있다.
→ 자가균형: 검색 / 삽입 / 삭제 작업이 항상 일정한 시간($O(logN)$)에 이루어 진다.

• 데이터가 매우 큰 경우에도, 트리의 높이가 낮아(차수는 높다) 검색, 삽입, 삭제 작업이 빠르다.

• B-Tree는 보조 메모리(SSD, HDD)에 적합하도록 설계되어 있다. 각 노드는 보조 메모리의 한 블록에 해당하며 높은 차수로 인해 트리의 높이가 낮다.

이진 탐색 트리(Binary Search Tree, BST)란?

• 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 갖는다.

• 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만을 갖는다.

• 자식 노드는 최대 두개까지만 갖는다.
→ B-Tree→ 자식 노드의 최대 개수를 늘리기 위해(2개 → 최대 n개: n차 B-Tree)

B-Tree

• 모든 leaf 노드들은 같은 레벨에 있다.
→ balanced tree
→ 검색 avg/worst case 모두 $O(logN)$을 갖는다.

• 이진탐색트리(Binary Search Tree, BST)를 일반화한 Tree라고도 함

• 자식 노드의 최대 개수를 늘리기 위해 ↔ BST 경우는 자식 노드의 최대 개수: 2개
• 부모 노드에 키(데이터)를 하나 이상 저장한다.
• 부모 노드의 키(데이터)들을 오름차순으로 정렬한다.
• 정렬된 순서에 따라 자식 노드들의 키(데이터) 값의 범위가 결정된다.



• 이런 방식을 활용하면 자식 노드의 최대 개수를 원하는 대로 변경하며 사용 가능
→ 즉, 최대 몇 개의 자식 노드를 가질 것인지가 B tree를 사용할 때 중요한 파라미터
 
• internal 노드의 키(데이터) 수가 개라면, 자식 노드의 개수는 언제나 개다.
• 노드가 최소 하나의 키(데이터)는 갖기 때문에 몇 차 B-Tree인지와 상관없이 B-Tree의 internal 노드는 최소 두 개 이상의 자식 노드를 갖는다.

B-Tree의 주요 파라미터

• M: 각 노드의 최대 자식 노드 수
• 최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부름
아래 사진은 3차 B-Tree

• M-1: 각 노드의 최대 키(데이터) 수

• M/2: 각 노드의 최소 자식 노드 수
• root node, leaf node 제외

• M/2 - 1: 각 노드의 최소 키(데이터) 수
• root node 제외

B-Tree 데이터 삽입

• 삽입할 위치를 찾는다. → 탐색(하양식)

• 삽입은 항상 leaf 노드에 한다

• 만약 노드가 가득 차 있다면 가운데 키(데이터)를 기준으로 좌우 키(데이터)들은 분할 하고 가운데 키(데이터)는 부모 노드로 올려 보낸다.
• 가운데 키(데이터)를 구하는 방법: M/2
1. M차 B-Tree (M이 홀수일 때 짝수일 때 동일한 방법)
1. 각 노드는 최대 M-1개의 키(데이터)를 갖는다.
2. 만약 가득 찬 노드에 데이터를 추가하게 된다면 해당 노드는 M개가 되고 이것의 가운데 값은 M/2번째 값으로 구할 수 있으며 이를 토대로 해당 키를 부모 노드로 보낸 후 좌우 키(데이터)들은 분할하여 포인터로 가르킨다.

B-Tree 데이터 삭제(leaf 노드일 때)

• 삭제도 항상 leaf 노드에서 한다.

• 삭제 후 최소 key 수(M/2 - 1: 각 노드의 최소 key 수 ) 보다 적어졌다면 재조정한다.
1. key 수가 여유 있는 형제노드(인접노드)의 지원을 받는다.
2. 1번이 불가능하면 부모의 지원을 받고 형제와 합친다
3. 2번 후 부모에 문제가 있다면 거기서 다시 재조정한다.

B-Tree 데이터 삭제(internal 노드일 때)

• internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제한다.
→ leaf 노드에 있는 데이터 중에 어떤 데이터와 위치를 바꿔 줄것인지가 이슈
→ 삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.
선임자(predecessor)
→ 나보다 작은 데이터들 중 가장 큰 데이터
후임자(successor)
→ 나보다 큰 데이터들 중 가장 작은 데이터
→ 선임자나 후임자는 항상 leaf 노드에 있으므로 삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.

왜 DB index로 B tree 계열이 사용되는가?

• BST는 불균형 트리도 존재하므로 의 시간복잡도가 존재함
→ 이는 보다 느리므로 balanced tree인 B-tree를 사용함

B - tree	avg case	worst case
조회	O	O
삽입	O	O
삭제	O	O

• 하지만 이를 해결하기 위한 self-balancing BST가 나옴
• AVL tree / Red-Black tree 등
→ 위 self-balancing BST는 을 만족

self-balancing BST	AVL tree	Red-Black tree
ㅤ	avg case	worst case
조회	O	O
삽입	O	O
삭제	O	O

Computer System

Secondary storage(SSD / HDD)

• 단점
• 불필요한 데이터까지 읽어올 가능성이 있다.

• 자녀 노드 수가 B tree는 3개 이상도 갖을 수 있으므로 데이터를 찾을 때 탐색 범위를 빠르게 좁힐 수 있다.
→ 즉, root노드에서 leaf 노드까지의 거리가 짧다.

• 각 노드의 데이터 수의 차이도 존재하여 훨씬 좋다.
→ 즉, block 단위에 대한 저장 공간 활용도가 더 좋다.

B tree의 강력함을 알아보자

with 101차 Btree

101차 B tree Best case

• 각 노드들이 최대 자녀수를 갖고 빈공간 없이 꽉 담을 때

101차 B tree Worst case

• 각 노드들이 최소 자녀수를 갖고 가능한 많은 빈공간을 갖을 때

• 추가적으로 root 노드와 leaf 노드는 최소 자녀 수와 최소 key수를 맞출 필요 없다

 

101차 B tree Avg case

• B tree index는 self-balancing BST에 비해 secondary storage 접근을 적게 한다.

• B tree 노드는 block 단위의 저장 공간을 알차게 사용할 수 있다.
→ 한 노드에 한 개의 데이터를 갖는 BST에 비해 한 노드에 여러 개의 데이터들을 갖을 수 있는 B tree가 성능면에서 더 좋다.

self-balancing BST의 노드들도 block 안에 최대한 담는다면?

Hash index를 쓴다면?