목록데이터베이스 (1)

넘치게 채우기

[자료구조] 4-10. B-트리

B-트리 B-트리는 스스로 균형을 맞추는 자가 균형 이진 트리의 확장판이다. 기존 이진 트리와 다른 점은, 한 노드에서 여러 개의 데이터를 가진다는 점이다. B트리는 탐색, 삽입, 삭제 모두 O(log N)의 시간복잡도를 가진다. 주로 디스크와 같은 물리저장소에서 빠르게 접근하기 위해서 사용된다. B트리는 다음과 같은 특징을 가진다: 1. 노드의 key 수가 k개이면, 노드의 자식은 k+1개여야 한다. 2. 노드의 key는 정렬되어야 한다. 3. 자식 노드의 key는 현재 노드의 key를 기준으로 나뉜다. 4. root 노드는 2개 이상의 자식노드를 가진다.(단, root 노드가 leaf인 경우에는 제외)\ 5. M차 트리일 때, 노드가 가질 수 있는 key값은 floor(M/2)-1부터 M-1개까지 가..
컴퓨터과학/자료구조 2023. 4. 15. 14:36
이전 Prev 1 Next 다음