[자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정

B- 트리란? 보통 B 트리라고 하면 B- 트리를 의미한다. B 트리는 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 이러한 B 트리의 다음과 같은 특징을 그림과 함께 알아보자. 1. 노드에는 2개 이상의 데이터(key)가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다. [그림 1]처럼 한 노드에 2개, 3개의 데이터가 들어가 있을 수 있으며, 항상 정렬된 상태로 저장된다. 2. 내부 노드는 M/2 ~ M개의 자식을 가질 수 있다. 최대 M개의 자식을 가질 수 있는 B 트리를 M차 B트리라고 한다. [그림 1]은 3차 B트리를 나타낸다. 즉, 3차 B트리의 리프 노드를 제외한 내부 노드는 1개~3개의 자식을 가질 수 있다. 3..

원문링크 : [자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정