B-Tree는 무엇이고 어떨 때 사용할 수 있나요?

[eunjungL]

.

[linirini]

이진 트리는 하나의 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면 검색 효율이 선형 검색 급으로 떨어진다. 하지만 이진 트리 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있기 때문에 여기서 확장하여 더 많은 자식을 가질 수 있도록 일반화 시킨 것이 B Tree이다. 자식 수에 대한 일반화를 진행하면서, 하나의 레벨에 더 저장되는 것 뿐만 아니라 트리의 균형을 자동으로 맞춰주는 로직까지 갖췄다.
B-tree는 빠른 검색을 요구하는 데이터베이스 인덱스 관리나 파일 시스템에서 사용한다.

[PgmJun]

탐색

탐색은 일반적인 방식, 즉 이진 탐색 트리와 동일한 방식으로 수행된다. 루트에서 시작하여, 하향식으로 탐색 대상의 값을 구분 값과 비교하며 자식 포인터를 찾아나가는 과정으로 진행한다.

삽입

삽입될 노드가 어느 위치로 삽입될지 찾아 해당 부모 노드에 삽입한다.
부적절한 상태의 노드가 없다면, 삽입 과정을 종료한다.
만약, 어떤 노드가 너무 많은 항목을 가지고 있다면, 이를 두 노드로 분리한다. 이 과정을 반복적으로 트리를 타고 올라가며 진행한다.
만약 루트 노드를 분리하였다면, 새로운 루트 노드를 만든다.

• 부적절한 상태에 있는 노드란, 그 노드에 허용된 자식 노드의 숫자가 허용된 범위 밖인 노드를 의미한다.

[Chocochip101]

@eunjungL 카테고리가 Java인데, B-tree를 물어보신 의도가 있나요?