BJ.54-2 B tree 데이터 삭제 동작 방식을 설명합니다 (DB 인덱스과 관련있는 자료 구조)

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널


쉬운코드

B-트리는 이진 탐색 트리(바이너리 서치 트리)를 일반화한 트리이다.

키를 기준으로 왼쪽 서브 트리는 키보다 작은 값, 오른쪽 서브 트리는 키보다 큰 값을 가진다.

B-트리는 이진 탐색 트리와 달리 부모 노드가 두 개 이상의 자녀 노드를 가질 수 있다.

노드가 x개의 자녀 노드를 가지면 키의 수는 x-1개이다.

각 노드의 키는 오름차순으로 저장된다.

모든 리프 노드는 같은 레벨에 있다.

가장 중요한 파라미터는 각 노드가 가질 수 있는 최대 자녀 노드 수(m)이다.

각 노드의 최대 키 수는 m-1이다.

각 노드의 최소 자녀 노드 수는 m/2를 올림한 값이다.

각 노드의 최소 키 수는 최소 자녀 노드 수 -1이다.

데이터 삭제는 항상 리프 노드에서 발생한다.

삭제 후 노드의 키 수가 최소 키 수보다 적으면 트리를 재조정한다.

최소 키 수 조건은 B-트리의 중요한 조건이다.

3차 B-트리(m=3)에서 최소 키 수는 1이다.

6 삭제: 리프 노드에서 삭제 후 최소 키 수 조건 만족.

5 삭제: 삭제 후 노드의 키 수가 0이 되어 최소 키 수 조건 위반.

1. 형제 노드로부터 키를 빌려온다.

2. 부모 노드로부터 키를 빌려오고 형제 노드와 합친다.

3. 부모 노드에서도 문제가 발생하면 재조정을 반복한다.

인터널 노드 데이터 삭제는 리프 노드 데이터와 위치를 바꾼 후 삭제한다.

삭제하려는 데이터의 선임자 또는 후임자와 위치를 바꾼다.

선임자 또는 후임자는 항상 리프 노드에 있다.

선임자 또는 후임자와 위치를 바꾸면 B-트리 속성을 유지할 수 있다.