B-Tree & B+Tree

이진트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조이다.

📺 B Tree

이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 균형이진트리의 확장판

이진트리와 달리 하나의 노드에 많은 정보를 갖거나, 두 개 이상의 자식을 가질 수도 있다.

하나의 노드에 여러 자료를 배치하며서 이진트리보다 많은 데이터를 더 효율적으로 저장소에 담을 수 있게 되었다.

• 자식 수에 대한 일반화를 진행하면서, 하나의 레벨에 더 저장되는 것 뿐만 아니라 트리의 균형을 자동으로 맞춰주는 로직까지 갖추었다.

• 단순하고 효율적이며, 레벨로만 따지면 완전히 균형을 맞춘 트리다.

• M개의 자식을 가질 수 있는 B-Tree ⇒ M차 B-Tree

특징

• 각 노드의 자료는 정렬된다

• 자료는 중복되지 않는다.

• 모든 leaf node는 같은 레벨이다

• root node는 자신이 leaf node가 되지 않는 이상 적어도 2개 이상의 자식을 가진다

• root node와 lead node를 제외한 노드들은 최대 $M$ 개부터 최소 $M/2$ 개까지의 자식을 가질 수 있다.

• 노드의 키는 최대 $M-1$개부터 최소 $(M/2) - 1$ 개의 키가 포함될 수 있습니다.

• 자식 수의 하한값을 $t$ 라고 하면, $M = 2t - 1$ 을 만족합니다.

🛁 B+Tree

B-Tree는 탐색을 위해 노드를 찾아서 이동을 해야 한다 이러한 문제 해경을 위해 B+Tree는 같은 레벨의 모든 키 값들이 정렬되어 있고, 같은 레벨의 Sibiling node는 연결리스트 형태로 이어져 있다.

같은 레벨의 형제 노드는 모두 연결되어 있어 키 값이 중복되지 않는다.

leaf node에 모든 자료들이 존재하고, 그 자료들이 연결리스트에 연결되어 있어 탐색에 매우 유리하다

leaf node가 아닌 자료는 인덱스 노드, leaf node 자료는 데이터 노드라 부른다.

인덱스 노드의 Value값에는 다음 노드를 가리킬 수 있는 포인터 주소가 존재하고, 데이터 노드의 Value값에 데이터가 존재한다.

→ 키값은 중복될 수 있다. → 인덱스 노드와 데이터 노드에서 동시에 등장이 가능하다

데이터 검색을 위해서는 반드시 leaf node까지 내려가야 한다는 특징을 가진다.

특징

• 데이터 노드의 자료는 정렬되어 있다

• 데이터 노드에서는 데이터가 중복되지 않는다

• 모든 leaf node는 같은 레벨에 있다

• leaf node가 아닌 node는 키 값의 수는 그 노드의 서브트리수보다 하나가 적다

• 모든 leaf node는 연결리스트로 연결되어있다.

🔗 참조한 사이트

https://ssocoit.tistory.com/217 [코딩하는 경제학도]

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer Science/Data Structure/B Tree %26 B%2B Tree.md