10000COW

2-3-4 트리란? 탐색트리 중 하나로, 이진 트리가 아니다. 즉, 자식 노드가 2개보다 많을 수 있다. 특징으로 1. 이름처럼 자식 노드의 개수는 2개 또는 3개 또는 4개를 가질 수 있다. (즉, 최소 2개 ~ 최대 4개) 2. 모든 leaf 노드가 같은 level에 존재한다. 3. 삽입 시, leaf 노드에 삽입한다. 삽입 추가할 key가 root부터 leaf 노드까지 내려가면서, 4-노드이면 split하면서 내려간다. split할 때 중간 값은 부모 노드로 무조건 올라갈 수 있는데, 그 이유는 key가 내려오면서 4-노드인 경우 split을 이미 해놨기 때문이다. split하는데 O(1)이 걸리고, 최악의 경우 leaf노드까지 내려가면서 매번 split 해야하므로(log n번), 삽입 시의 시간복..

B-트리란? B-트리(B-tree)는 데이터베이스와 파일 시스템에 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드에 여러 개의 데이터를 저장한다. 차수가 p인 B-트리의 특성 1)적어도 노드의 반은 채워야 한다. 즉, root와 leaf를 제외한 모든 노드의 pointer 수 = 서브트리 수 = 최소 ⌈p / 2⌉개, 최대 p 개 2) root는 pointer를 2개 이상 가져야 한다. 즉, root의 서브트리의 수 >= 2 3) 모든 leaf는 같은 level (즉, 균형 트리이다) 4) 노드의 key 개수 leaf가 아닌 노드: pointer 수 - 1 개 = 서브트리 수 - 1개 (아래 B-트리 기본 구조 그림을 보면, key의 개수는 (pointer 개수 - 1)일 수 밖..