B- Tree

정의

• 모든 리프 노드가 동일한 레벨에 있어 효율적인 검색 및 삽입, 삭제가 가능한 자체 균형 트리
• 이진 트리를 일반화 한 트리
  • 이진 트리와 다르게 한 노드에 여러 개의 자식 노드를 가진다(2개 제약 없음)
  • 부모 노드도 1개 이상의 키를 가진다.

특징

• balance
  • 모든 리프 노드는 같은 레벨에 존재
  • 이 특성으로 인해 데이터 크기에 상관없이 일정한 데이터 접근속도 유지
• self balancing
  • 데이터 삽입/삭제의 경우 b- tree는 자동적으로 밸런스 유지 작업을 수행
• mulitiple keys per node
  • 각 노드마다 여러개의 키를 가질 수 있다.
  • 이 특성으로 인해 메모리를 효율적으로 사용하고 트리의 depth을 낮추게 된다.
• order
  • b- tree의 key는 정렬된 상태를 유지한다.
  • 이 특성으로 트리 검색에 효율적이다.

property

• M : 각 노드의 최대 자녀 노드 수
  • 최대 M개의 자녀 노드를 가질 수 있는 B-Tree는 M차 B-tree
• M-1 : 각 노드의 최대 키 개수
  • 5차 B-Tree에서 부모 노드의 최대 키는 4개
• ceil(M/2) : 각 노드의 최소 자녀 노드 수
  • 5차 B-Tree의 경우, 5/2 = 2.5를 올림한 3이 최소 자녀 노드의 수
• ceil(M/2) - 1 : 각 노드의 최소 키 수
  • root node 제외

B-Tree 연산

insert

• 데이터 추가는 항상 리프 노드에 한다.
• 삽입 후 노드가 넘치게 되면 가운데 키를 기준으로 좌우 키를 분할하고 가운데 키는 승진한다.
  • M차 B-Tree에서 노드 M-1개 보다 더 많은 키가 생기는 경우

delete

• 데이터 삭제는 항상 리프 노드에 한다.
  • internal 노드에 데이터가 있는 경우 리프 노드의 데이터와 위치를 교환한 후 진행한다.
• 삭제 후 노드가 최소 키 수 보다 적어진다면 조정 작업을 진행한다.

참고자료

geeksforgeeks- b- tree
깃짱코딩 - [자료구조] B-Tree의 개념, 파라미터, 데이터 삽입, 삭제 과정을 알아보자!