Understanding B-Tree Data Deletion Process

B-트리 데이터 삭제는 리프 노드에서 발생하므로 키 수가 최소값 이하로 떨어지면 재밸런싱이 필요합니다.

### B-Tree 이해: 데이터 삭제 방법 및 특성
* 📚 이 동영상에서는 왼쪽 하위 트리는 부모보다 작은 키를 포함하고 오른쪽 하위 트리는 더 큰 키를 포함하는 이진 검색 트리(BST)의 일반화된 형태인 **B-트리에서 데이터가 어떻게 삭제되는지** 살펴봅니다.
* 🔍 B-트리는 최대 두 개의 자식으로 제한되는 이진 검색 트리와 달리 **부모 노드가 두 개 이상의 자식 노드를 가질 수 있습니다.**
* 📊 자식 노드가 x개인 B-트리의 각 노드는 **x-1개의 키**를 가지며, 이는 노드가 오름차순으로 저장된 여러 키를 포함할 수 있음을 나타냅니다.
* 🌳 B-트리의 모든 리프 노드는 동일한 레벨에 있으므로 **데이터 삽입 및 삭제 시 중요한 데이터 구조의 균일성**을 보장합니다.
* 📝 B-트리의 기본 파라미터는 자식 노드의 최대 수(m)로, 노드당 최대키는 **m-1**로, 자식 노드의 최소 수는 **m/2의 상한**으로 결정됩니다.
* ✂ B-트리의 데이터 삭제는 주로 리프 노드에서 이루어지며, **키를 삭제하면 필요한 최소 키보다 적은 수의 키**가 생성되면 트리를 다시 구조화해야 합니다.
* 🔄 노드가 최소 키 수에 미달하면 **형제 노드에서 키를 빌리거나 빌릴 수 없는 경우 형제 노드와 병합**할 수 있으며, 이 경우 트리의 구조가 추가로 재구성될 수 있습니다.
* 🛠 삭제하는 동안과 삭제한 후에 B-트리 속성을 유지하는 방법을 포함하여 **삭제 프로세스를 예시**를 통해 설명하여 구조가 균형 있고 효율적으로 유지되도록 합니다.

### B-Tree 데이터 삭제 과정 이해하기
* 📚 B-Tree에서 데이터를 삭제할 때는 **리프 노드에서만 삭제**가 이루어지며, 인터널 노드에서 삭제가 필요한 경우에는 **삭제할 데이터의 선임자 또는 후임자와 위치를 바꿔줘야 한다.**
* 🔄 삭제 후 최소 키 수 조건을 만족하지 못할 경우에는 재조정을 해야 하며, 이 과정에서 **형제 노드에게 도움**을 요청하거나 **부모 노드의 지원**을 받아야 한다.
* 👨 ‍👩‍👧‍👦 부모의 지원을 받는 경우, **형제 노드와 합쳐야 하며, 이때 합칠 때는 항상 왼쪽으로 합쳐야 한다**는 점을 기억해야 한다.
* 📝 예를 들어, **15를 삭제할 때는 9와 위치를 바꿔 리프 노드로 이동** 후 삭제가 이루어지며, 이 과정에서 B-Tree의 특성을 유지해야 한다.
* 🔍 선임자와 후임자는 항상 리프 노드에 위치하므로, **삭제할 데이터와 그 위치를 바꿔주면 최종적으로 삭제할 데이터는 리프 노드에 위치**하게 된다.
* 📊 예시를 통해 B-Tree에서의 삭제 과정을 설명하며, **"삭제는 항상 리프 노드에서 발생하게 된다"**는 점을 강조하였다.
* ⚠ ️ B-Tree에서 데이터 삭제 시에는 각 노드의 **최소 키 수 조건**을 충족하는지 항상 확인해야 하며, 필요 시 **재조정 과정을 반복**해야 한다.
* 💡 마지막으로, B-Tree에서 데이터 삽입 및 삭제 방식은 여러 가지가 있지만, 오늘 설명한 방식이 **이해하기 쉽고 효과적**이라는 점을 강조하였다.

(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-트리 속성을 유지할 수 있다.