한달꾸 한달꾸

B-Tree - 삭제 B Tree 삽입에서 가득 찬 노드들을 미리 분할했던 것 처럼, 삭제시에도 최소 키의 개수를 가지는 노드들이 키를 더 많이 가질 수 있도록 미리 처리한다. k를 찾아 재귀적으로 내려가는 과정에서 방문하는 경로에 존재하는 키의 개수가 (t-1)인 경우 형제 노드에서 키를 가져오거나, 형제노드와 병합하는 과정을 거친다. 삭제 과정에서 발생할 수 있는 모든 경우의 수에 대해 알아보자. 1. 리프 노드 x를 방문했을 때, x 내에 k가 존재한다. 2. 리프 노드가 아닌 노드 x를 방문했을 때, x 내에 k가 존재한다. 3. 리프 노드가 아닌 노드 x를 방문했을 때, x 내에 k가 존재하지 않는다. 1. 리프 노드 x를 방문했을 때, x 내에 k가 존재한다. 리프 노드 x 내에 k가 존재한다..

이번 포스팅에서는 트리를 단순화하기 위해, 키와 관련된 부수적인 정보는 키와 같은 노드에 있다고 가정한다. Abdul Bari 교수님의 10.2 B Trees and B+ Trees. How they are useful in Databases click 위의 강의에서 설명하는 방식과 다른 방식의 삽입을 설명합니다. 해당 포스팅에서 설명하는 방식은 루트 노드에서 리프 노드까지 Top-Down으로 내려가며 재귀적으로 탐색하는 방식입니다. B-Tree - 기본 규칙 1. 모든 노드 x는 아래와 같은 속성이 있다. a. x.n은 노드 x에 현재 저장되어 있는 키의 개수다. b. x의 key들은 x.key(1) leaf; z->n = DEGREE - 1; for (int j = 0; j < DEGREE - 1; ..

B-Tree 1월 8일 부터 1월 13일까지, B - Tree와 B+ - Tree를 구현하는 프로젝트를 진행하고 있다. 오늘(1월 11일)을 시작으로 한 주 동안 B - Tree의 원리, 삽입 그리고 삭제가 어떻게 이루어지는지에 대해 알아볼 것이다. B - Tree 관련 포스팅들은 [Introductions to Algorithms (Third Edition), Tomas H. Corman]의 내용을 토대로 부족한 설명들과 예시를 덧 붙일 예정이다. 들어가기 전에 B - Tree를 공부하며, 인터넷의 여러 강의들 그리고 블로그들을 참고했다. 그런데, B - Tree를 구현하는 방법이 조금씩 달라서 이해하는데 혼란스러웠던 점이 있다. 특히, 대부분의 자료들에서 삽입에 대한 설명보다 삭제에 대한 설명이 부족..