B* 트리: Difference between revisions
From IT Wiki
(새 문서: 현대 RDBMS에서 가장 많이 사용되는 인덱스 구조로, B 트리의 개선 버전 == 특징 == * 노드의 약 2/3이상이 채워지는 B트리 * 노드가 꽉 차면...) |
mNo edit summary |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
현대 RDBMS에서 가장 많이 사용되는 인덱스 구조로, B 트리의 개선 버전 | [[분류:자료 구조]][[분류:데이터베이스]] | ||
;현대 RDBMS에서 가장 많이 사용되는 인덱스 구조로, B 트리의 개선 버전 | |||
== 특징 == | == 특징 == | ||
| Line 6: | Line 7: | ||
* 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮김 | * 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮김 | ||
* 삽입/ 삭제 시 발생하는 노드 분리를 줄이려고 고안됨 | * 삽입/ 삭제 시 발생하는 노드 분리를 줄이려고 고안됨 | ||
* 데이터가 기본적으로 정렬되어 저장됨 | |||
* Max/Min의 효율적 처리 가능 | |||
== 구성 == | == 구성 == | ||
Latest revision as of 23:22, 31 August 2021
- 현대 RDBMS에서 가장 많이 사용되는 인덱스 구조로, B 트리의 개선 버전
특징[edit | edit source]
- 노드의 약 2/3이상이 채워지는 B트리
- 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮김
- 삽입/ 삭제 시 발생하는 노드 분리를 줄이려고 고안됨
- 데이터가 기본적으로 정렬되어 저장됨
- Max/Min의 효율적 처리 가능
구성[edit | edit source]
- Root 노드
- Branch 노드
- Leaf 노드
규칙[edit | edit source]
차수가 m인 B*트리는 다음 조건을 만족하는 B 트리이다
- 공집합이거나 높이가 1이상인 m원 탐색 트리이다.
- Root 노드는 2개 이상 2(2m-2)/3+1 개 이하의 자식노드를 갖는다.
- 내부노드는 최소한 (2m-1)/3개의 자식노드 를 갖다.
- 모든 Leaf 노드는 동일한 레벨에 놓인다.
- 포인터가 k개인 Leaf가 아닌 노드는 k-1개의 키를 갖는다. (Root 노드 포함)
