[Data_structure] B tree

B-트리 개요

정의

B-트리(B-tree)는 데이터를 효율적으로 저장하고 관리하기 위한 정렬하여 탐색, 삼입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조이다.

B-트리 장점

빠른 검색 및 접근 속도: B-트리는 균형 잡힌 구조를 유지하며 모든 leaf 노드까지의 경로 길이가 동일하다. 이는 데이터를 검색하는 데 필요한 시간을 최소화하고, 이진 탐색을 활용하여 빠른 검색 속도를 제공한다.

B-트리 특징

• 자녀 노드의 최대 개수를 늘리기 위해서
  부모 노드에 key를 하나 이상 저장한다
• 부모 노드의 key들을 오름차순으로 정렬한다
• 정렬된 순서에 따라 자녀 노드들의 key값의 범위가 결정된다

(이런 방식을 이용하면 자녀 노드의 수를 내 임의대로 결정해서 쓸수 있다.)

💡 텍스트B-트리의 중요 4가지 파라미터

• m 각 노드의 최대 자녀 노드 수
• m-1 각 노드의 최대 key 수
• [m/2] 각 노드의 최소 자녀 노드 수
• [m/2]-1 각 노드의 최소 key 수 **
  root node, leaf node 제외
  root node 제외

B tree 노드의 key 수와 자녀 수의 관계

• internal 노드의 key수가 x개라면 자녀의 노드의 수는 언제나 x+1 개다

• 노드가 최소 하나의 key는 가지기 때문에 auc ck B tree 인지와 상관없이 internal 노드는 최소 두개의 자녀는 가진다