B-Tree B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 트리다. 정렬된 순서를 보장하고, 멀티 레벨 인덱싱을 통한 빠른 검색이 가능하다. B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 지식을 가질 수 있는 B트리를 M차 B트리라고하며 다음과 같은 특징을 가진다. 노드는 최대 M개부터 최소 M/2개 까지의 자식을 가질 수 있다. 노드에는 최대 M-1개 부터 최소 [M/2]-1개의 키가 포함 될 수 있다. 노드의 키가 x라면 자식의 수는 x+1개 이다. 최소차수는 자식수의 하한값을 의미, 최소차수가 t라면 M=2t-1를 만족한다. Key 검색과정 루트노드에서 시작하여 하향식으로 검색을 수행한다(검색하고..