[Data Structure] B+Tree

B+Tree란?

B+Tree란 B-Tree의 변형으로, 데이터베이스에서 널리 쓰이는 자료구조 중 하나이다.

B+Tree의 특징

• 데이터를 가리키는 포인터는 leaf node에만 존재한다.
• internal node는 key 및 자식 노드를 가리키는 포인터만 존재한다.
• 모든 key값과 데이터를 가리키는 포인터는 leaf node에 존재한다. internal node의 키 값이 leaf node에 또 존재하므로 중복된 키 값이 있을 수 있다.
• leaf node들은 linked list로 연결되어 있다. 따라서 형제 노드에 link를 통해 쉽게 접근할 수 있다

출처: https://en.wikipedia.org/wiki/File:Bplustree.png

B-Tree와의 유사점

• 노드 안의 key들은 오름차순으로 정렬되어 있다.
• 삽입은 leaf node에서 일어난다.
• 제거 시 트리의 balance를 맞추기 위해 재조정이 일어난다.

B+Tree와의 차이점

	B-Tree	B+Tree
검색 방법	모든 노드에 key와 값이 존재하므로 search algorithm (e.g. inorder traversal)을 통해 모든 노드를 순회하며 찾는다.	leaf node에만 값이 존재하므로 데이터를 검색할 때 항상 leaf node로 이동한 후 탐색한다. 따라서 탐색 경로가 단순해진다.
범위 쿼리와 범위 검색	범위 쿼리를 수행하려면 트리의 root에서 leaf까지 이동하며 internal node도 검색해야 하므로 불필요한 탐색 과정이 발생한다.	범위 쿼리를 수행하기 위해 leaf node끼리 연결되어 있는 포인터로 이동만 하면 되므로 간단하다.
순차 탐색	순차적인 탐색을 위한 알고리즘이 필요하다.	연결된 리스트를 따라가면 된다.
메모리 사용	모든 노드가 자식 노드를 가리키는 포인터와 데이터를 가리키는 포인터를 가지므로 노드 하나가 B+Tree보다 더 많은 메모리를 차지한다.	데이터를 가리키는 포인터는 leaf node에만 존재하므로 메모리 효율이 B-Tree에 비해 좋다.

 

B-Tree와 B+Tree의 internal node를 간단하게 나타낸 그림이다.

간략하게 나타낸 그림입니다. 정확하지 않을 수 있습니다.

 

---

참고
https://www.youtube.com/watch?v=aZjYr87r1b8 (이 영상이 B+Tree를 이해하는 데 많은 도움이 되었다.)
https://engineerinsight.tistory.com/336