자료구조 - B트리

- B트리란? 색인(index)의 규모가 매우 크다면 메인 메모리가 아니라 불가피하게 디스크에서 데이터를 둬야한다. 메인메모리가 충분하지 않을 때도 마찬가지이다. 디스크에 색인을 두어야 한다면 디스크의 특성을 최대한 활용하여 디스크 접근 시간으로 인한 비효율을 최대한 줄여야 한다. 이로 인해 나온 것이 B트리이다. - B트리의 특징 1) k개의 노드가 있다면 k+1개의 자식트리를 가진다. 2) 서브 트리 Ti의 모든 키들은 key i-1보다 크고 key i보다 작다. 3) 루트를 제외한 모든 노드는 [k/2] ~ k개의 키를 갖는다. 4) 모든 리프 노드는 같은 깊이를 가진다. 5) 노드는 정렬된 상태이다. 6) 루트는 2개 이상의 자식노드를 가진다. -B트리 색인 ex) 8 색인 과정 - B트리 삽입 ..

원문링크 : 자료구조 - B트리