티스토리 뷰
B+ Tree
- 데이터의 빠른 접근을 위해 비단말(Non Leaf) 노드는 인덱스 역할만 수행
- B 트리 + Leaf 노드들의 데이터는 연결리스트로 표현된 색인 구조
- 실제 DB에서 사용하는 인덱싱
- Index 부분 과 Leaf Node로 구성된 순차 데이터 부분 으로 이루어짐
- 인덱스 부분의 key값은 leaf에 있는 key값을 직접 찾아가는데 사용함
- leaf 노드는 연결리스트 형태, 선형 검색이 가능
특징
- 루트노드는 적어도 2개 이상의 자식을 가져야함
- 루트노드를 제외한 모든 노드는 M/2개 부터 M개의 자식을 가짐
- 노드에는 최소 [M/2]-1개 부터 최대 M-1개의 키를 포함
- 노드의 자료수(key)가 x개라면, 자식수는 x+1개 여야함
- 최소 차수(t)는 자식수의 하한값을 의미, 최소차수가 t가 2라면 M = 2 * t - 1
- (최소차수 t가 라면 3차 B트리, key의 하한은 ceil(3/2)-1 = 1개)
B트리와의 차이점
- 모든 data가 leaf node에만 모여있음, B트리의 경우 각 노드(key)마다 data를 저장
- 모든 리프노드가 연결리스트로 연결
- B트리는 옆에있는 리프노드를 검사할때 다시 루트노드부터 검사해야하지만, B+ 트리는 리프노드에서 선형검사를 할 수 있어 시간복잡도가 굉장히 줄어듦
key 탐색, 삽입, 삭제 과정 추가예정
참고한곳
'자료구조' 카테고리의 다른 글
| Red-Black 트리(Red-Black Tree) (0) | 2021.12.24 |
|---|---|
| AVL 트리(AVL Tree) (0) | 2021.12.24 |
| B 트리(B-Tree) (0) | 2021.12.24 |
| 트라이(Trie) (0) | 2021.12.24 |
| 해시(Hash) (0) | 2021.12.23 |
Comments
Related Articles
more
