ComputerScience/자료구조

[자료구조] B Tree

B 트리는 이진트리에서 발전되어 모든 리프 노드들이 같은 레벨을 가질 수 있도록 자동으로 밸린스를 맞추는 트리입니다. 정렬된 순서를 보장하고, 멀티레벨 인덱싱을 통한 빠른 검색을 할 수 있기 때문에 DB에서 사용하는 자료구조중 한 종류입니다. B트리는 하나의 노드에 다수의 정보를 저장할 수 있습니다. 최대 M개의 자식을 가질 수 있는 트리를 M차 B트리라고 하며, 다음과 같은 특징을 갖습니다. 노드는 최대 M개부터 M/2개 까지의 자식을 가질 수 있습니다. 노드에는 최대 M-1개부터 M/2 -1 개의 키가 포함될 수 있습니다. 노드의 키가 x개 라면 자식의 수는 x + 1개입니다. 최소 차수는 자식수의 하한 값을 의미하며, 최소 차수가 t 라면 M=2t-1을 만족합니다. (최소 차수가 2라면 3차 B트리..