[자료구조] B-트리, B+트리

앞서 살펴본 AVL 트리는 이진 탐색 트리이나, 이제 살펴볼 트리들은 nonbinary tree이다.

스택 오버플로우에 의하면 AVL 트리는 인메모리 시에 랜덤 액세스가 상대적으로 cost가 적어 유용하지만, 디스크에 저장되는 경우에는 B-Tree가 유용하다고 한다. AVL 트리는 기본적으로 많은 양의 데이터를 저장하는 용도는 아니다. 그래서 데이터베이스에서 주로 인덱스 시에 B 트리를 활용하는 것인가... (FYI. 해시테이블이 인덱스로 쓰일 수 있으나, 주로 등호 연산만 가능하고, 부등호 표현은 불가능하기 때문에 비효율적이다.) B트리는 2개 이상의 child를 가질 수 있기 때문에 용량이 상대적으로 방대한 편이다.

 

B-트리는 탐색 성능을 높이기 위해 균형 있게 높이를 유지하는 Balanced Tree의 일종이다.

모든 leaf 노드가 같은 level로 유지되도록 자동으로 밸런스를 맞춰준다.

자식node의 개수가 2개 이상이며, node 내의 key가 1개 이상일 수 있다.

node의 자식 수 중 최댓값을 K라고 한다면, 해당 B-Tree를 K차 B-Tree라고도 한다.

 

B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다.

B+Tree는 오직 leaf node에만 데이터를 저장하고, leaf node가 아닌 node에서는 자식 포인터만 저장한다. → 메모리를 더 확보할 수 있다. 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.

그리고 leaf node끼리는 Linked List로 연결되어있다. → leaf node 탐색 시 선형의 시간이 소모된다.

또한 B+Tree는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가는 과정을 위해 key가 중복될 수 있다.

 

B+트리 시뮬레이터

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

B-Tree Visualization