B-Tree

B-트리는 데이터베이스 시스템과 파일 시스템에서 사용되는 자료구조이다.

데이터를 효율적으로 관리하기 위해 설계되었다.

 

B-트리의 구조

B-트리는 노드 기반의 트리 구조인데, 각각의 노드는 공통된 특징을 가진다.

 

B-트리 노드의 구조

1. 키 : 하나 이상의 키를 가진다. 키는 데이터를 정렬하는데 사용된다.

2. 자식 포인터 : 노드는 자식 노드를 가리키는 포인터를 가지고 있다. 하나 이상 가질 수 있음.

 

이때, M차 B-트리의 의미는

 

각 노드는 자식 노드를 (M~M/2)개 가질 수 있다.

각 노드는 키를 M-1 ~ M/2-1 개 가질 수 있다.

 

노드의 키가 N개이면 자식 노드를 최대 N+1 개 가질 수 있다.

 

B-트리는 균형 트리이기 때문에 각 노드는 최소, 최대한의 키를 가지는 장점이 있다.

효율적인 검색 및 삽입/삭제가 가능하다. O(log(n))

하나의 노드가 여러 키를 가지기 때문에 트리의 깊이를 줄 일 수 있다.

다만, 균형 유지를 위해 삽입/삭제 이후에 추가 연산 및 새로운 노드 생성이 있을 수 있다.

 

 

B-트리에 데이터 삽입 시에는 1. 비분할 2. 분할 로 나뉜다.

 

참고로 B-트리의 삽입은 항상 리프노드까지 내려가며 이후에 분할, 비분할로 경우가 나뉜다.

 

1. 비분할

비분할은 데이터가 삽입 될 위치의 리프노드가 최대 허용 KEY 갯수를 초과하지 않았을 때 이다.

아직 들어갈 KEY 공간이 존재하므로 해당 노드에 데이터를 삽입하면 끝.

 

2. 분할

분할은 데이터가 삽입 될 위치의 리프노드가 최대 허용 KEY 갯수를 초과하였을 때 일어난다.

이때, 해당 KEY 를 초과해서 가지고 있는 리프노드는 중앙 KEY 값을 부모 노드로 올리거나 부모 노드가 없을 시 상위 노드로 생성되어 올라간다.

중앙 KEY  가 보모 노드로 올라갔을 때 부모 노드도 KEY 개수를 초과 했을 시에는 다시 중앙 KEY 값을 부모로 올리거나 부모가 없을 시 생성한다.

 

데이터 삭제

1. 삭제할 키가 리프노드에 존재하며 재정립이 필요 없다면 데이터를 삭제하고 끝.

 

2. 삭제할 키가 리프노드에 존재하나 키 삭제로 인해 부모 노드의 자식 노드 포인터 중 한 곳이 NULL 될 때

형제 노드의 키 갯수에 따라 부모 노드의 키를 이용하여 NULL 상태의 자식 노드 포인터를 채워준다.

부모 노드의 키로부터 NULL 포인터를 채우는것은 맞지만, 형제 노드의 키 갯수에 따라 부모 노드의 키 갯수에 변동이 있을 수 있다.

 

3. 삭제할 키가 리프노드가 아닌 내부 노드일 경우

  3-1 삭제할 키가 존재하는 내부 노드가 2개 이상의 키를 가질 경우 키를 삭제하고 자식으로부터 키를 받아 삭제된 키의 위치를 메꾼다.

  3-2 삭제할 키가 존재하는 내부 노드가 1개의 키를 가질 경우 키가 삭제되면서 노드가 포함된 계층의 층수가 -1 되기 때문에 이를 막기 위해 부모 및 형제 노드의 재정립으로 각 계층의 층수를 유지한다.