10000COW

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)일 수 밖..