여기서 B-트리가 무엇인지 살펴보겠습니다. B-트리는 특화된 m-way 탐색 트리입니다. 이것은 디스크 액세스에 널리 사용될 수 있습니다. 차수가 m인 B-트리는 최대 m-1개의 키와 m개의 자식을 가질 수 있습니다. 이것은 단일 노드에 많은 수의 요소를 저장할 수 있습니다. 그래서 키가 상대적으로 작습니다. 이것이 B-트리의 큰 장점 중 하나입니다.
B-Tree는 하나의 m-way tree의 모든 속성을 가지고 있습니다. 다른 속성이 있습니다.
-
B-Tree의 모든 노드는 최대 m개의 자식을 보유합니다.
-
루트와 잎을 제외한 모든 노드는 최소 m/2개의 자식을 보유할 수 있습니다.
-
루트 노드에는 최소한 두 개의 자식이 있어야 합니다.
-
모든 리프 노드는 동일한 수준이어야 합니다.
B-트리의 예
검색, 삽입, 삭제와 같은 기본 작업을 지원합니다. 각 노드에서 항목이 정렬됩니다. 위치 i에 있는 요소는 앞뒤에 자식이 있습니다. 따라서 이전에 정렬된 자식은 더 작은 값을 보유하고 오른쪽에 있는 자식은 더 큰 값을 보유하게 됩니다.