데이터베이스에 데이터가 저장될 때는 Tree구조로 저장된다.
하지만, Tree구조로 배치해놔도 절반씩 갈라가며 탐색하기 때문에 데이터의 양이 많아지면 굉장히 오래걸린다.
이진탐색기법을 적용한 데이터베이스 구조를 BST(Binary Search Tree) 구조라고 하는데, 여기서 더 효율적이고 빠르게 탐색하기 위해서 Node라는 개념을 적용한다.
기존의 BST는 1/2 탐색을 한다면, 오래 걸릴 탐색을 1/3 혹은 1/4로 탐색을 하여 탐색을 보다 빠르게 한다.
이것이 B-Tree 구조라고 한다.
근데 쓰다보니, 이것도 비효율적이다.
왜? 순차탐색을 할때, 중위순회를 하기 때문이다. (혹시 순차탐색과 중위순회가 뭔지 모른다면, 공부하고 오기 바란다)
B-Tree 구조를 약간 변형시켜, 순차탐색을 효율적으로 할 수 있게 만든 구조가 바로 B+Tree 구조다.
뭐가 다른가?
B-Tree 구조에서는 하나의 Node에 하나의 Key 값만 존재할 수 있었지만, B+Tree에서는 하나의 Node에 여러 개 Key가 존재할 수 있다.
또한 B+Tree 구조에서 데이터는 Leaf Node에만 저장되고, 이 Leaf Node는 Linked List로 연결되어 있으며, 내부 노드는 Index 역할만 한다.
이게 무슨 소리냐...
- "데이터가 Leaf Node에만 저장된다" ?
실제 데이터는 Leaf Node. 즉, 가장 하위 레벨의 노드(트리의 가장 하단)에 저장된다.
이와 반대로 BST, B-Tree는 중간 노드에도 데이터가 저장될 수 있다.
- "Leaf Node는 Linked List로 연결된다" ?
Leaf Node의 Node Group이 아래와 같다면
1 2 3 | 4 5 6 | 7 8 9
2~5까지의 데이터를 찾을 때, B+Tree가 아니라면, 상위 Node를 거쳐서 옆 Node로 이동해야 하지만,
1 2 3 -> 4 5 6 -> 7 8 9
와 같이 Node끼리 이어져 있기 때문에 Range Search(범위 탐색)을 할때 굉장히 효율적이다.
- "내부 노드는 Index 역할만 한다":
말 그대로 내부 노드는 Data가 아니라 Index 역할만 한다.
즉, Value를 가지고 있는 것이 아니라 Value가 있는 곳을 가리키는 Reference를. 즉, Pointer만 갖고 있는 것이다.
이를 통해 탐색 과정에서 어떤 경로로 내려가야 할지 안내를 하는 이정표 역할을 수행할 수 있게 된다.
아직도 이해가 안 되는 사람들을 위해 (물론 그럴 수 있다) 그림을 제작해봤으니, 이해하는 데 도움이 됐으면 좋겠다.
Tree 구조 설명(B+Tree)