외부탐색

목차

외부탐색

m-원 탐색 트리

m-원 탐색 트리의 특성

3-원 탐색 트리의 예

차수가 3인 B-tree의 예

B-tree의 성능

B*-tree

B+-tree

본문내용

개념
인텍스의 성능은 트리의 가지 수를 증가시킴으로써 향상시킬 수 있다.
m-원 탐색 트리는 모든 노드가 m보다 같거나 작은 진출 차수를 갖는 트리
트리의 각 노드는 다음과 같은 구조를 갖는다.
Pn : 노드의 서브트리에 대한 포인터
kn-1 : 키 값
키의 수는 포인터의 수보다 1만큼 작다.
각 노드는 포인터의 수가 m보다 작거나 같으므로 n≤m-1
노드의 키 값은 오름차순(ki < ki+1)
i=0,…n-1인 i에 대해 Pi가 가리키는 서브트리의 모든 노드들의 키 값은 ki의 값보다 작다.
Pn이 가리키는 서브트리의 모든 노드들의 키 값은 kn-1의 키 값보다 크다
i=0,…, n인 i에 대해 Pi가 가리키는 서브트리 또한 m-원 탐색 트리

키워드

B*-tree,   m-원 탐색 트리,   외부탐색,   3-원 탐색 트리의 예,   B+-tree