이진트리는 하나의 부모가 두개의 자식밖에 갖지못합니다. 또 균형이 맞지 않으면 검색효율이 선형검색만큼 떨어지죠. 따라서 B Tree는 트리의 균형까지 자동으로 맞추어 주는 자료구조입니다. 이렇게하면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보일 수 있으니까요.

B Tree

• 데이터베이스, 파일시스템에서 널리 사용되는 트리 자료구조의 일종입니다.
• 이진 트리를 확장해서, 더 많은 수의 자식을 가질 수 있게 일반화 시킨것이죠
• 자식 수에 대한 일반화를 진행하면서, 하나의 레벨에 더 저장되는 것 뿐 아니라 트리의 균형을 자동으로 맞춰주는 로직까지 갖추었습니다. 단순하고 효율적이며 레벨로만 따지면 완전히 균형을 맞춘 트리입니다.

장점

대량의 데이터를 처리할 때, 하나의 노드에 많은 데이터를 가질 수 있어 효율적입니다. 대량 데이터는 메모리보다 블럭 단위로 입출력하는 하드디스크나 SSD에 저장해야하기때문이죠.

한 블럭이 만약 1024바이트라 가정합시다. 하지만 2바이트를 읽으나 1024바이트를 읽으나 입출력 비용은 동일합니다. 따라서 하나의 노드를 모두 1024바이트로 꽉 채워 조절하면 입출력에 있어서 굉장히 효율적입니다. → B Tree는 이런 장점을 토대로 많은 데이터베이스 시스템의 인덱스 저장방법으로 사용됩니다.

조건

• 노드의 자료수가 N이면, 자식 수는 N+1이어야한다.
• 각 노드의 자료는 정렬된 상태여야 한다.
• 루트노드는 적어도 2개 이상의 자식을 가져야한다.
• 루트노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
• 외부노드로 가는 경로의 길이는 모두 같다
• 입력자료는 중복될 수 없다.