B-tree
"데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다."
정리하자면, B-tree는 Binary search tree와 유사하지만, 한 노드 당 자식 노드가 2개 이상 가능하다 라고 할수있다.
여기서 먼저 트리구조에 대해 알아보자.
트리 구조는 꼭 데이터베이스에 한정하지 않더라도 시스템 세계에서는 데이터를 유지하기 위해 자주 사용하는 구조이다. '탐색' 시, 단시간 내에 실행할 수 있기 때문이다.
B-tree의 핵심은 데이터가 정렬된 상태로 유지되어 있다는 것이다.
그림에 표시된 사각형으로 표시된 한 개 한 개의 데이터를 '노드(Node)'라고 한다.
가장 상단의 노드를 '루트 노드(Root Node)', 중간 노드들을 '브랜치 노드(Branch Node)', 가장 아래 노드들을 '리프 노드(Leaf Node)'라고 한다. (B-tree가 되려면 위 그림에 맨왼쪽 Branch에 Leaf Node 하나가 추가되어야함)
B-tree의 경우 key와 data를 브랜치 노드와 리프 노드에 담을 수 있다. 따라서 풀 스캔을 위해 모든 노드를 탐색해야 한다.
Balanced Tree
B-tree는 Balanced Tree의 한 종류인데, Balanced Tree는 노드 삽입 및 삭제 시 스스로 균형을 맞춰주는 트리를 말한다. 기존 이진 트리의 문제점은 좌우 균형이 맞지 않다는 것이었는데, 트리가 좌우 불균형 하면 높이가 커서 검색하는데 상당히 비효율적일 수 있다. (최악의 경우엔 선형검색과 같은 O(N)의 시간복잡도를 가짐) 이를 위해 균형적으로 트리를 만들어 주면, 어느 경로를 가더라도 높이가 같다. (시간복잡도 O(logN))
Balance 트리에는 AVL 트리, Red-Black Tree, B-Tree가 있다.
균형트리
B-tree는 균형트리인데, '균형 트리'란 루트로부터 리프까지의 거리가 일정한 트리 구조를 뜻하는 것으로, 트리 중에서 특히 성능이 안정화 되어있다.
B+tree
B+tree는 B-tree의 확장 개념으로, B-tree와 달리 브랜치 노드에는 key만 담고, 리프 노드에만 key와 data를 담을 수 있으며, 각 리 노드끼리 Linked list로 연결되어 있다.
따라서 B+tree는 아래와 같은 장점을 갖는다.
1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음)
2. 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다.(리프노드에서 선형탐색)
B-tree Vs B+tree
📗참고사이트
'Algorithm > KBro Study' 카테고리의 다른 글
| [자료구조] 그래프(Graph) + 구현하기(Java의 인접행렬과 인접리스트) (0) | 2023.01.17 |
|---|---|
| [알고리즘] Brute Force(브루트 포스) (0) | 2023.01.08 |
| [자료구조] Java - 해시테이블(HashTable) 이론정리 (0) | 2022.12.23 |
| [자료구조] Java - Heap(힙) 이론정리 + 구현 + Priority Queue(우선순위 큐) (0) | 2022.12.11 |
| [자료구조]Java - Binary Search Tree(이진 탐색트리) 개념 + 구현 (0) | 2022.12.06 |