B Tree 정의와 데이터 삽입

* 나무위키의 내용 및

* 아래 링크의 유튜브 영상을 보고  본 글은 제 학습의 결과를 정리한 내용입니다.

https://youtu.be/bqkcoSm_rCs?si=TVQzH3urhF3rorru 

 

정의

B 트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.

 

방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효율적이다. B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 O(logn) 지수시간으로 할 수 있다

 

특징

자식 노드의 개수를 늘려 저장하기 위해서 최소 1개 이상의 key는 부모노드에 존재한다.

부모노드의 key는 오름차순으로 정렬되어 있다.

부모노드가 정렬이 되어있다면, (k1 < k2 라면) 자식노드의 key값의 범위가 정해진다.

 

부모가 저장하는 key개수를 정함에 따라 자식노드의 최대갯수를 정해서 사용할 수 있다. 

 

최대 n개의 자식을 가질수 있는 B Tree를  n차 B Tree라 부른다.

 

- n 최대 자식의 개수 

- n-1 각 노드의 최대 Key의 개수

- ceil(n / 2)  각 노드의 최소 자식의 개수 (root, leaf node는 예외)

- ceil(n / 2) - 1 각 노드의 최소 Key의 개수 (root는 예외)

 

* internal node(leaf node가 아닌 노드)라면  key의 개수가 x개 라면 자식의 노드의 수는 x + 1이다.

* B Tree의 차수에 관계없이 부모 노드의 key는 1개 이상이기 때문에 Internal 노드의 개수는 최소 2개이다

 

데이터 삽입

*추가를 leaf node에서 진행한다.

 

1. 부적절한 상태에 있는 노드가 발생할 경우 가운데 key값을 기준으로 분할하고 가운데 key는 부모노드로 올린다.

2. 모든 leaf node들은 데이터 삽입이 끝난후 동일한 level에 있다 (Balanced Tree)

- 모든 노드가 만족된 상태일때 까지 재귀적으로 실행.

 

Balanced -->  leaf node들의 차이가 높이 차이가 2 이상 차이나지 않는 상태

 

예시) 3차 B Tree

 

insert 1, 15

insert 2

insert 5

insert 30

insert 90

insert 20

insert 7

insert 9

insert 8

insert 10

insert 50

insert 70

insert 60

insert 40