[자료구조] B+ tree & B- tree
[자료구조] B+ tree & B- tree
검색을 위한 이진탐색트리
부모노드를 기준으로 왼쪽서브트리의 노드들은 모두 부모노드보다 작고, 오른쪽 서브 트리의 노드들은 모두 부모노드보다 큽니다.
이러한 특성 덕분에 어떤 수를 탐색할 때 시간복잡도는 트리의 높이가 h라고 했을 때, O(h)가 됩니다.
이진탐색 트리가 다음과 같이 경사 이진 트리 형태이면, 높이가 n이므로 O(n)의 시간복잡도를 가져서 비효율적입니다.
Balance tree는 노드가 삽일될 때마다 자동으로 균형을 맞춰주는 트리입니다.
B- tree, B+ -tree, B* -tree는 Balance tree중 하나로 이진 트리와 다르게 노드가 2개이상의 자식을 가질 수 있습니다.
주로 데이터베이스의 인덱스가 B- tree 구조입니다.
B- tree
M차 b- tree는 한 노드에 들어갈 수 있는 최대 키의 개수가 M개입니다.M차 b-tree의 특성은 다음과 같습니다.
- 한 노드의 키가 N개라면, 그 노드의 자식의 갯수는 반드시 N+1이어야 한다.
따라서 tree의 max degree는 M+1) - root node가 leaf node인경우를 제외하고 항상 최소 2개의 자식을 가진다.
- root node를 제외한 모든 노드는 적어도 l M/2 l 개의 키를 가지고 있어야 한다.
- 모든 leaf node들은 같은 level에 있어야 한다.
- node내의 key값들은 오름차순이다. (중복된 키 허용 x)
- node의 자료 Dk 왼쪽 서브트리는 Dk보다 작은 값들이고, 오른쪽 서브트리는 Dk보다 큰 값들이다.
B+ -tree
정렬된 데이터를 표현하기 위한 트리자료입니다.
주로 데이터베이스에서 인덱스에 이용되고, B- tree의 변형된 형태입니다.
B+ 트리는 인덱스구조에서 순차접근에 대한 문제의 해결책으로 제시되었습니다.
B- 트리에서는 특정 key값이 하나의 노드에서만 존재할 수 있지만, B+ 트리에서는 leaf노드와 leaf의 부모 노드에서 공존할 수 있고,
B+ 트리의 비단말 노드(index set)들은 데이터의 빠른 접근을 위한 인덱스 역할만 하기 때문에 키와 포인터로만 구성되어있습니다.
그리고 leaf 노드들은 연결 리스트 형태로 서로 연결되어 있어 이를 순차집합(sequence set)이라고 하며 오름차순으로 정렬되어 있습니다.
고로 B+ 트리는 (기존의 B- 트리 + 데이터의 연결 리스트)로 구현된 색인구조라고 할 수 있습니다.
이 때문에 순차적인 탐색에 매우 유리합니다.
출처
댓글
댓글 쓰기