B-Tree, B+Tree, B*Tree에 대해 설명하세요
Keyword
depth, balance, inner node, leaf node, multiway search tree, key, data, block, pointer, 순차 탐색 문제, 분할, 병합, 메모리 낭비
Script
B-Tree는 각 Node에 여러개의 Key와 Child를 가질 수 있는 multiway search tree입니다. 이때 모든 Leaf Node는 동일한 Depth를 가지며 Tree의 균형을 맞출 수 있습니다. N Order B-Tree의 경우 각 Node에 최대 N-1개의 key와 N개의 Child를 가집니다. 그리고 일반적인 Multiway Search Tree처럼 각 노드 내에서 key는 오름차 순으로 정렬됩니다. 이렇게 하나의 Node에 여러개의 key를 가지는 특성 덕분에, 용량이 큰 Block 단위로 Data를 읽고 쓰는 Disk 환경에서는 Binary Search Tree보다 B-Tree가 효율적입니다.
B+Tree는 B-Tree의 개량형 자료구조로, 가장 큰 차이는 Leaf Node에만 Key와 Data가 저장되고 Inner Node에는 Key만 저장된다는 것입니다. 각 Leaf Node를 Pointer로 연결하여 B-Tree에 비해 순회가 쉽다는 장점이 있습니다. 그리고 Inner Node에 Data를 넣지 않기 때문에, B-Tree보다 Inner Node의 용량이 작아, 하나의 Disk Block에 더 많은 Inner Node를 배치할 수 있어 Key 탐색에서 B-Tree보다 유리합니다.
B*Tree는 B+Tree처럼 B-Tree의 개량형 자료구조로, 순차 탐색 문제를 해결하기 위한 B+Tree와는 달리 메모리 낭비와 보조 연산 문제를 해결하기 위한 자료구조입니다. 실제 대용량 시스템에서는 B-Tree를 운용하면 전체 노드의 상당 부분이 비어있게 되어 메모리 낭비 문제를 일으킵니다. 또 B-Tree의 삽입/삭제 연산에서 분할과 병합 연산을 최소로 줄이기 위해 고안된 자료구조라고 할 수 있습니다.
Additional
B-Tree, B+Tree
B-Tree
B+Tree
B+Tree는 B-Tree의 변형된 형태로, data를 linear하게 탐색해야할 경우에 순차 접근을 해야하는데, B-Tree에서는 inOrder 탐색을 통해 Tree의 모든 Node를 방문해야한다.
하지만 B+Tree의 경우, Data는 모두 Leaf Node에 있고, 그들이 pointer로 연결되어있기 때문에 순차 집합(Sequence Set)이 만들어지고 이를 통해 key 값 기준 순차 탐색에 유리하도록 설계되었다.
이러한 특성 때문에 Leaf Node를 제외한 Inner Node들은 단지 key 값과 pointer만 저장하게 되어, 인덱스 집합(index set)이라 불리고 leaf node의 data들의 index 역할을 하게 된다.
B+Tree의 삽입
- 리프 노드가 full 상태가 아니라면 오름차순 정렬에 맞게 삽입한다.
- 리프 노드가 full 상태라면 노드를 분할해야 한다.
- 새로운 리프 노드를 구성하고 기존 리프 노드 데이터의 절반을 옮긴다.
- 새로운 리프 노드의 최소 키(기존 리프 노드의 중간값)를 부모 노드에 삽입하여 기준 포인터로 삼는다.
- 부모 노드 역시 리프 노드의 key를 받았으므로 full 상태인지 체크해야 한다.
(부모 노드가 쪼개지지 않는 시점이 올 때까지 상향식으로 반복한다.)
- 루트가 쪼개지면 새로운 루트 노드를 생성하되 1개의 키와 2개의 양쪽 포인터로 구성되어야 하며 기존 루트 노드의 중간 key는 새로운 루트 노드에 저장한 뒤 제거한다.
B*Tree
B-Tree의 경우, 각 Node는 disk의 block과 같기 때문에, Node 하나에 접근하는 것은 disk를 한번 더 접근하는 것과 같다. 그래서 적은 수의 Node를 가질수록 index 구조의 성능을 높이는데 도움이 된다. B*Tree는 이와 같은 맥락에서, 생성되는 Node 수를 줄이기 위해 고안되었다.
또, B-Tree는 균형을 유지하기 위해 삽입 과정에서의 분열과 삭제과정에서의 합병과 같은 보조연산이 필요하다. B*Tree는 이와 같은 보조 연산을 가급적 지연시키는 설계로 이루어져있다.
B*Tree는 B-Tree와 다르게 모든 Node는 2/3 이상 채워져야 한다. (B-Tree는 1/2 이상) 즉, 최대한 Node 사용률을 높이는 것이다. 또, B-Tree는 Node가 가득차면 분열하여 새로운 Node를 만드는데, B * Tree는 이웃한 형제 Node로 재배치한다. 이 또한 Node의 사용률을 높이기 위한 설계이다. 최대한 분열을 늦추어 불가피한 상황을 제외하고는 Node를 새로 만들지 않는다.
