[DS] B+Tree [1] — VS B-Tree, (Range) Search
이번 글에서는 B-Tree 와 비교하여 B+Tree 는 어떤 특징을 가지고 있는지 다룬다. 참고로 B-Tree 에 대한 글을 아래 목록에서 확인할 수 있다.
👉 DS — B-Tree [1] — Balanced Tree, Binary Search Tree, Self-Balancing BST
| B+Tree
B+Tree 는 B-Tree 와 달리 리프 노드에서 트리의 모든 Key 를 가지고 있다. 예를 들어, 1 -> 2 -> … -> 10 을 순서대로 추가한 B+Tree 는 리프 노드에 1 ~ 10 값을 갖는 모든 키가 저장되어 있어야 한다.
먼저, B-Tree 를 통해서 어떤 차이가 있는지 확인해보자. [ 그림 1 ] 은 3차 B-Tree 에 1 -> 2 -> … -> 10 순서대로 값을 추가한 결과를 보여 준다. 이 때 B+Tree 에서 설명한 것과 달리 B-Tree 는 리프 노드에 1 ~ 10 범위의 모든 키가 저장되어 있지 않은 것을 볼 수 있다.
[ 그림 2 ] 는 3차 B+Tree 에 마찬가지로 1 -> 2 -> … -> 10 순서로 값을 추가한 결과를 보여 준다. 앞서 B+Tree 설명과 같이, [ 그림 2 ] 의 리프 노드를 보면 1 ~ 10 범위의 모든 키가 리프 노드에 저장되어 있는 것을 볼 수 있다.
[ 그림 3 ] 을 보면, 루트 노드를 포함한 내부 노드의 키와 달리 리프 노드의 키에는 * 가 붙어 있는 것을 볼 수 있다. 이는 임의로 리프 노드에 모든 키가 포함되어 있다는 것을 설명하고, 내부 노드의 키와 구분하기 위해 추가 했다. 현재 예시로 든 내용은 노드 내부의 키가 그 자체로 데이터를 의미하기 때문에 내부 노드의 키와 리프 노드의 키가 같은 경우 이를 구분하는 것이 큰 의미가 없어 보인다. 예를 들어, [ 그림 3 ] 에서 루트 노드에 포함된 5 와 리프 노드에 포함된 5 는 각 Key 가 갖고 있는 값을 기준으로 보면 차이가 없다.
따라서 다른 예시를 통해, B+Tree 에서 루트 노드를 포함한 내부 노드와 리프 노드의 차이를 확인해보자.
예를 들어, [ 그림 4 ] 와 같이 Map 타입 <Key, Value> 의 데이터를 저장할 때 내부 노드와 리프 노드 간의 차이가 분명해진다. 우선 위에서 설명한 것과 같이 리프 노드에는 모든 Key 와 이에 해당하는 데이터를 저장한다. 반면 내부 노드에는 Key 에 해당하는 데이터를 저장하지 않고, 단지 리프 노드에 있는 각 Key 에 접근할 수 있도록 중간에서 라우터와 같은 역할을 한다. B-Tree 와 달리, B+Tree 를 이용하면 내부 노드에서 데이터를 저장할 필요가 없으므로 해당 공간 만큼 추가로 Key 를 관리할 수 있어 상대적으로 더 얕게 Search 해서 원하는 값을 찾을 수 있다는 이점이 있다.
B+Tree 는 B-Tree 에서 볼 수 없는 또 다른 특징이 있는데, [ 그림 4 ] 에서 리프 노드가 서로 연결되어 있다는 점이다. 이중 연결 리스트를 통해서 해당 관계를 구현할 수 있다. 이렇게 리프 노드 간의 관계를 연결짓는 것으로 얻을 수 있는 효과는 어떤 것이 있을까?
결론부터 말하면, B+Tree 는 B-Tree 에 비해 Range Search (구간 탐색)에 효율적이다.
이를 설명하기 전에 B+Tree 의 Search 과정을 먼저 이해해야 하는데, 특정 Key 를 Search 하는 것은 B-Tree 와 동일하다. 예를 들어, [ 그림 4 ] 에서 Key 1 을 찾는 과정은 다음과 같다. 루트 노드의 키 값이 3 이므로 (1 보다 큰 값) 루트 노드의 왼쪽 자식 노드로 이동한다 마찬가지로 해당 노드의 Key 값이 1 보다 큰 값이므로 또 다시 왼쪽 자식 노드로 이동하고, 이 때 노드의 Key 값이 1 이므로 Search 가 종료된다.
Range Search 에 효율적인 이유는 바로 리프 노드 간의 양방향으로 연결된 관계에서 찾을 수 있다. B-Tree 는 Range 에 해당 하는 Key 에 대해서 매번 바로 위에서 예로 든 Search 과정을 반복해야 한다. 반면, B+Tree 는 최초 한 번만 리프 노드에 도달한 뒤 이중 연결 리스트를 통해 구현된 양방향 관계를 이용하여 순차적으로 구간에 해당 하는 Key 에 접근할 수 있기 때문에 상대적으로 빠르고, 효율적으로 Range Search 가 가능하다.
| Reference
The Difference Between B-trees and B+trees | Baeldung on Computer ScienceDifference between B tree and B+ tree — GeeksforGeeks
