[자료구조] B-Tree

 

 

B-Tree가 사용되는 이유

 

 

 

효율적 자료 탐색의 도구로 활용되는 이진트리는 검색과 삽입에 효율적이지만, 대용량 데이터에서 불편한 면이 있다.

 

이진탐색트리의 삽입,삭제 연산 시간복잡도

이진탐색트리의 삽입과 삭제 연산은 탐색이후 이루어지기 때문에 탐색에 필요한 O(h)이 소요되며 연결리스트를 사용하므로 입력과 삭제에는 O(1)이 사용된다.

따라서 총 소요되는 시간 복잡도는 O(h)이며 최악의 경우 탐색과 동일하게 O(N)이 소요된다.

 

따라서, 이진 탐색 트리는 한쪽 방향으로 노드가 집중된 편향트리에서는 효율적이지 않다.

 

이러한 이진트리의 특징에 대응하여 B트리는 각 노드에 여러 키를 저장할 수 있고, 여러 하위 노드를 가질 수 있다는 특징을 활용하여 트리의 높이가 상대적으로 낮아질 수 있으며, 한 번의 디스크 액세스로 많은 양의 데이터를 읽을 수 있습니다.

이러한 특징을 통해 대량의 데이터를 저장하고 검색하는 경우 디스크 액세스 속도를 최소화 하는 자료구조이다. 

 

M차 B-Tree 특징

최대 M개의 자식을 가질 수 있는 B 트리를 M차 B-Tree라고 한다. 

 

1. 노드는 최대M개의 자식 노드를 가질 수 있습니다.
2. 노드에는 최대 M-1개의 KEY를 가질 수 있습니다.
3. 각 노드는 최소 ⌈M/2⌉개의 자식 노드를 가집니다.
4. 각 노드는 최소 ⌈M/2⌉-1개의 키를 가지게 됩니다.

 

 

B-Tree 삽입

밑 링크로 데이터들을 삽입하면서 B-Tree가 내부적으로 어떻게 저장이 되는지 확인할 수 있다. 

https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-Tree Visualization

 

 

추가는 항상 leaf 노드에 한다. 

노드가 넘치면 가운데(Median) key를 기준으로 좌우 key들을 분할하고 가운데 key는 승진한다. 

 

1.트리가 비어있다면 루트 노드를 할당하고 K를 삽입합니다.
2. 트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드를 탐색합니다.
3. 리프 노드에 데이터를 넣고 리프 노드가 적절한 상태에 있다면 종료합니다.

리프 노드가 부적절한 상태에 있다면 분리합니다.