23.09.23 B-Tree

B-Tree

B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리입니다. 또한 정렬된 순서를 보장하고, *멀티레벨 인덱싱을 통한 빠른 검색을 할 수 있기 때문에 DB에서 사용하는 자료구조 중 한 종류라고 합니다.

 

 *멀티레벨 인덱싱 : 데이터를 여러 수준의 인덱스로 구성하여 데이터 접근을 빠르게 하는 기술

 

B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있습니다. 최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 하며 다음과 같은 특징을 같습니다.

• 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있습니다.
• 노드에는 최대 M−1개 부터 [M/2]−1개의 키가 포함될 수 있습니다.
• 노드의 키가 x개라면 자식의 수는 x+1개 입니다.
• 최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t−1을 만족합니다. (최소차수 t가 2라면 3차 B트리이며, key의 하한은 1개입니다.)

 

다음은 차수가 3인 B트리 입니다. 파란색 부분은 각 노드의 key를 나타내며, 빨간색 부분은 자식 노드들을 가르키는 포인터입니다. key들은 노드 안에서 항상 정렬된 값을 가지며, 이진검색 트리처럼 각 key들의 왼쪽 자식들은 항상 key보다 작은 값을, 오른쪽은 큰 값을 가집니다.

출처 : https://velog.io/@emplam27

 

정리하면 모든 리프 노드들이 같은 레벨을 가지며 순서를 보장하고 빠른 검색을 할 수 있게 하는 트리이다. 이 때 내가 의문이 들었던 것은 자식의 수(  M/2 )와 키의 수( [M/2]−1 )이다. ( [M/2]−1)은 0인데 왜 최소차수 t가 2라면 3차 B트리이며, key의 하한은 1개입니다. 에서 모순이 생기는지 의문이 생긴다면 이것은 각 노드가 1개 이상의 키를 가진 다는 것을 전제로 하고 계산 해야 한다.

 

이 블로그에 내용이 너무 잘 정리되어서 그대로 가져오고 내가 이해되지 않았던 부분에 대한 내용을 추가했다. 이 외에도 검색이나 삽입, 삭제에 대한 내용도 있지만 한 번에 다 알 순 없으니 이런 구조라는 것만 알고 다시 찾아보자