[개발 일기] 2025.01.16 - B+Tree

개요

 

어젠 B-Tree에 대한 일기를 썼다.

 

 

오늘은 B-Tree의 단점을 보완한 자료구조인 B+Tree에 대해 정리해 보자.

 

 

 

B+Tree

 

B+Tree는 현업에선 데이터베이스의 인덱스에 주로 사용된다.

 

 

대부분의 대부 구조는 B-Tree와 유사하다.

 

 

하지만 크게 두 가지 다른 점이 있다.

1. 내부 노드는 키만 저장하고, 데이터는 리프 노드에만 저장
2. 리프 노드는 데이터를 저장하는 곳으로, 리프 노드들은 연결 리스트 형태로 서로 연결

 

 

내부 노드는 키만 저장하고, 데이터는 리프 노드에만 저장

 

아래의 B+Tree 구조를 보면 리프노드에만 데이터가 저장되어 있는 것을 볼 수 있다.

 

 

이러한 구조의 장점은 크게 세 가지이다.

1. 리프 노드에만 데이터가 저장되고, 나머지 내부 노드는 키만 저장하기 때문에 기존의 B-Tree 보다 용량 측면에서 더 유리하다.
2. 내부 노드는 데이터를 저장하지 않기 때문에 용량이 남는다. 그렇다면 트리 내부에 더 많은 데이터를 저장할 수 있는 것이다.
3. B+Tree의 내부 노드에서 더 많은 키를 관리할 수 있기 때문에 조회 측면에서 더 유리하다.

 

 

리프 노드는 데이터를 저장하는 곳으로, 리프 노드들은 연결 리스트 형태로 서로 연결

 

 

리프 노드들이 연결 리스트 형태로 연결되어 있기 때문에, 범위 검색 시 연속적인 데이터를 빠르게 탐색할 수 있다.

 

 

예를 들어, "A"부터 "Z"까지의 모든 데이터를 순차적으로 찾고자 할 때, 연결 리스트를 따라가며 리프 노드를 하나씩 처리하면 된다.

 

 

만약 B-Tree의 경우 루트 노드부터 탐색해야 하지만 B+Tree는 한 번의 순차적인 접근으로 범위 내 모든 데이터를 얻을 수 있다.

 

 

 

느낀 점

 

다음에 기회가 된다면 B-Tree, B+Tree를 직접 구현해 데이터베이스를 만들어봐야겠다.

 

 

벌써 설레네.. 이걸로 떼돈 벌어야지..